摘要
该文首先给出一种无环约束满足问题的无回溯搜索算法Tree_Search,然后将环切割思想嵌入到目前最流行的MAC3 rm算法中,给出一种新算法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 sepa- rates 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 has improved MAC3rm. It is proved that the partial solution which is found by MAC3rm can be extended to a global solution and MAC3rm can not find a partial solution on the cycle_cut set if the global solution does not exist. The experiments show that CCS is more efficient than MAC3rm. While solving the random CSPs which are at the phase transition, CCS can reach a maximum of 140 times more efficient than MAC3rm, and while solving some of the benchmarks, CCS can reach up to 100 times more efficient than MAC3rm.
出处
《计算机学报》
EI
CSCD
北大核心
2011年第8期1528-1535,共8页
Chinese Journal of Computers
基金
国家自然科学基金(60773097
60873148
60973089)
吉林省自然科学资金项目(20060532
20071106
20080107)资助
