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

Symbolic ADD Algorithms for Weighted Constraint Satisfaction Problem

作　　者：徐周波[1,2] 古天龙[2] 常亮[2] 

机构地区：[1]西安电子科技大学电子工程学院,西安710071 [2]桂林电子科技大学计算机科学与工程学院,桂林541004

出　　处：《模式识别与人工智能》2011年第1期14-21,共8页Pattern Recognition and Artificial Intelligence

基　　金：国家自然科学基金(No.60963010;60903079);广西自然科学基金(No.0832006Z)资助项目

摘　　要：加权约束满足问题(WCSP)是一类软约束满足问题.给出WCSP的代数决策图(ADD)描述,以及基于ADD的两种符号求解算法.首先,通过对变量和变量域值的二进制编码,给出软约束图的ADD表示.其次,将分支定界搜索算法与桶消元算法及符号ADD技术相结合,在静态变量序下,利用结点一致性预处理技术,对WCSP问题进行符号ADD求解.通过引入有向弧一致性计数技术提高符号ADD算法的搜索下界,对符号ADD求解算法作了改进.最后,对大量随机生成的测试用例进行实验分析.结果表明,文中算法在性能上明显优于带有存在有向弧一致性或结点一致性预处理技术的具有前向检查功能的深度优先分支定界搜索算法.The weighted constraint satisfaction problem （WCSP） is a kind of soft constraint satisfaction problems with many practical applications. An algebraic decision diagram （ADD） based scheme is proposed to solve WCSP efficiently. Firstly, the soft constraint network is represented as ADDs so that the WCSP can be formulated symbolically and manipulated implicitly. Secondly, the symbolic ADD algorithm is presented, where the branch and bound algorithm is integrated with bucket elimination algorithm symbolically. And the static variable orderings and the node consistency during search are used. To improve the lower bound of the symbolic ADD algorithm, the counting technique of directional arc consistency is adopted, and thus the symbolic ADD algorithm is improved. Finally, experiments on random problems are implemented, and the results show that the proposed algorithms outperform the depth-first branch and bound algorithms enhanced with a look-ahead process and a preprocessing step of either existential directional arc consistency or the node consistency.

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]