作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2020, Vol. 46 ›› Issue (4): 46-52. doi: 10.19678/j.issn.1000-3428.0054075

• 人工智能与模式识别 • 上一篇    下一篇

一种维持约束网络相容性的双向传播策略

李晓, 司怀伟, 郭宗沂, 李东雨, 谭国真   

  1. 大连理工大学 电子信息与电气工程学部, 辽宁 大连 116024
  • 收稿日期:2019-03-04 修回日期:2019-04-16 出版日期:2020-04-15 发布日期:2020-04-07
  • 作者简介:李晓(1994-),女,硕士研究生,主研方向为人工智能、约束处理、多智能体协同;司怀伟,博士研究生;郭宗沂、李东雨,硕士研究生;谭国真,教授、博士生导师。
  • 基金资助:
    国家自然科学基金青年基金(61602084);国家自然科学基金辽宁省联合基金重点支持项目(U1808206);辽宁省博士科研启动基金(201601041)。

A Two-way Propagation Strategy for Maintaining Constraint Network Consistency

LI Xiao, SI Huaiwei, GUO Zongyi, LI Dongyu, TAN Guozhen   

  1. Department of Electronic Information and Electrical Engineering, Dalian University of Technology, Dalian, Liaoning 116024, China
  • Received:2019-03-04 Revised:2019-04-16 Online:2020-04-15 Published:2020-04-07

摘要: 约束满足问题是经典NP-hard问题,其基本算法是递归形式的回溯算法和弧一致性算法。将弧相容与回溯搜索结合,可以有效降低解空间大小。针对弧相容的维持问题,提出一种新的基于时序计数的传播方案,用于增量更新约束子网。将accumulateRevision和pushRevison作为双向修订的主要方法,以减少修订次数和域过滤变量的数量。实验结果表明,与经典的基于关系的方案和基于变量的传播方案相比,该方案的整体求解速度明显提高,且具有较少的修订时间。

关键词: 人工智能, 约束网络, 弧相容, 启发式传播, 传播策略

Abstract: The constraint satisfiability problem is a classic NP-hard problem,its basic algorithms are recursive backtracking and arc consistency algorithms.The combination of Arc Consistency(AC) and backtracking search can effectively reduce the size of solution space.Aiming at the maintaining problem,this paper proposes a new propagation scheme based on temporal counting to incrementally update the constraint subnet and use accumulateRevision and pushRevisionas the main process of two-way revision in order to reduce revision times and the numbers of domain filtering variables.Experimental results show that compared with the classic relationship-based scheme and variable-based propagation scheme,the overall solution speed of this scheme is significantly improved,and it has less time of revision.

Key words: artificial intelligence, constraint network, Arc Consistency(AC), heuristic propagation, propagation strategy

中图分类号: