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

计算机科学 ›› 2013, Vol. 40 ›› Issue (12): 243-247.

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

王腾飞,徐周波,古天龙

桂林电子科技大学广西可信软件重点实验室桂林541004;桂林电子科技大学广西可信软件重点实验室桂林541004;桂林电子科技大学广西可信软件重点实验室桂林541004

出版日期:2018-11-16 发布日期:2018-11-16
基金资助:
本文受国家自然科学基金(60963010,5,61262030),广西研究生教育创新计划(2011105950812M23)资助

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

WANG Teng-fei,XU Zhou-bo and GU Tian-long

Online:2018-11-16 Published:2018-11-16

摘要/Abstract

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

关键词: 约束满足问题(CSP),代数决策图(ADD),弧一致性(AC)

Abstract: 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 constrains in one time,not as the traditional algorithm which can only deal with one value pair in a constraint per step.Fistly,CSP was described as pseudo-Boolean function by 01coding and represented by ADD.Secondly,based on traditional arc consistency algorithm,the ADD operations intersection,union and abstraction were used to achieve constraint propagation and variable domain filtering.Finally,the symbolic algebraic decision diagram (ADD) algorithm for arc consistency was embedded in BT search algorithm to solve the CSP.The result of experimental simulation to solve some problems 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+BJ,meanwhile the performance is better than algorithms BT+MPAC and BT+MPAC* which is based on AC preprocess realized by traditional data structure in CSP solving.

Key words: Constraint satisfaction problem(CSP),Algebraic decision diagram(ADD),Arc consistency(AC)

王腾飞,徐周波,古天龙. 弧一致性符号ADD算法及在CSP求解中的应用[J]. 计算机科学, 2013, 40(12): 243-247. https://doi.org/

WANG Teng-fei,XU Zhou-bo and GU Tian-long. Symbolic ADD Algorithms for Arc Consistency and Application in Constraint Satisfaction Problem Solving[J]. Computer Science, 2013, 40(12): 243-247. https://doi.org/

参考文献

[1] Marriot K,Stuckey P．Programming with constraints[M]．Cambridge:MIT Press,1998
[2] Apt K．Principle of Constraint Programming[M]．Cambridge:Cambridge Press,2003
[3] Prosser P．Hybrid algorithms for the constraint satisfactionproblems[J]．Computational Intelligence,1993,9(3):268-299
[4] Ginsberg M L．Dynamic backtracking[J]．Artificial Intelligence,1993,1:25-46
[5] Larrosa J,Schiex T．Solving Weighted CSP by Maintaining Arc Consistency[J]．Artificial Intelligence,2004,159(1/2):1-26
[6] Mackworth A K．Consistency in networks of relations[J]．Artificial Intelligence,1977,8(1):99-118
[7] Christian B,Charles R J．Refining the basic constraint propagation algorithm[C]∥Proceedings of the 17th International Joint Conference on Artificial Intelligence．Seattle WA:Morgan Kaufmann,2001:309-315
[8] Mohr R,Henderson T C．Arc and path consistency revised[J]．Artificial Intelligence,1986,28(2):225-233
[9] 刘春晖．基于约束传播的约束求解方法研究[D]．长春:吉林大学,2008
[10] 古天龙,徐周波.有序二叉决策图及应用[M].北京:科学出版社,2009
[11] Bryant R E．Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams[J]．ACM Computing Surveys,1992,24(3):293-318
[12] Bachar R I,Frohm E A,Gaona C M,et al．Algebraic Decision Diagrams and Their Applications[J]．Formal Methods in Systems Design,1997,10(2/3):171-206
[13] Hachtel G D,Somenzi F．A Symbolic Algorithm for Maximum Flow in 0-1Networks[J]．Formal Methods in System Design,1997,10(2/3):207-219
[14] 徐周波,古天龙,赵岭忠.网络最大流问题的一种新的符号ADD求解算法[J].通信学报,2005,26(2):1-8
[15] 徐周波,古天龙,常亮.加权约束满足问题的符号ADD求解算法[J].模式识别与人工智能,2011,24(1):14-21
[16] Larrosa J．Node and Arc Consistency in Weighted CSP[C]∥Proc．of the AAAI-02．Alberta,Canada,Aug.2002:48-53
[17] 孙吉贵,朱兴军,张永刚,等．一种基于预处理的约束满足问题求解算法[J]．计算机学报,2008,1(6):919-926

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed