维持弧的唯一性优化粗粒度弧相容算法

• 作者: 李占山 李颖 杨罡
• 来源期刊: 哈尔滨工程大学学报
• 学科: 工学
• 关键词: 人工智能 约束满足问题 维持弧相容 粗粒度算法 哈希算法 唯一 预处理 一致性 冗余 回溯
• 年，卷（期）: 2018,（4）
• 页码范围: 744-750
• 页数: 7页
• 分类号: TP18
• 字数: 4356字
• 语种: 中文
• DOI: 10.11990/jheu.201610104

摘要

针对人工智能领域中广泛应用的约束满足问题,本文分析了约束满足问题的粗粒度维持弧相容求解算法在弧相卷(arc corsistency,AC)执行过程中对于弧存在冗余的放回操作,并证明了这类放回是冗余的.同时提出一种改进方法AC_AO,避免这类冗余的弧放回操作,从而保证了弧的唯一性.改进后框架可用于改进所有的粗粒度弧相容算法.实验结果表明,经过AC_AO改进后的算法最多可以少检查77%的弧,最多可以减少30%的CPU求解时间.这将大大减少修正函数的调用次数,从而提高AC的执行效率,应用在维持弧相容算法求解的过程中提高效率是非常有意义的.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李颖	吉林大学计算机科学与技术学院	79	451	12.0	18.0
2	李占山	吉林大学计算机科学与技术学院	43	234	7.0	13.0
3	杨罡	吉林大学计算机科学与技术学院	1	1	1.0	1.0