一种基于环切割的约束满足问题求解算法

摘要：

该文首先给出一种无环约束满足问题的无回溯搜索算法Tree_Search,然后将环切割思想嵌入到目前最流行的MAC3rm算法中,给出一种新算法CCS.CCS将原同溯搜索过程分为两部分:第1部分通过回溯搜索求解环切割集中变量,将原问题化简成一个满足弧相容的无环问题；第2部分通过无回溯的Tree_Search算法求解化简后的无环问题,改进了MAC3rm算法.证明了MAC3rm算法在环切割集上求得的局部解一定可以扩展为一个全局解,并且如果原问题无解,则MAC3rm算法在环切割集上找不到局部解.实验结果显示,CCS的效率在大多数情况下高于MAC3rm.在求解随机问题相变阶段的测试用例时,CCS的效率最高可以达到MAC3rm的140倍.Benchmark中几组问题的测试结果显示,CCS在整体上效率高于MAC,最高可以达到MAC3rm的100倍以上.

关键词：弧相容、无回溯搜索、环切割、MAC3 rm

所属期刊栏目：34

分类号：TP18(自动化基础理论)

资助基金：国家自然科学基金60773097,60873148,60973089;吉林省自然科学资金项目20060532、20071106、20080107

在线出版日期：2012-01-14（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：1528-1535