|
软件学报 2012
改进求解约束满足问题粗粒度弧相容算法DOI: 10.3724/SP.J.1001.2012.04129, PP. 1816-1823 Keywords: 约束满足问题,维持弧相容,粗粒度算法,修正检查 Abstract: 约束满足问题在人工智能领域有着广泛的应用.研究了约束满足问题的粗粒度维持弧相容求解算法,发现在求解过程中,对于指向已赋值变量的弧存在无效的修正检查,证明了这类修正检查是冗余的.提出一种方法避免这类冗余的修正检查,给出改进后的粗粒度弧相容算法的基本框架ac3_frame_arr,该改进框架可用于改进所有粗粒度弧相容算法.实验结果表明,经过ac3_frame_arr改进后的算法最多可以节省80%的修正检查次数和40%的求解耗时.
|