chapter 7 回溯法-new.ppt

1、克服困难性,任课教师：何婧 Email: ,简介,问题：有许多实际问题尚无有效的算法，并且这些问题的算法，即使对于中等规模的实例，需要的时间量也要用年或世纪来度量。 解决方法： 方法一：适用于平均情况下可以得到良好的复杂度，但最坏情况下很难得到多项式解法的问题。例如：回溯法、分支界限法，搜索状态空间，在搜索过程中进行剪枝。 方法二：基于精确的概率概念。例如：随机算法。 方法三：得到近似解。在解的质量上妥协，以得到更快的算法效率（多项式时间）。,回溯法,任课教师：何婧 Email: ,Chapter 7,Outline,算法思想 皇后问题 着色问题 算法复杂度分析,7.1 算法思想,回溯法：有组

2、织的穷尽搜索。在搜索的过程中通过各种约束条件，进行剪枝，避免对所有状态的搜索，从而提高算法效率。 回溯法适用于求解那些组合数多，有大量潜在解的问题，有“通用解题法”之称。,不适合用回溯法求解，可用效率更高的算法，如贪心法和动态规划法求解。,7.1 算法思想,回溯法求问题的所有解时，要回溯到根，且根结点的所有子树都被搜索遍才结束。 回溯法求解问题的一个解时，只要搜索到问题的一个解就可以结束。 运用回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树，算法搜索至解空间树的任一结点时，先判断该结点是否包含问题的解，如果肯定不包含，则跳过以该结点为根的子树的搜索，逐层向其祖先结点回溯；否

3、则，进入该子树，继续按深度优先策略搜索。,7.1 算法思想,问题描述：求一个n元向量（x1,x2,xn）,使之满足问题的某个判定函数B( x1,x2,xn )规定的条件。 显约束：凡是给定了每一个xi的取值范围的约束都是显约束。满足问题的所有显约束的多元向量定义为问题的解空间。 隐约束：描述的是各xi之间复杂的关系。基于问题的解空间，求解满足判定函数B的多元向量。,7.2 皇后问题,问题：n个皇后，置于n*n的方格内，如果任何两个皇后处于同一行，同一列，或处于同一斜线上（斜率为1），都会遭到对方攻击，求一种互不遭到攻击的状态。,解：,有nn种可能解 考虑显约束，有n！种可能解,我们规定第i个皇

4、后位于第i行，n个皇后所在的列构成一个n元向量（x1,x2,xi）xi1，2，n。 皇后甲（i,j）；皇后乙（k,l） 分析判定函数： 不在同一行： i k 不在同一列： j l 不在同一斜线上： |(i-k)/(j-l)|1,7.2 皇后问题,下面我们以四皇后问题为例： 首先：i=1（放置第1个皇后） （1,7.2 皇后问题,i=2 （1，2 因为|（1-2）/（1-2）|=1 故 （1，3,7.2 皇后问题,i=3 （1，3，2 （1，3，4 第三个皇后已经没有合适的位置，此时需要重新放置第（i-1）个（即第2个皇后），此时，需要进行回溯；,7.2 皇后问题,i=i-1=2 原来：（1，3

5、 试探第4个位置 （1，4,7.2 皇后问题,i=3 （1，4，2,7.2 皇后问题,i=4 （1，4，2，3 （1，4，2，4 此时，再次回溯。 i=i-1;,7.2 皇后问题,i=i-1=3 （1，4，3 （1，4，4 又一次回溯,7.2 皇后问题,由于第2个皇后已经没有合适的位置，所以一直回到i=1，我们的工作又回到了起点！,7.2 皇后问题,按照以上的方法，最终可以得到一种4皇后互不攻击的序列 （2 （2，1 （2，3 （2，4 （2，4，1 （2，4，1，3）,7.2 皇后问题,当然，照此方法，我们还可以得到其它互不攻击的序列。实际上，根据对称关系，即可得到另一个解为： （3，1，4

6、，2） （2，4，1，3）,7.2 皇后问题,算法：BackTrack() 求n后问题的所有解 procedure BACKTRACK(n) /迭代回溯过程 begin k=1; X1=0; /k表示行，Xk表示列 while k=1 and k=n begin Xk=Xk1; while Xk=n 且 Placek=false do Xk=Xk1; if Xk=n begin if k=n then 输出Xk; /找到一个解 else k=k+1; Xk=0; end else k=k-1; /回溯 endwhile end,7.2 皇后问题,procedure Place(k) /迭代回溯

