弧一致性符号ADD算法及在CSP求解中的应用

Symbolic ADD Algorithms for Arc Consistency and Application in Constraint Satisfaction Problem Solving

约束满足问题(CSP)是人工智能领域中一个重要的研究课题,弧一致性(AC)技术是提高约束满足问题求解效率的一种有效技术。对传统弧一致性技术进行了改进,给出了弧一致性的符号代数决策图(ADD)算法并将其应用于CSP求解。传统弧一致性技术在压缩问题的搜索空间时,一次只能处理一条约束上的一个值对;而借助ADD技术来压缩问题搜索空间,可以一次处理多条约束。算法首先通过01编码将CSP问题描述成伪布尔函数,并由ADD进行表示。然后基于传统弧一致性技术的算法思想,利用ADD的交、并和提取操作来实现约束传播和变量域过滤。最后将弧一致性的符号ADD算法嵌入到BT搜索算法中来实现对CSP的求解。对标准库中的测试用例以及随机生成的测试用例进行了实验仿真,结果表明,该算法求解CSP的时间既优于带弧一致性维护的回跳算法MAC3+BJ和MAC2001+BJ,也优于采用传统数据结构进行预处理的CSP求解算法BT+MPAC和BT+MPAC*。

Constraint satisfaction problem （CSP） is an important research topic in the field of artificial intelligence, and arc consistency （AC） is an effective technology to improve the CSP solving efficiency. The symbolic algebraic decision diagram （ADD） algorithm for arc consistency was proposed here to improve the traditional arc consistency technology and was applied in CSP solving. In this paper,ADD was used to compress the search space. It can process multiple con- strains in one time, not as the traditional algorithm which can only deal with one value pair in a constraint per step. Fist- ly, CSP was described as pseudo-Boolean function by 01 coding and represented by ADD. Secondly, based on traditional arc consistency algorithm, the ADD operations intersection, union and abstraction were used to achieve constraint propa- gation and variable domain filtering. Finally, the symbolic algebraic decision diagram （ADD） algorithm for arc consisten- cy was embedded in BT search algorithm to solve the CSP. The result of experimental simulation to solve some prob- lems in benchmark and randomly generated test case shows that the efficiency is higher than backjumping algorithm maintained with AC, such as MAC3 ＋BJ and MAC2001 ＋B J, meanwhile the performance is better than algorithms BT ＋MPAC and BT＋MPAC which is based on AC preproeess realized by traditional data structure in CSP solving.