最大受限路径相容约束传播算法的研究进展

Research Progress on Max Restricted Path Consistency Constraint Propagation Algorithms

约束传播技术对于约束满足问题的求解性能至关重要。约束传播技术在一个预处理过程中能彻底地移除一些局部不相容值,或者在搜索期间高效地剪枝搜索树。最大受限路径相容算法(max Restricted Path Consistency,maxRPC)是最近提出的一种强相容性约束传播算法,它能够删除更多不相容值,在解决复杂问题中取得了很好的效果。文中对弧相容算法AC和最大受限路径相容算法maxRPC的相关算法AC3,AC3rm,maxRPC1,maxRPC2,maxRPCrm,maxRPC3等及其相关变体分别进行介绍和比较。在Mistral求解器上的实验测试结果验证了各种算法的性能。

Constrained propagation technology is critical to the performance of constraint satisfaction problems.Constrained propagation technology completely removes some local inconsistency values during apreprocessing process,or efficiently pruning the search tree during the search.The max restricted path consistency algorithm（maxRPC）is a strong consistency constraint propagation algorithm proposed recently,which can remove more inconsistent values,and achieves good results in solving complex problems.In this paper,some algorithms,such as AC3,AC3 rm,maxRPC1,maxRPC2,maxRPCrm,maxRPC3 and other related algorithms which are related to the arc consistency algorithm AC and max restricted path consistency algorithm maxRPC,were introduced respectively and compared with each other.The performance of the proposed algorithm is verified by the experimental results on the mistral solver.