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

• 作者: 古天龙 常亮 徐周波
• 来源期刊: 模式识别与人工智能
• 学科: 工学
• 关键词: 加权约束满足问题(WCSP) 分支定界 桶消元 符号算法 代数决策图(ADD)
• 年，卷（期）: 2011,（1）
• 所属期刊栏目: 论文与报告
• 页码范围: 14-21
• 分类号: TP301
• 字数: 6780字
• 语种: 中文
• DOI: 10.3969/j.issn.1003-6059.2011.01.002

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	古天龙	桂林电子科技大学计算机科学与工程学院	207	1546	18.0	30.0
2	常亮	桂林电子科技大学计算机科学与工程学院	77	450	12.0	17.0
3	徐周波	西安电子科技大学电子工程学院	53	284	8.0	15.0