回溯法的效率分析.docx

回溯法概述
与穷举的“笨拙”搜索相比，回溯法则是一种“聪明”的求解效益更高的搜索法。
下面介绍回溯设计及其应用，体会回溯法相对于穷举的特点与优势。
回溯的概念
有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往使用回溯法。
回溯法是一种试探求解的方法：通过对问题的归纳分析，找出求解问题的一个线索，沿着这一线索往前试探，若试探成功，即得到解；若试探失败，就逐步往回退，换其他路线再往前试探。因此，回溯法可以形象地概括为“向前走，碰壁回头”。
回溯法的基本做法是试探搜索，是一种组织得井井有条的、能避免一些不必要搜索的穷举式搜索法。回溯法在问题的解空间树中，从根结点出发搜索解空间树，搜索至解空间树的任意一点，先判断该结点是否包含问题的解；如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其父结点回溯；否则，进入该子树，继续搜索。
从解的角度理解，回溯法将问题的候选解按某种顺序进行枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解。在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。倘若当前候选解除了不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。
与穷举法相比，回溯法的“聪明”之处在于能适时“回头”，若再往前走不可能得到解，就回溯，退一步另找线路，这样可省去大量的无效操作。因此，回溯与穷举相比，回溯更适宜于量比较大，候选解比较多的问题。
5.1.2 回溯描述
1．回溯的一般方法
下面简要阐述回溯的一般方法。
回溯求解的问题P，通常要能表达为：对于已知的由n元组(x1,x2,…,xn)组成的一个状态空间E={(x1,x2,…,xn)|xi∈si,i=1,2,…,n}，给定关于n元组中的一个分量的一个约束集D，要求E中满足D的全部约束条件的所有n元组。其中si是分量xi的定义域，且|si|有限，i=1,2,…,n。称E中满足D的全部约束条件的任一n元组为问题P的一个解。
解问题P的最朴素的方法就是穷举法，上面已经作了介绍，即对E中的所有n元组逐一地检验其是否满足D的全部约束，若满足，则为问题P的一个解。显然，其计算量是相当大的。
对于许多问题，所给定的约束集D具有完备性，即i元组(x1,x2,…,xi)满足D中仅涉及到x1,x2,…,xi的所有约束，意味着j(j及到x1,x2,…,xj的一个约束，n≥i＞j。因此，对于约束集D具有完备性的问题P，一旦检测断定某个j元组(x1,x2,…,xj)违反D中仅涉及x1,x2,…,xj的一个约束，就可以肯定，以(x1,x2,…,xj)为前缀的任何n元组(x1,x2,…,xj,xj+1,…,xn)都不会是问题P的解，因而就不必去搜索它们，即省略了对部分元素(xj+1,…,xn)的操作与测试。回溯法正是针对这类问题，利用这类问题的上述性质而提出来的比穷举法效率更高的算法。
2. 4皇后问题的回溯实施
为了具体说明回溯的实施过程，先看一个简单实例。
如何在4×4的方格棋盘上放置4个皇后，使它们互不攻击，即任意两个皇后不允许处在同一横排，同一纵列，也不允许处在同一与棋盘边框成45°角的斜线上。
图5-1所示为应用回溯的实施过程，其中方格中的×表示试图在该方格放置一个皇后,但由于受前面已放置的皇后的攻击而放弃的位置。

图5-1 4皇后问题回溯实施求解
图（a）为在第1行第1列放置一个皇后的初始状态。
图（b）中，第2个皇后不能放在第1、2列，因而放置在第3列上。
图（c）中，表示第3行的所有各列均不能放置皇后，则返回第2行，第2个皇后需后移。
图（d）中，第2个皇后后移到第4列，第3个皇后放置在第2列。
图（e）中，第4行的所有各列均不能放置皇后，则返回第3行；第3个皇后后移的所有位置均不能放置皇后，则返回第2行；第2个皇后已无位可退，则返回第1行；第1个皇后需后移。
图（f）中，第1个皇后后移至第2格。
图（g）中，第2个皇后不能放在第1，2，3列，因而放置在第4列上。
图（h）中，第3个皇后放在第1列；第4个皇后不能放置1，2列，于是放置在第3列。
这样经以上回溯，得到4皇后问题的一个解：2413。
继续以上的回溯探索，可得4皇后问题的另一个解：3142。
3．回溯算法框架描述
(1) 回溯描述
对于一般含参量m,n的搜索问题，回溯法框架描述如下：
输入正整数n,m,(n≥m)
i=1;a[i]=<元素初值>;
while (1)
{
for(g=1,k=i-1;k>=1;k--)
if( <约束条件1> ) g=0; // 检测约束条件,不满足则返回
if(g && <约束条件2>)
printf(a[1-m]); // 输出一个解
if(i;continue;}
while(a[i]==<回溯点> && i>1) i--; // 向前回溯
if(a[i]==n && i==1) break; // 退出循环，结束
else a[i]=a[i]+1;
}
具体求解问题的试探搜索范围与要求不同，在应用回溯设计时，需根据问题的具体实际确定数组元素的初值、取值点与回溯点，同时需把问题中的约束条件进行必要的分解，以适应上述回溯流程。
其中实施向前回溯的循环
while(a[i]==<回溯点> && i>1) i--;
是向前回溯一步，还是回溯两步或更多步，完全根据a[i]是否达到回溯点来确定。例如，回溯点是n，i=6，当a[6]=n时回溯到i=5；若a[5]=n时回溯到i=4；依此类推，到a[i]达到回溯点则停止。
图5-1所示的4皇后问题迭代回溯过程描述为：
n=4;i=1;a[i]=1;
while (1)
{
g=1;for(k=i-1;k>=1;k--)
if(a[i]=a[k] && abs(a[i]-a[k])=i-k)
g=0; // 检测约束条件,不满足则返回
if(g && i==4)
printf(a[1-4]); // 输出一个解
if(i1) i--; // 向前回溯
if(a[i]==n && i==1) break; // 退出循环结束
else a[i]=a[i]+1;
}
以上回溯体现在迭代式i=i-1，因而又称为迭代回溯。
此外，递归也能实现回溯。
（2） 递归回溯
int put(int k)
{ int i,j,u;
if( k<=问题规模 )
{ u=0;
if( <约束条件> )
u=1; // 当k时不可操作
if(u==0) // 当k时可操作
{ if(k==规模) // 若已满足规模，则打印出一个解
printf( <一个解> );
else put(k+1); // 调用 put(k+1)
}
}
}
在调用put(k)时，当检测约束条件知不可操作（记u=1），即再往前不可能得解，此时当然不可能输出解，也不调用put(k+1)，而是回溯，返回调用put(k)之处。这就是递归回溯的机理。
如果是主程序调用put(1)，最后返回到主程序调用put(1)的后续语句，完成递归。
图5.1所示的4皇后问题迭代回溯过程描述为：
int put(int k)
{ int i,j,u;
if(k<=4)
{ for(i=1;i<=4;i++) // 探索第k行从第1格开始放皇后
{ a[k]=i;
for(u=0,j=1;j<=k-1;j++)
if(a[k]==a[j] || abs(a[k]-a[j])==k-j )
u=1; // 若第k行第i格放不下,则置u=1
if(u==0) // 若第k行第i格可放,则检测是否满4行
{ if(k==4) // 若已放满到4行时，则打印出一个解
{ s++; printf(" ");
for (j=1;j<=4;j++)
printf("%d",a[j]);
}
else put(k+1); // 若没放满4行,则放下一行 put(k+1)
}
}
}
}
4. 回溯法的效益分析
应用回溯设计求解实际问题，由于解空间的结构差异，很难精确计算与估计回溯产生的结点数，因此回溯法的复杂度是分析回溯法效率时遇到的主要困难。回溯法产生的结点数通常只有解空间结点数的一小部分，这也是回溯法的计算效率大大高于穷举法的原因所在。
回溯求解过程实质上是一个遍历一棵“状态树”的过程，只是这棵树不是遍历前预先建立的。回溯算法在搜索过程中，只要所激活的状态结点满足终结条件，应该把它输出或保存。由于在回溯法求解问题时，一般要求输出问题的所有解，因此在得到结点后，同时也要进行回溯，以便得到问题的其他解，直至回溯到状态树的根且根的所有子结点均已被搜索过为止。
组织解空间便于算法在求解集时更易于搜索，典型的组织方法是图或树。一旦定义了解空间的组织方法，这个空间即可从开始结点进行搜索。
回溯法的时间通常取决于状态空间树上实际生成的那部分问题状态的数目。对于元组长度为n的问题，若其状态空间树中结点总数为n!，则回溯算法的最坏情形的时间复杂度可达O(p(n)n!)；若其状态空间树中结点总数为2n，则回溯算法的最坏情形的时间复杂度可达O(p(n)2n)，其中p(n)为n的多项式。
对于不同的实例，回溯法的计算时间有很大的差异。对于很多具有大n的求解实例，应用回溯法一般可在很短的时间内求得其解，可见回溯法不失为一种快速有效的算法。
对于某一具体实际问题的回溯求解，常通过计算实际生成结点数的方法即蒙特卡罗方法（Monte carlo）来评估其计算效率。蒙特卡罗方法的基本思想是在状态空间树上随机选择一条路径(x0,x1,…,xn-1)，设X是这一路径上部分向量(x0,x1,…,xk-1)的结点，如果在Ｘ处不受限制的子向量数是mk，则认为与X同一层的其他结点不受限制的子向量数也都是mk。也就是说，若不受限制的x0取值有m0个，则该层上有m0个结点；若不受限制的x1取值有m1个，则该层上有m0m1个结点；依此类推。由于认为在同一层上不受限制的结点数相同，因此，该路径上实际生成的结点数估计为

计算路径上结点数m的蒙特卡罗算法描述如下：
// 已知随机路径上取值数据m0,m1,…,mk-1
m=1;t=1;
for(j=0;j<=k-1;j++)
{ t=t*m[j];
m=m+t;
}
printf(“%ld”,m);
把所求得的随机路径上的结点数（或若干条随机路径的结点数的平均值）与状态空间树上的总结点数进行比较，由其比值可以初步看出回溯设计的效益。在下面的n皇后问题的回溯求解时将具体应用以上蒙特卡罗算法估计回溯设计的效益。

5.8 回溯应用小结
本章应用回溯设计求解了逐位整除数与桥本分数式等涉及数与数式的典型案例、求解了新颖的素数环与德布鲁金环等环序列，求解了直尺刻度分布与数码串珠等趣题，也求解了伯努利装错信封问题与别出心裁的情侣拍照等难度较大的组合案例可见回溯法的应用是非常广阔的。
回溯法有“通用解题法”之称，是一种比穷举“聪明”的搜索技术，在搜索过程中动态地产生问题的解空间，系统地搜索问题的所有解。当搜索到解空间树的任一结点时，判断该结点是否包含问题的解。如果该结点肯定不包含，则“见壁回头”，跳过以该结点为根的子树的搜索，逐层向其祖先结点回溯，可大大缩减无效操作，提高搜索效率。因此，结合具体案例的实际设计合适的回溯点是应用回溯法的关键所在。
值得注意的是，递归具有回溯的功能，很多问题应用递归回溯可探索出问题的所有解。例如，在求解桥本分数式中，既用了回溯法求解，也应用了递归求解，请认真比较这二者之间的关联。尽管递归的效率不高，但递归设计的简明是一般回溯设计所不及的。
回溯法的时间复杂度因案例的具体实际而异，其计算时间可用蒙特卡罗方法计算。一般来说，其搜索效率要高于穷举。