算法设计之回溯法(第5章)课件

1、第5章 回溯法有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。回溯法问题的解空间问题的解向量：回溯法希望一个问题的解能够表示成一个n元式(x1,x2,xn)的形式。显约束：对分量xi的取值

2、限定。隐约束：为满足问题的解而对不同分量之间施加的约束。解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。注意：同一个问题可以有多种表示，有些表示方法更简单，所需表示的状态空间更小（存储量少，搜索方法简单）。n=3时的0-1背包问题用完全二叉树表示的解空间回溯法的基本思想(1)针对所给问题，定义问题的解空间；(2)确定易于搜索的解空间结构；(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。常用剪枝函数：用约束函数在扩展结点处剪去不满足约束的子树；用限界函数剪去得不到最优解的子树。用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解

3、空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n)。而显式地存储整个解空间则需要O(2h(n)或O(h(n)!)内存空间。递归回溯回溯法对解空间作深度优先搜索，因此，在一般情况下用递归方法实现回溯法。/针对N叉树的递归回溯方法void backtrack (int t) if (tn) output(x); else for (int i=f(n,t);i0) if (f(n,t)=g(n,t) for (int i=f(n,t);in) output(x); else for (int

4、i=0;in) output(x); else for (int i=t;i n) / 到达叶结点 更新最优解bestx,bestw;return; r -= wi; if (cw + wi bestw) xi = 0; / 搜索右子树 backtrack(i + 1); r += wi; 装载问题批处理作业调度给定n个作业的集合J1,J2,Jn。每个作业必须先由机器1处理，然后由机器2处理。作业Ji需要机器j的处理时间为tji。对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间。所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和。批处理作业调度问题要求对于给定的n个作

5、业，制定最佳作业调度方案，使其完成时间和达到最小。tji机器1机器2作业121作业231作业323顺序完成时间和1，2，33610191，3，2378182，1，34610202，3，1489213，1，2568193，2，156819显然，1,3,2是最佳调度方案批处理作业调度tji机器1机器2作业121作业2310作业323解空间：排列树批处理作业调度tji机器1机器2作业121作业2310作业323顺序完成时间和1，2，331518361，3，23717272，1，3131417442，3，1131617463，1，25617283，2，15151636解空间：排列树批处理作业调度cla

6、ss Flowshop private: void Backtrack(int i); int *M, / 各作业所需的处理时间 *x, / 当前作业调度 *bestx, / 当前最优作业调度 *f2, / 机器2完成处理时间 f1, / 机器1完成处理时间 f, / 完成时间和 bestf, / 当前最优完成时间和 n; / 作业数; Mj1:作业j的在机器1上要的时间Mj2:作业j的在机器2上要的时间批处理作业调度解空间：排列树void Flowshop:Backtrack(int i) if (i n) for (int j = 1; j = n; j+) bestxj = xj; be

7、stf = f; else for (int j = i; j f1)?f2i-1:f1)+ Mxj2; f+=f2i; if (f bestf) Swap(xi, xj); Backtrack(i+1); Swap(xi, xj); f1- =Mxj1; f- =f2i; 最坏情况下，算法效率为O(n!)解向量：(x1, x2, , xn)显约束：xi=1,2, ,n隐约束： 1)不同列：xixj 2)不处于同一正、反对角线：|i-j|xi-xj|n后问题(i,xi)(j,xj)(i,xi)(j,xj)bool Queen:Place(int k) /判断第k个皇后的位置是否与前面的皇后相冲

8、突。 for (int j=1;jn) sum+; /找到了一组新的解 else for (int i=1;i=n;i+) xt=i; if (Place(t) Backtrack(t+1); n后问题解空间：满N叉树0-1背包问题解空间：子集树可行性约束函数：上界函数：解空间：满二叉树考虑一个右子树的时候，设r是当前未考虑的剩余物品的总价值cp是当前的价值bestp是当前得到的最优价值那么，满足： 时，可以删去右子树。但是，上界r太松。一个更加紧的上界：将剩余物品按照单位重量价值排序，然后依次装入物品，直到装不下，再将剩余物品的一部分放入背包。Typep Knap:Bound(int i)

9、/ 计算上界 Typew cleft = c - cw; / 剩余容量 Typep b = cp; /用于计算上界 以物品单位重量价值递减序装入物品 while (i = n & wi = cleft) cleft -= wi; b += pi; i+ / 装满背包 if (i = n) b += pi * cleft / wi ; return b;0-1背包问题上界函数1423645201030旅行售货员问题旅行售货员问题就是在图中找到一个权最小的周游路线解空间：排列树剪枝策略：当前路径的权重下一个路径的权重当前的最小权重，则搜索该路径4旅行售货员问题templatevoid Travel

10、ing:Backtrack(int i) if (i = n) if (axn-1xn != NoEdge & axn1 != NoEdge & (cc + axn-1xn + axn1 bestc | bestc = NoEdge) for (int j = 1; j = n; j+) bestxj = xj; bestc = cc + axn-1xn + axn1; 节点n-1与节点n之间有通路节点1与节点n之间有通路新计算出来的周游权重比最小的周游权重还小记载该最优周游权重aN+1N+1:图的邻接矩阵；x:当前解；bestx:最优解；cc:当前费用；bestc:当前最优费用算法未完接下页

11、else for (int j = i; j = n; j+) / 是否可进入xj子树? if (axi-1xj != NoEdge & (cc + axi-1xi bestc | bestc = NoEdge) / 搜索子树 Swap(xi, xj); cc += axi-1xi; Backtrack(i+1); cc -= axi-1xi; Swap(xi, xj); 旅行售货员问题当前路径的权重下一个路径的权重 n) / 到达叶结点 for (int j = 1; j = n; j+) bestxj = xj; bestn = cn; return; / 检查顶点 i 与当前团的连接 boolean ok = true; for (int j = 1; j bestn) / 进入右子树 xi = 0; backtrack(i + 1); 12453复杂度分析最大团问题的回溯算法backtrack所需的计算时间显然为O(n2n)。进一步改进算法的建议选择合适的搜索顺序，可以使得上界函数更有效的发挥作用。例如在搜索之前可以将顶点按度从小到大排序。这在某种意义上相当于给回溯法加入了启发性。定义Si=vi,vi+1,.