| 《计算机学报》文章摘要 全文下载 | |
| 文章题目 | 一种基于环切割的约束满足问题求解算法 |
| 作者 | 李占山 李宏博 张永刚 王孜文 |
| 作者单位 | (吉林大学符号计算与知识工程教育部重点实验室 长春 130012) (吉林大学计算机科学与技术学院 长春 130012) |
| 发表年份 | 2011 |
| 发表月份 | 8期(1528—1535) |
| 文章摘要 | 摘要 该文首先给出一种无环约束满足问题的无回溯搜索算法Tree_Search，然后将环切割思想嵌入到目前最流行的MAC3rm算法中，给出一种新算法CCS.CCS将原回溯搜索过程分为两部分：第1部分通过回溯搜索求解环切割集中变量，将原问题化简成一个满足弧相容的无环问题；第2部分通过无回溯的Tree_Search算法求解化简后的无环问题，改进了MAC3rm算法.证明了MAC3rm算法在环切割集上求得的局部解一定可以扩展为一个全局解，并且如果原问题无解，则MAC3rm算法在环切割集上找不到局部解.实验结果显示，CCS的效率在大多数情况下高于MAC3rm.在求解随机问题相变阶段的测试用例时，CCS的效率最高可以达到MAC3rm的140倍.Benchmark中几组问题的测试结果显示，CCS在整体上效率高于MAC，最高可以达到MAC3rm的100倍以上. 关键词 弧相容；无回溯搜索；环切割；MAC3rm 中图法分类号 TP18 DOI号: 10.3724/SP.J.1016.2011.01528 |