改进求解约束满足问题粗粒度弧相容算法

摘要：

约束满足问题在人工智能领域有着广泛的应用.研究了约束满足问题的粗粒度维持弧相容求解算法,发现在求解过程中,对于指向已赋值变量的弧存在无效的修正检查,证明了这类修正检查是冗余的.提出一种方法避免这类冗余的修正检查,给出改进后的粗粒度弧相容算法的基本框架AC3_frame_ARR,该改进框架可用于改进所有粗粒度弧相容算法.实验结果表明,经过AC3 frame ARR改进后的算法最多可以节省80％的修正检查次数和40％的求解耗时.

关键词：约束满足问题、维持弧相容、粗粒度算法、修正检查

所属期刊栏目：23

分类号：TP18(自动化基础理论)

资助基金：国家自然科学基金60773097,60873148,60973089;吉林省自然科学基金201101039,20071106,20080107;国家教育部博士点专项基金20100061110031

在线出版日期：2012-09-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：1816-1823