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

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