维持弧的唯一性优化粗粒度弧相容算法 |
| |
引用本文: | 李颖,杨罡,李占山.维持弧的唯一性优化粗粒度弧相容算法[J].哈尔滨工程大学学报,2018(4). |
| |
作者姓名: | 李颖 杨罡 李占山 |
| |
作者单位: | 吉林大学计算机科学与技术学院; |
| |
摘 要: | 针对人工智能领域中广泛应用的约束满足问题,本文分析了约束满足问题的粗粒度维持弧相容求解算法在弧相卷(arc corsistency,AC)执行过程中对于弧存在冗余的放回操作,并证明了这类放回是冗余的。同时提出一种改进方法 AC_AO,避免这类冗余的弧放回操作,从而保证了弧的唯一性。改进后框架可用于改进所有的粗粒度弧相容算法。实验结果表明,经过AC_AO改进后的算法最多可以少检查77%的弧,最多可以减少30%的CPU求解时间。这将大大减少修正函数的调用次数,从而提高AC的执行效率,应用在维持弧相容算法求解的过程中提高效率是非常有意义的。
|
本文献已被 CNKI 等数据库收录! |
|