%0 Journal Article
%T 加权约束满足问题的符号ADD求解算法
%A 徐周波
%A 古天龙
%A 常亮
%J 模式识别与人工智能
%P 14-21
%D 2011
%X 加权约束满足问题(WCSP)是一类软约束满足问题。给出WCSP的代数决策图(ADD)描述，以及基于ADD的两种符号求解算法。首先，通过对变量和变量域值的二进制编码，给出软约束图的ADD表示。其次，将分支定界搜索算法与桶消元算法及符号ADD技术相结合，在静态变量序下，利用结点一致性预处理技术，对WCSP问题进行符号ADD求解。通过引入有向弧一致性计数技术提高符号ADD算法的搜索下界，对符号ADD求解算法作了改进。最后，对大量随机生成的测试用例进行实验分析。结果表明，文中算法在性能上明显优于带有存在有向弧一致性或结点一致性预处理技术的具有前向检查功能的深度优先分支定界搜索算法。
%K 加权约束满足问题(WCSP)
%K 分支定界
%K 桶消元
%K 符号算法
%K 代数决策图(ADD)
%U http://manu12.magtech.com.cn/Jweb_prai/CN/abstract/abstract9310.shtml