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

• 作者: 李占山 李宏博 王涛
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 约束满足问题 维持弧相容 粗粒度算法 修正检查
• 年，卷（期）: 2012,（7）
• 所属期刊栏目: 模式识别与人工智能
• 页码范围: 1816-1823
• 分类号: TP18
• 字数: 6410字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2012.04129

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李占山	吉林大学计算机科学与技术学院	43	234	7.0	13.0
5	王涛	长春工业大学计算机科学与工程学院	55	196	7.0	12.0
6	李宏博	吉林大学计算机科学与技术学院	9	39	4.0	6.0