一种面向变量传播的弧一致性算法

在AC-3算法的基础上,提出了采用面向变量的约束传播机制新的弧一致性算法(Improved-AC3),算法(Improved-AC3)完全脱离附加的数据结构,使得程序的空间复杂度非常小,也避免了新算法在维护数据结构上的开销,是一种空间复杂度优先的通用弧一致性算法.新算法对于通用弧一致性算法的改进效果是明显的,是对现有弧一致性算法的提高和完善,使其实用性更好,应用前景更宽.

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

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