桂林电子科技大学学报2017，Vol.37Issue(2)：127-133,7.
基于改进树分解技术的约束满足问题的符号ADD求解算法
Symbolic ADD algorithm for constraint satisfaction problem based on improved tree decomposition
摘要
Abstract
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.关键词
约束满足问题/树分解/代数决策图/符号算法Key words
constraint satisfaction problem/tree decomposition/algebraic decision diagram/symbolic algorithm分类
信息技术与安全科学引用本文复制引用
王敏,徐周波..基于改进树分解技术的约束满足问题的符号ADD求解算法[J].桂林电子科技大学学报,2017,37(2):127-133,7.基金项目
国家自然科学基金(61262030,61572146,61363030) （61262030,61572146,61363030）
广西自然科学基金(2014GXNSFAA118354) （2014GXNSFAA118354）
