| 一种基于环切割的约束满足问题求解算法 |
| 李占山[1,2] 李宏博[1,2] 张永刚[1,2] 王孜文[1,2] |
| 关键词：弧相容 无回溯搜索 环切割 MAC3rm |
| 主要内容：该文首先给出一种无环约束满足问题的无回溯搜索算法Tree_Search，然后将环切割思想嵌入到目前最流行的MAC3rm算法中，给出一种新算法CCS．CCS将原回溯搜索过程分为两部分：第1部分通过回溯搜索求解环切割集中变量，将原问题化简成一个满足弧相容的无环问题；第2部分通过无回溯的Tree_Search算法求解化简后的无环问题，改进了MAC3rm算法．证明了MAC3rm算法在环切割集上求得的局部解一定可以扩展为一个全局解，并且如果原问题无解，则MAC3rm算法在环切割集上找不到局部解．实验结果显示，CCS的效率在大多数情况下高于MAC3rm．在求解随机问题相变阶段的测试用例时，CCS的效率最高可以达到MAC3rm的140倍．Benchmark中几组问题的测试结果显示，CCS在整体上效率高于MAC，最高可以达到MAC3rm的100倍以上． |
| 《计算机学报》 2011,34(8).-1528-1535 |
| 全文下载请进入http://hightech.stlib.cn/tpi_1/sysasp/include/index.asp |
微信公众号