基于动态值启发式的约束满足求解算法

被引：2

作者：

王孜文 ^{[1
,2
]}

李占山 ^{[1
,2
]}

艾阳 ^{[1
,2
]}

李宏博 ^{[1
,2
]}

机构：

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

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

来源：

计算机集成制造系统 | 2011年 / 17卷 / 04期

关键词：

动态值启发式; 值排序; 约束满足问题; 弧相容技术; 启发式算法;

D O I：

10.13196/j.cims.2011.04.162.wangzw.015

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

为提高约束满足问题的求解效率,提出了一种基于动态值启发式的约束满足问题求解算法。该算法在求解过程中吸收了以往启发式算法的优点,充分利用了预处理和弧相容检查阶段的信息。不但加入了变量启发式,而且在实例化变量时,对所有值的优先级进行动态的改变,从而实现了动态值启发式。比较了静态值启发式和动态值启发式的效率,分析了该算法的优缺点。通过随机问题标准库用例测试表明,该算法比经典主流算法具有更好的效率优势。

引用

页码：832 / 837

页数：6

共 4 条

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

孙吉贵 ;

朱兴军 ;

张永刚 ;

李莹 .

计算机学报, 2008, (06) :919-926

[2] 最先失败原则的约束传播算法 [J].

孙吉贵 ;

朱兴军 ;

张永刚 ;

高健 .

小型微型计算机系统, 2008, (04) :678-681

[3]

Contradicting Conventional Wisdom in Constraint Satisfaction .2 Sabin,D.,Freuder,E. C. Proc. 11th ECAI . 1994

[4]

the "Handbook of Constraint Programming" .2 Peter van Beek. Elsevier . 2006

← 1 →