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

Symbolic ADD Algorithms for Weighted Constraint Satisfaction Problem

加权约束满足问题(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.