一个基于最小冲突修补的动态约束满足求解算法

被引：13

作者：

孙吉贵

高健

张永刚

机构：

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

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

来源：

计算机研究与发展 | 2007年 / 12期

关键词：

最小冲突修补; 动态约束满足问题; 禁忌搜索; 分支定界; 解重用;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

约束满足问题是人工智能中一个重要的研究方向,近年来,对动态变化的约束满足问题的研究逐渐成为该领域的热点.在目前该领域最流行的LC算法基础上,引入禁忌搜索策略,提出了一个基于最小冲突修补的算法Tabu-LC.算法在每次冲突调整时将所有冲突变量看成一个整体,并采用分支定界搜索策略求解冲突变量组成的子问题,极大地提高了求解效率.同时,在约束求解系统"明月1.0"架构下给出了算法的具体实现,并针对大量随机问题进行了对比实验.结果表明,Tabu-LC算法在求解效率和解的质量上都明显优于LC算法.

引用

页码：2078 / 2084

页数：7

共 7 条

[1] 最大度二元约束满足问题粒子群算法 [J].

杨轻云 ;

孙吉贵 ;

张居阳 .

计算机研究与发展, 2006, (03) :436-441

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

孙吉贵 ;

景沈艳 .

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

[3]

Constraint Solving in Uncertain and Dynamic Environments: A Survey[J] . Gérard Verfaillie,Narendra Jussien.Constraints . 2005 (3)

[4]

Fuzzy rr DFCSP and planning[J] . Ian Miguel,Qiang Shen.Artificial Intelligence . 2003 (1)

[5] Local search with constraint propagation and conflict-based heuristics [J].

Jussien, N ;

Lhomme, O .

ARTIFICIAL INTELLIGENCE, 2002, 139 (01) :21-45

[6]

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

[7] Dynamic flexible constraint satisfaction [J].

Miguel, I ;

Shen, Q .

APPLIED INTELLIGENCE, 2000, 13 (03) :231-245

← 1 →