基于变量传播的弧一致性算法

Arc Consistency Algorithm Based on Variable Transmission

在AC-3算法的基础上,提出了采用面向变量的约束传播机制新的弧一致性算法(IAC3),算法(IAC3)引入了一个小型的附加数据结构,使得新算法的时间复杂度降低了一个幂次为O(ed2).以小的空间代价换取了显著时间效率.新算法对于通用弧一致性算法的改进效果是明显的,是对现有弧一致性算法的提高和完善,使其实用性更好,应用前景更宽.

On the basis of AC -3 algorithm, the paper presents a new arc consistency algorithm （IAC3） using the variable - oriented constraint propagation mechanism. The algorithm （IAC3） introduces a somall additional data structure, making the time coonplexity of the new algorithm reduce a power as O（ed2）. The time efficiency is achieved at a cost small space. The new algorithm has greatly improved the effect of the generic arc consistency algorithm.