一种基于图分割的动态回溯算法

动态回溯算法在进行回溯时保留所有已赋值变量的值，从而可能与后面赋值的变量产生冲突，其在解决不具有明显子问题结构的约束满足问题时效率较低。为此，将图分割技术应用于动态回溯，通过图分割将变量分为若干集合，当发生回溯时，不保留全部变量的值，舍弃那些与引起冲突的变量在同一集合变量中的值。实验结果表明，该算法在求解没有明显子问题结构的约束满足问题时具有较高的效率。

A Dynamic Backtracking Algorithm Based on Graph Partitioning

The dynamic backtracking algorithm keeps its assigned value for each variable when it backtracks. However, it becomes inefficient when it comes to the constraint satisfaction problems that do not consist of sub problems. To solve the problem, this paper applies graph partitioning to dynamic backtracking. The main idea is to divide all the variables into several sets using graph partitioning. When it back tracks, it gives up the values of the variables that are in the same set with the culprit variable, instead of keeping all the values. Experimental results show that the new method has higher efficiency on the random satisfaction problems.