关键词: 约束满足问题, 相容性技术, 图分割, Singleton弧相容

Abstract:

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.

Key words: constraint satisfaction problem, consistency technique, graph partitioning, Singleton arc consistency