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

被引：7

作者：

李占山

李宏博

张永刚

王孜文

机构：

[1] 吉林大学符号计算与知识工程教育部重点实验室

[2] 吉林大学计算机科学与技术学院

来源：

计算机学报 | 2011年 / 34卷 / 08期

关键词：

弧相容; 无回溯搜索; 环切割; MAC3rm;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

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

引用

页码：1528 / 1535

页数：8

共 7 条

[1] 一种基于预处理技术的约束满足问题求解算法 [J].