一种基于环切割的约束满足问题求解算法
李占山;李宏博;张永刚;王孜文
【期刊名称】《计算机学报》 【年(卷),期】2011(034)008
【摘要】该文首先给出一种无环约束满足问题的无回溯搜索算法Tree_Search,然后将环切割思想嵌入到目前最流行的MAC3rm算法中,给出一种新算法CCS.CCS将原同溯搜索过程分为两部分:第1部分通过回溯搜索求解环切割集中变量,将原问题化简成一个满足弧相容的无环问题；第2部分通过无回溯的Tree_Search算法求解化简后的无环问题,改进了MAC3rm算法.证明了MAC3rm算法在环切割集上求得的局部解一定可以扩展为一个全局解,并且如果原问题无解,则MAC3rm算法在环切割集上找不到局部解.实验结果显示,CCS的效率在大多数情况下高于MAC3rm.在求解随机问题相变阶段的测试用例时,CCS的效率最高可以达到MAC3rm的140倍.Benchmark中几组问题的测试结果显示,CCS在整体上效率高于MAC,最高可以达到MAC3rm的100倍以上.%Firstly a backtrack-free algorithm Tree_Search is given to solve the cycle-free CSPs. Secondly, by embedding the cycle-cut idea in the MAC3rm algorithm which is the most popular solver for binary CSPs in recent years, the new algorithm, called CCS, is presented. CCS separates the backtracking procedure into two steps, the former step searches the partial solution for the variables in the cycle-cut set and simplifies the problem into a cycle-free problem that is arc consistency, and the latter step solves the rest variables by Tree_Search algorithm. As a result, CCS
一种基于环切割的约束满足问题求解算法
