最先失败原则的约束传播算法

被引：7

作者：

孙吉贵

朱兴军

张永刚

高健

机构：

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

来源：

小型微型计算机系统 | 2008年 / 04期

关键词：

最先失败原则; 弧相容; 约束满足问题; 约束传播;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

约束满足问题是人工智能研究领域的重要问题.而弧相容算法是求解约束满足问题的重要工具.在弧相容算法中应用启发式规则已经证明是一种很有效的方式.本文提出一个基于最先失败原则的约束传播算法,该算法在搜索过程中更早地发现含有空域的变量并提前进行回溯,从而提高问题求解效率.同时,在"明月1.0"架构下实现了该算法,实验结果表明使用最先失败原则的弧相容算法要比原来的算法效率上提高了约40%.

引用

页码：678 / 681

页数：4

共 5 条

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

孙吉贵 ;

景沈艳 .

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

[2]

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

[3]

Contradicting conventional wisdom in constraint satisfaction. Sabin D,Freuder E C. Proceedings of the Eleventh European Conference on Artificial Intelligence（ECAI‘94） . 1994

[4]

Arc-consistency and arc-consistency again. Bessiere C. Artificial Intelligence . 1994

[5]

Foundations of constraint satisfaction. Tsang Edward. A-cademic Press Linited . 1993

← 1 →