摘要
为提高大规模约束满足问题(CSP)的求解效率,提出了基于改进树分解技术的符号ADD求解算法。通过CSP的ADD描述,将树分解技术的树聚类与符号ADD结合,以提高算法的求解效率。采用改进最大基数(MC)的变量选择法,提高构造弦图的效率,引导团的构造以及连接树的生成。对大量随机生成的测试用例进行实验仿真,结果表明,基于改进树分解技术的符号ADD求解算法求解效率优于BT-FC-ADD算法和BT-ADD算法。
In order to improve the solving efficiency of large scale of CSP algorithm, the improved tree decomposition symbol- ic ADD algorithm is proposed. An ADD description of CSP is introduced, then tree-clustering of tree decomposition method is combined with symbolic ADD algorithm to improve the solving efficiency. Through improving the maximum cardinality （MC） method of variable selection, the efficiency of constructing chordal graph is improved for the construction of clique and the generation of join-tree. Experiments on random problems are tested, and the results show that the improved tree decom- position symbol ADD algorithm is more efficiency than BT-FC-ADD and BT-ADD.
出处
《桂林电子科技大学学报》
2017年第2期127-133,共7页
Journal of Guilin University of Electronic Technology
基金
国家自然科学基金(61262030
61572146
61363030)
广西自然科学基金(2014GXNSFAA118354)
关键词
约束满足问题
树分解
代数决策图
符号算法
constraint satisfaction problem
tree decomposition
algebraic decision diagram
symbolic algorithm
