全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

加权约束满足问题的符号ADD求解算法

, PP. 14-21

Keywords: 加权约束满足问题(WCSP),分支定界,桶消元,符号算法,代数决策图(ADD)

Full-Text   Cite this paper   Add to My Lib

Abstract:

加权约束满足问题(WCSP)是一类软约束满足问题。给出WCSP的代数决策图(ADD)描述,以及基于ADD的两种符号求解算法。首先,通过对变量和变量域值的二进制编码,给出软约束图的ADD表示。其次,将分支定界搜索算法与桶消元算法及符号ADD技术相结合,在静态变量序下,利用结点一致性预处理技术,对WCSP问题进行符号ADD求解。通过引入有向弧一致性计数技术提高符号ADD算法的搜索下界,对符号ADD求解算法作了改进。最后,对大量随机生成的测试用例进行实验分析。结果表明,文中算法在性能上明显优于带有存在有向弧一致性或结点一致性预处理技术的具有前向检查功能的深度优先分支定界搜索算法。

References

[1]  He Renjie, Tan Yuejin. Improved Depth-First Search Algorithm for Valued Constraint Satisfaction Problem. Journal of Systems Engineering, 2004, 19(5):512-516 (in Chinese) (贺仁杰,谭跃进.加权约束满足问题的改进深度优先搜索算法. 系统工程学报, 2004, 19(5): 512-516)
[2]  Larrosa J, Schiex T. Solving Weighted CSP by Maintaining Arc-Consistency. Artificial Intelligence, 2004, 159(1/2): 1-26
[3]  Dechter R. Bucket Elimination: A Unifying Framework for Reasoning. Artificial Intelligence, 1999, 113(1/2): 41-85
[4]  Larrosa J, Schiex T. In the Quest of the Best Form of Local Consistency for Weighted CSP // Proc of the 18th International Joint Conference on Artificial Intelligence. Acapulco, Mexico, 2003: 239-244
[5]  de Givry S, Zytnicki M, Heras F, et al. Existential Arc Consistency: Getting Closer to Full Arc Consistency in Weighted CSP // Proc of the 19th International Joint Conference on Artificial Intelligence. Edinburgh, Scotland, 2005: 84-89
[6]  Gu Tianlong, Xu Zhoubo. Ordered Binary Decision Diagram and Its Application. Beijing, China: Science Press, 2009 (in Chinese) (古天龙,徐周波.有序二叉决策图及应用.北京:科学出版社, 2009)
[7]  Bryant R E. Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams. ACM Computing Surverys, 1992, 24(3): 293-318
[8]  Bachar R I, Frohm E A, Gaona C M, et al, Algebraic Decision Diagrams and Their Applications. Formal Methods in Systems Design, 1997, 10(2/3): 171-206
[9]  Hachtel G D, Somenzi F. A Symbolic Algorithm for Maximum Flow in 0-1 Networks. Formal Methods in System Design, 1997, 10(2/3): 207-219
[10]  Xu Zhoubo, Gu Tianlong, Zhao Lingzhong. A Novel Symbolic ADD Algorithm for Maximum Flow in Networks. Journal on Communications, 2005, 26(2):1-8 (in Chinese) (徐周波,古天龙,赵岭忠.网络最大流问题的一种新的符号ADD求解算法.通信学报, 2005, 26(2): 1-8)
[11]  Chatalic P, Simon L. Multi-Resolution on Compressed Sets of Clauses // Proc of the 12th International Conference on Tools with Artificial Intelligence. Vancouver, Canada, 2000: 2-10
[12]  Pan Guoqiang, Vardi M Y. Symbolic Techniques in Satisfiability Solving. Journal of Automated Reasoning, 2005, 35(1/3): 25-50
[13]  Larrosa J, Meseguer P. Exploiting the Use of DAC in Max-CSP // Proc of the 2nd International Conference on Principle and Practice of Constraint Programming. Cambridge, USA, 1996: 308-322
[14]  Wallace R J. Directed Arc Consistency Preprocessing // Proc of the Workshop on Constraint Processing. Berlin, Germany: Springer-Verlag, 1995: 121-137

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133