弧相容算法性能比较

Performance Comparison of Arc Consistency Algorithms

为了化简约束满足问题的规模、有效地处理大规模难解问题,从求解算法的角度研究弧相容技术。分析讨论了8种弧相容算法各自的优势和特点。在“明月”约束求解平台上针对随机约束满足问题,对该系列弧相容算法的性能进行了测试。实验结果表明,无论是在搜索之前还是搜索过程中,AC-2001(AC-3.1)都比其他算法表现出更优异的性能。

In order to reduce CSPs （Constraint Satisfaction Problems ） to deal with large and hard problems effectively, we study arc consistency techniques from an algorithm point of view. We analysis and discuss each the advantages and characteristics of all the eight kinds of arc consistency algorithms. We test all the algorithms on random generate problems and examine their performance based on the ＂Mingyue＂ constraint solving platform. The results show that AC-2001 （ AC-3.1 ） is better than other algorithms on both before search and during search.