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

A Two-way Propagation Strategy for Maintaining Constraint Network Consistency

约束满足问题是经典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.