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

A Two-way Propagation Strategy for Maintaining Constraint Network Consistency

作　　者：李晓 司怀伟 郭宗沂 李东雨 谭国真 LI Xiao;SI Huaiwei;GUO Zongyi;LI Dongyu;TAN Guozhen(Department of Electronic Information and Electrical Engineering,Dalian University of Technology,Dalian,Liaoning 116024,China)

机构地区：[1]大连理工大学电子信息与电气工程学部,辽宁大连116024

出　　处：《计算机工程》2020年第4期46-52,共7页Computer Engineering

基　　金：国家自然科学基金青年基金(61602084);国家自然科学基金辽宁省联合基金重点支持项目(U1808206);辽宁省博士科研启动基金(201601041)。

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

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

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