基于改进树分解技术的约束满足问题的符号ADD求解算法

摘要：

为提高大规模约束满足问题(CSP)的求解效率,提出了基于改进树分解技术的符号ADD求解算法.通过CSP的ADD描述,将树分解技术的树聚类与符号ADD结合,以提高算法的求解效率.采用改进最大基数(MC)的变量选择法,提高构造弦图的效率,引导团的构造以及连接树的生成.对大量随机生成的测试用例进行实验仿真,结果表明,基于改进树分解技术的符号ADD求解算法求解效率优于BT-FC-ADD算法和BT-ADD算法.

关键词：约束满足问题、树分解、代数决策图、符号算法

所属期刊栏目：37

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金61262030,61572146,61363030;广西自然科学基金2014GXNSFAA118354

在线出版日期：2017-06-15（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：127-133