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

作     者：李颖 杨罡 李占山 LI Ying;YANG Gang;LI Zhanshan

作者机构：吉林大学计算机科学与技术学院吉林长春130012 

出 版 物：《哈尔滨工程大学学报》 (Journal of Harbin Engineering University)

年 卷 期：2018年第39卷第4期

页      面：744-750页

核心收录：

学科分类：08[工学] 081104[工学-模式识别与智能系统] 0817[工学-化学工程与技术] 0807[工学-动力工程及工程热物理] 0827[工学-核科学与技术] 0802[工学-机械工程] 0703[理学-化学] 0825[工学-航空宇航科学与技术] 0811[工学-控制科学与工程] 0801[工学-力学（可授工学、理学学位）] 

基　　金：国家自然科学基金项目(61272208 61373052) 吉林省科技计划项目(20180101043JC) 

主　　题：人工智能 约束满足问题 维持弧相容 粗粒度算法 哈希算法 唯一 预处理 一致性 冗余 回溯 

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