图分割在Singleton弧相容算法中的应用

Graph Partitioning Applied in Singleton Algorithm

基于原有SAC-MP算法,提出一种将图分割技术应用到SAC-MP算法中的一种新算法,该算法在执行时能充分利用图分割技术确定适当的k值,避免了由于k值的不确定带来的冗余操作和盲目性.实验结果表明,该算法在求解约束满足问题时效率较高.

We studied the SAC-MP algorithm and presented the idea of the application of graph partitioning technology in the SAC-MP algorithm. The proposed algorithm takes the full advantage of the graph partition technology to determine the value of k in the process of executing, so it can avoid the redundant operations and blindness caused by the uncertainty of the value of k. Thus the algorithm has a better efficiency in solving the constraint satisfaction problem. The result of our experiments shows that our method is very effective and can improve the efficiency of the algorithm.