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

Optimized coarse-grained arc-consistency algorithm for maintaining the uniqueness of arc

作　　者：李颖[1] 杨罡 李占山[1] LI Ying;YANG Gang;LI Zhanshan(College of Computer Science and Technology,Jilin University,Changchun 130012,China)

机构地区：[1]吉林大学计算机科学与技术学院,吉林长春130012

出　　处：《哈尔滨工程大学学报》2018年第4期744-750,共7页Journal of Harbin Engineering University

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

摘　　要：针对人工智能领域中广泛应用的约束满足问题,本文分析了约束满足问题的粗粒度维持弧相容求解算法在弧相卷(arc corsistency,AC)执行过程中对于弧存在冗余的放回操作,并证明了这类放回是冗余的。同时提出一种改进方法 AC_AO,避免这类冗余的弧放回操作,从而保证了弧的唯一性。改进后框架可用于改进所有的粗粒度弧相容算法。实验结果表明,经过AC_AO改进后的算法最多可以少检查77%的弧,最多可以减少30%的CPU求解时间。这将大大减少修正函数的调用次数,从而提高AC的执行效率,应用在维持弧相容算法求解的过程中提高效率是非常有意义的。To address the widely encountered problem of constraint satisfaction in artificial intelligence,this paper analyzed the putback operation of the coarseness maintenance arc-consistency algorithm to avoid the drawbacks of redundant checks for arcs while implementing the AC algorithm and verified that these checks are redundant.An improved algorithm,AC_AO,was proposed to avoid the drawbacks of these redundant checks to ensure the uniqueness of the arc and improve coarse-grained arc-consistency algorithms.The experimental results reveal that AC_AO can reduce the arc checking quantity by 77%and reduce the CPU computation time up to 30%.This improvement will greatly reduce the frequency of modifications and significantly increase the efficiency of AC algorithm execution.

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

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]