原创 回溯法的一般方法

    在用回溯法求解有关问题的过程中，一般是一边建树，一边遍历该树。在回溯法中我们一般采用非递归方法。下面，我们给出回溯法的非递归算法的一般流程：

    在用回溯法求解问题，也即在遍历状态空间树的过程中，如果采用非递归方法，则我们一般要用到栈的数据结构。这时，不仅可以用栈来表示正在遍历的树的结点，而且可以很方便地表示建立孩子结点和回溯过程。

问题的解空间 

问题的解向量：回溯法希望一个问题的解能够表示成一个n元式(x1,x2,…,xn)的形式。

显约束：对分量xi的取值限定。

隐约束：为满足问题的解而对不同分量之间施加的约束。

解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。

注意：同一个问题可以有多种表示，有些表示方法更简单，所需表示的状态空间更小（存储量少，搜索方法简单）。

例子：回溯的一般方法，代码如下：

void BackTrack(n){
//这是对回溯法控制流程的抽象描述。每个解都在X(1:n)中生成，一个解
//一经确定就立即输出。在X(l),…,X(k-l)已被选定的情况下，T(X(l), …,
//X(k-1))给出X(k)的所有可能的取值。限界函数B(X(l),…,X(k))
//判断哪些元素X(k)满足隐式约束条件。
int k，n ；int X[n]；
k=1；
while(k>0) {
if(还剩未检验的X(k)使得X(k)∈T(X[l],…,X[k-1] and
B(X[1],…,X[k])=True) {
if((X[1],…,X[k])是一条已抵达一答案结点的路径) {
print(X[1],…,X[k]) }；//if
++k； //考虑下一个集合
else {--k；} //回溯到先前的集合
}；//if
}；
}// BackTrack

注意：集合T()将提供作为解向量的第一个分量X(1)的所有可能值，解向量则取使限界函数B1(X(1))为真的那些X(1)的值。还要注意的是，这些元素是如何按深度优先方式生成的。随着k值的增加，解向量的各分量不断生成，直到找到一个解或者不再剩有未经检验的X(k)为止。当k值减少时，算法必须重新开始生成那些可能在以前剩下而没经检验的元素。因此，还需拟制一个子算法，使它按某种次序来生成这些元素 X(k)。如果只想要一个解，则可在print后面设置一条 return语句。

例如：递归回溯算法，代码如下：

void RBackTrack(k) {
//此算法是对回溯法抽象地递归描述。进入算法时，解向量
// X(1:n)的前k-1个分量X(1)，…，X(k-1)已赋值
int n，X[n]； //定义成全局变量
for(对每个X[k]|X[k]∈T(X[1],…,X[k-1]) and
B(X[1],…,X[k]=true) {
if(X[1],…,X[k])是一条已抵达一答案结点的路径)
{print(X[1],…,X[k])；}//if
RBackTrack(k+1)；
}；
}//RBackTrack

　　解向量(x1,…,xn)作为一个全程数组X(1:n)来处理。该元组的第k个位置上满足B的所有元素逐个被生成，并被连接到当前向量(X(l),…,X(k-1))，每次X(k)都要附带一种检查，即判断一个解是否已被找到。因此，这个算法被递归调用。当退出for循环时，不再剩有X(k)的值，从而结束此层递归并继续上次未完成的调用。要指出的是，当k大于n时，T(X(1),…,X(k-1))返回一个空集，因此，根本不进入for循环。还要指出的是，这个程序输出所有的解，而且组成解的元组的大小是可变的。如果只想要一个解，则可加上一个标志作为一个参数，以指明首次成功的情况。

效率估计
上面所给出的两个回溯程序的效率主要取决于以下四种因素：
① 生成下一个X(k)的时间；
② 满足显式约束条件的X(k)的数目；
③ 限界函数Bi的计算时间；
④ 对于所有的 i，满足 Bi的X(k)的数目。

例如，估计回溯法的效率，算法如下：

void Estimate() {
//程序沿着状态空间树中一条随机路径产生该树中不受限界结点的估计数
m = l；r = 1；k = 1；
while(1) {
T[k]={X[k]|X[k]∈T(X[1],…,X[k-1]) and Bk(X[1],…,X[k])}
if(Size(T[k])=0) break；
r* = Size(T[k])；
m += r；
X[k]=Choose(T[k])；
++k；
}；//while
return m；
}//Estimate

　　对算法Estimate稍加修改就可得到更准确的结点估计数。这只需增加一个for循环语句，选取数条不同的随机路径(一般可取20条)，在求出沿每条路径的估计值后，取平均值即得。