7、过程 begin i=1; while ik do /判断第1行到第k-1行的位置 begin if xi=xk or ABS(i-k)=ABS(xi-xk); then return(false); i=i+1; end return (true); end,7.2 皇后问题,7.3 图的着色问题,问题描述：给定一个无向连通图G和m种不同颜色，用这些颜色给G的各顶点着色，每个顶点着一色，问是否有使得G中任何一条边的两个顶点的颜色不同的着色法。,a,b,c,d,e,a,b,c,d,e,显约束： 1Xj,7.3 图的着色问题,算法：找一个图的m着色法，输出所有可能的着色方案 procedure

8、Mcoloring(k) /递归回溯过程, k表示节点，初始为1，Xk表示采用的颜色,初始为0 begin while Xk=m do begin NextValue(k); if Xk = 0 then return; /k节点没有可用的颜色，回溯 if k=n then print(X); /找到一个解 else Mcoloring(k+1); Xk+; endwhile end,7.3 图的着色问题,procedure NextValue(k) /寻找k节点的着色 begin Xk=(Xk+1) mod (m+1); if Xk=0 then return; /Xk的所有色彩已经用完 f

9、or j=1 to n do if Graph(k,j) =1 and Xk=Xj ;/有边相连，且颜色相同 then goto 3; return ; /找到k节点的应着色 end,7.4算法复杂度分析,一个回溯过程的效率在很大程度上依赖于四个方面的因素： 产生显约束函数X(k)的时间； 满足显约束的值X(k)的个数； 计算约束函数Bi (x1,x2,xi)的时间 ； 满足约束函数Bi (x1,x2,xi)的X(k)的个数.,7.4 算法复杂度分析,若从结点数目考虑，能显著地减少生成结点数目的约束函数就是良好的约束函数； 如果从计算Bi (x1,x2,xi)的角度考虑，约束函数越容易计算越好

10、； 然而，我们在选择约束函数时，即要考虑使生成的结点少又要使Bi (x1,x2,xi)容易计算是比较困难的。,7.4 算法复杂度分析,在研究效率时，一般要应用到“重排原理”,对许多问题而言，集合Si可以取任意的顺序，因此，我们可以考虑在其它条件等价的情况下，从具有最小元素个数集合中进行下一步抉择将更为有效。根据这一原则，我们将能够得到效果较好的状态空间树。,7.4 算法复杂度分析,状态空间树选定以后，影响回溯效率的前三个因素就可以确定，只有生成结点的数目是可变的，它将随问题的性质内容及结点的不同生成方式而变动。 如果解空间的节点数是2或2！，在最坏情况下，回溯法的时间耗费一般为O(p(n) 2

11、)或O(q(n)n!)。其中p(n)和q(n)均为n的多项式。 虽然回溯法和穷举法几乎是同一复杂度量级，但它改进了常数因子,7.4 算法复杂度分析,当应用回溯法处理某一具体输入I时，可用蒙特卡罗法来估算将要产生的结点数目。 在状态空间树上产生一条随机的路径，设X是这条随机路径上的一个结点，且位于状态空间树的第h-i层上，对X的所有孩子，用约束函数检验出满足约束条件的结点数目mi，下一个结点从mi中随机选取一个。这条路径一直延伸到叶结点或所有孩子都不满足约束条件为止。,7.4 算法复杂度分析,假设第1层有m0个满足约束的结点，若解空间树的同一层结点具有相同的出度，则第1层上每个结点平均有m1个孩

12、子结点，因此第2层有m0 m1个满足约束条件的结点 依此类推，可以估计回溯法生成的满足约束的结点数m为：1+m0+m0m1+m0m1m2+,7.4 算法复杂度分析,例如：8皇后问题，用Estimate算法估计5条随机路径的解空间状态数,(8,5,4,3,2) =1649,(8,5,3,1,2,1)=769,7.4 算法复杂度分析,例如：8皇后问题，用Estimate算法估计5条随机路径的解空间状态数,(8,5,3,2,2,1,1,1)=2329,(8,6,4,2,1,1,1)=1785,(8,6,4,3,2)=1977,7.4 算法复杂度分析,例如：8皇后问题，用Estimate算法估计5条随机路径的解空间状态数 (8,5,4,3,2) =1649 (8,5,3,1,2,1)=769 (8,6,4,2,1,1,1)=1785 (8,6,4,3,2)=1977 (8,5,3,2,2,1,1,1)=2329 m的平均值为1702 8后问题的解空间树的结点总数为,1.55%左右 回溯法效率大大高于穷举法,