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

摘要

为提高大规模约束满足问题(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 symbolic 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 decomposition symbol ADD algorithm is more efficiency than BT-FC-ADD and BT-ADD.