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

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

针对人工智能领域中广泛应用的约束满足问题,本文分析了约束满足问题的粗粒度维持弧相容求解算法在弧相卷(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.