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

被引：10

作者：

孙吉贵

朱兴军

张永刚

李莹

机构：

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

[2] 吉林大学计算机科学与技术学院长春吉林大学符号计算与知识工程教育部重点实验室

来源：

计算机学报 | 2008年 / 06期

关键词：

约束满足问题; 弧相容技术; singleton弧相容; pre-弧相容;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

相容性技术作为约束满足问题的一种有效求解技术,不论是在求解前的预处理过程中,还是在搜索过程中,都扮演着极为重要的角色.文中对预处理阶段的相容性技术进行改进和信息抽取,提出两种应用于搜索过程中的新算法Pre-AC和Pre-AC*,并嵌入到BT框架中,形成新的搜索算法BT+MPAC和BT+MPAC*,给出了其正确性证明,通过复杂性分析得到Pre-AC和Pre-AC*的时间复杂度分别是O(nd)和O(ed2),明显低于目前最流行的弧相容技术的时间复杂度O(ed3).实验测试结果表明:对于不同类别的用例,新算法的执行效率是弧相容维护算法的250倍.

引用

页码：919 / 926

页数：8

共 5 条

[1] 非二元约束满足问题求解 [J].

孙吉贵 ;

景沈艳 .

计算机学报, 2003, (12) :1746-1752

[2] An optimal coarse-grained arc consistency algorithm [J].

Bessière, C ;

Régin, JC ;

Yap, RHC ;

Zhang, YL .

ARTIFICIAL INTELLIGENCE, 2005, 165 (02) :165-185

[3]

Random Constraint Satisfaction: Flaws and Structure[J] . Ian P. Gent,Ewan Macintyre,Patrick Prosser,Barbara M. Smith,Toby Walsh.Constraints . 2001 (4)

[4]

Arc and path consistency revisited .2 Mohr R,henderson T C. Artificial Intelligence . 1986

[5]

Hybrid algorithms for the constraint satis-faction problems .2 Patrick Prosser. Computational Intelligence . 1993

← 1 →