| 摘要: |
| 广义弧相容是求解约束满足问题应用最广泛的相容性，MDDc，STR2和STR3是表约束上维持广义弧相容应用较多的算法，其中，MDDc基于对约束压缩表示的思想，将表约束表示成多元决策图，对各个元组之间存在较多交叠部分的约束具有很好的压缩效果；STR3同STR2一样，基于动态维持有效元组的思想，当元组集规模缩减较慢时，STR3维持广义弧相容的效率高于STR2.通过深入分析发现，MDDc中查找节点的有效出边和STR3中检测并删除无效元组是耗时最多的操作.分别对MDDc和STR3提出一种自适应查找有效出边和检测删除无效元组的方法AdaptiveMDDc和AdaptiveSTR，对于同一操作，可以根据回溯搜索不同阶段的局势，自适应地选择代价最小的实现方法.得益于较低的判断代价以及回溯搜索不同阶段采用不同方法的效率差异，AdaptiveMDDc和AdaptiveSTR相比，原算法速度提升显著，其中，AdaptiveSTR在一些问题上相比STR3提速3倍以上. |
| 关键词: 约束满足问题(CSP) 广义弧相容(GAC) 自适应 多元决策图(MDD) AdaptiveMDDc AdaptiveSTR |
| DOI：10.13328/j.cnki.jos.005242 |
| 分类号: |
| 基金项目:国家自然科学基金（61272208，61373052）；吉林省自然科学基金（20140101200JC） |
|
| Optimizing MDDc and STR3 for Solving Constraint Satisfaction Problem |
|
YANG Ming-Qi1,2, LI Zhan-Shan1,2, LI Zhe1,2
|
|
1.College of Computer Science and Technology, Jilin University, Changchun 130012, China;2.Key Laboratory of Symbolic Computation and Knowledge Engineering(Jilin University), Ministry of Education, Changchun 130012, China
|
| Abstract: |
| Generalized arc consistency(GAC) is the most widely studied consistency for solving constraint satisfaction problem(CSP). MDDc, STR2 and STR3 are widely used algorithms for enforcing GAC on table constraints, where MDDc represents constraints in a compression method which converts a table constraint into a multi-valued diagram(MDD). When a MDD has many identical parts, the compression ratio is high and MDDc outperforms others. STR3, similar to STR2, dynamically reduces the table size by maintaining a table of only valid tuples. When valid tuples decrease slowly, STR3 outperforms STR2. Considering that finding valid outgoing edges of MDD nodes and checking and deleting invalid tuples in dual table are the most time-consuming operations in MDDc and STR3, this study proposes AdaptiveMDDc and AdaptiveSTR respectively for MDDc and STR3 to perform the above two operations in an adaptive way so that the lowest cost strategy in different backtrack search stages is always employed. Benefiting from lower cost of strategy and significant performance difference of each strategy during different backtrack search stages, AdaptiveMDDc and AdaptiveSTR have better performance compared to the original methods, and ApaptiveSTR is over three times faster than STR3 in some instances. |
| Key words: constraint satisfaction problem(CSP) generalize arc consistency(GAC) adaptability multi-valued diagram(MDD) AdaptiveMDDc AdaptiveSTR |
