(算法分析设计)第5章回溯法课件.ppt

1、12回溯法 解空间：问题可行解的集合；回溯法：以深度优先方式系统搜索问题的解回溯法：以深度优先方式系统搜索问题的解“通用解题法通用解题法”系统地搜索问题的所有解 在问题的解空间树中，按深度优先策略，从根结点出发在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树搜索解空间树 当搜索到解空间树的任一结点时，先判断该结点是否包含问题的解。如果确定不包含，则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯回溯；否则，进入该子树，继续按深度优先策略搜索。求解问题性质求解问题性质 回溯法求问题的所有解时，要回溯到根，且根结点的所有子树都被搜索遍才结束；回溯法求问题的一个解时，只要搜索到问题的

2、一个解即可3知识点 问题的解空间 回溯法的基本思想 递归回溯 迭代回溯 子集树与排列树4知识点 问题的解空间问题的解空间 回溯法的基本思想 递归回溯 迭代回溯 子集树与排列树5问题的解空间 解空间解空间 应明确问题的解空间的定义 问题的解空间至少应包含问题的一个（最优解）。对问题解空间进行组织 通常组织为树或图的形式。有利于回溯法对整个解空间的搜索6知识点 问题的解空间 回溯法的基本思想回溯法的基本思想 递归回溯 迭代回溯 子集树与排列树7回溯法的基本思想 基本思想基本思想 在确定解空间的组织结构后，回溯法从开始结点（根结点）出发，以深度优先方式搜索深度优先方式搜索整个解空间。这个开始结点成为

3、活结点活结点，同时也成为当前的扩展结点当前的扩展结点。在当前扩展结点处，搜索向纵深方向移至一个新结点。这个新结点成为新的活结点，并成为扩展结点。如果在当前扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点死结点。此时，应往回移动（回溯）往回移动（回溯）到最近的活结点处，并使该结点成为当前的扩展结点。回溯法按上述方式递归递归地在解空间中搜索，直到找到所直到找到所要求的解或解空间中无活结点为止要求的解或解空间中无活结点为止。8实例分析 n=3的的0-1背包问题背包问题 w=16,15,15 p=45,25,25 c=309解空间为：解空间为：(0,0,0),(0,1,0),(0,0,1),

4、(1,0,0),(0,1,1),(1,0,1),(1,1,0),(1,1,1)ABCDEFGHIJKLMNO10111111000000n=3的的0-1背包问题的解空间树背包问题的解空间树活结点&当前扩展结点BBB活结点死结点10ABCDEFGHIJKLMNO10111111000000当前唯一的活结点，也是当前的扩展结点假定沿纵深方向假定沿纵深方向进行搜索时，选进行搜索时，选择先移至结点择先移至结点B11ABCDEFGHIJKLMNO10111111000000结点A、B都是活结点，B是当前扩展结点说明：由于选中了w1，所以结点B处剩余背包容量为30-16=14，获取的价值为45下一步向D移

5、动，还是向E移动？12ABCDEFGHIJKLMNO10111111000000分析：分析：由于移动到D，表明需要将物品2放入背包，物品2的体积为15，而背包目前的剩余容量为1414）移向结点K可行（不增加容量）15ABCDEFGHIJKLMNO10111111000000分析：分析：由于从K结点无法再向纵深方向移动，因此，K结点成为死结点，回溯到上一个活结点E。（1，0，0）为一可行解）为一可行解16ABCDEFGHIJKLMNO10111111000000分析：分析：由于从E结点无法再向纵深方向移动，因此，E结点成为死结点，回溯到上一个活结点B。17ABCDEFGHIJKLMNO10111

6、111000000分析：分析：由于从B结点无法再向纵深方向移动，因此，B结点成为死结点，回溯到上一个活结点A。18ABCDEFGHIJKLMNO10111111000000向纵深移动到C19ABCDEFGHIJKLMNO10111111000000此时A、C为活结点C为当前扩展结点分析：分析：此时，背包的剩余容量为r=30，获取的价值为0假定沿纵深方向进假定沿纵深方向进行搜索时，选择先行搜索时，选择先移至结点移至结点F20ABCDEFGHIJKLMNO10111111000000此时A、C、F为活结点F为当前扩展结点分析：分析：此时，背包的剩余容量为r=30-15=15，获取的价值为25移动方

7、向：移动方向：L or M？分析：分析：移向结点L、M都可行（都在容量允许范围内）21ABCDEFGHIJKLMNO10111111000000(0,1,1)为一可行解为一可行解22ABCDEFGHIJKLMNO10111111000000按上述规则进行解空间搜索，直到所有的结点都成为死结点此时共获得5个可行解：(1,0,0)，(0,1,1)，(0,1,0)，(0,0,1)，(0,0,0)其中其中(0,1,1)为最优解为最优解23如何避免回溯法的无效搜索 避免无效搜索避免无效搜索 用约束函数约束函数在扩展结点处剪去不满足约束的子树；见0-1背包问题 用限界函数限界函数剪去得不到最优解的子树；见

8、TSP问题以上两类函数统称为剪枝函数24回溯法的主要步骤 主要步骤主要步骤 针对所给问题，定义问题的解空间；确定易于搜索的解空间结构；以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。25知识点 问题的解空间 回溯法的基本思想 递归回溯递归回溯 迭代回溯 子集树与排列树26递归回溯void backtrackbacktrack(int t)if(tn)output(x);elsefor(int i=f(n,t);i0)if(f(n,t)=g(n,t)for(int i=f(n,t);in)output(x);elsefor(int i=0;in)output(x);elsefor

9、(int i=t;i59，所以舍弃该结点所以舍弃该结点。按上述搜索原则，对整个按上述搜索原则，对整个排列树进行遍历，共找到排列树进行遍历，共找到条可能的周游路径，其条可能的周游路径，其中费用最少的周游路径为中费用最少的周游路径为1-3-2-4-1（其费用为（其费用为25）45剪枝函数的引入 剪枝函数的引入剪枝函数的引入 目的：提高回溯法的搜索效率；剪枝函数的设定：剪枝函数的设定：采用当前已知的最短路径（为）为标准，对于有个结点的TSP问题来说，假设当前搜索第层(1i25，所以舍弃该结点所以舍弃该结点。I为根为根的子树不可能包含更优的解，剪去。的子树不可能包含更优的解，剪去。按上述搜索原则，对整

10、个按上述搜索原则，对整个排列树进行遍历，共找到排列树进行遍历，共找到条可能的周游路径，其条可能的周游路径，其中费用最少的周游路径为中费用最少的周游路径为1-3-2-4-1（其费用为（其费用为25）47#include#include const int n=4;/图的顶点数class Travelingfriend int TSP(int an,int v);private:void Swap(int&,int&);void Backtrack(int i);int ann,/图G的邻接矩阵 cv,/当前费用 bestv;/当前最优值 *x,/当前解*bestx,/当前最优解;48void T

11、raveling:Backtrack(int i)if(i+1n)if(axn-2xn-1&axn-10&cv+axn-2xn-1+axn-10bestv)/比较当前的最优解与当前获得的解，当前解更优则替换for(int j=0;jn;j+)bestxj=xj;bestv=cv+axn-2xn-1+axn-10;return;for(int j=i;jn;j+)/判断是否可进入xj子树，此处实现了剪枝if(axi-1xj&cv+axi-1xjbestv)/搜索子树Swap(xi,xj);cv+=axi-1xi;Backtrack(i+1);cv-=axi-1xi;Swap(xi,xj);49i

12、nt TSP(int an,int v)/初始化Traveling Y;Y.x=new int n;for(int i=0;in;i+)Y.xi=i;for(i=0;in;i+)/连接代价对称for(int j=0;j=i;j+)Y.aij=Y.aji=aij;Y.cv=0;Y.bestv=100000;/Y.bestx=v;coutAdjacency Matrix of G:n;for(i=0;in;i+)for(int j=0;jn;j+)coutsetw(5)Y.aij;coutendl;Y.Backtrack(1);delete Y.x;return Y.bestv;50void ma

13、in()int tn=0,30,6,5,4,10,20,vn=0,1,2,3;coutnBestv=TSP(t,v)nnPath=;for(int i=0;in;i+)coutvi+1setw(4);coutv0+1endlendl;复杂度分析复杂度分析算法backtrack在最坏情况下可能需要更新当前最优解O(n-1)!)次，每次更新bestx需计算时间O(n)，从而整个算法的计算时间复杂性为O(n!)。51常用的TSP问题求解方案 常用的求解常用的求解TSP问题的方案问题的方案 遗传算法 模拟退火 神经网络 并行算法52N皇后问题皇后问题53皇后问题 P129 皇后问题皇后问题 问题描述：

14、在n*n格的棋盘上放置彼此不受攻击的个皇后。按国际象棋规则，皇后可以攻击与之处于同一行或同一列或同一斜线上的棋子。54皇后问题 皇后问题皇后问题 大数学家高斯于大数学家高斯于1850年提出年提出 N.Wirth在在程序程序=算法算法+数据结构数据结构中中给出了该问题的回溯给出了该问题的回溯算法（算法（Pascal语言实语言实现）现）可获得个解，但可获得个解，但实际上实际上只有个不只有个不同解同解（考虑棋盘的对（考虑棋盘的对称性）称性）55皇后问题的个不同解图示说明图示说明56其中一个可行解的图示其中一个可行解：x1 x2 x3 x4 x5 x6 x7 x81 5 8 6 3 7 2 4表示第个

15、皇后被放在第行的第列上57算法设计 算法设计算法设计 用元组x1:n表示n皇后问题的解 xi表示皇后i放在第i行的第xi列上 用完全叉树表示解空间用完全叉树表示解空间 剪枝函数设计剪枝函数设计：对于两个皇后A(i,j)、B(k,l)两个皇后不同行：i不等于k;两个皇后不同列：j不等于l;两个皇后不同一条斜线|i-k|j-l|，即两个皇后不处于同一条y=x+a或y=-x+a的直线上58实现递归算法bool Queen:Place(int k)for(int j=1;jn)sum+;else for(int i=1;i=n;i+)xt=i;if(Place(t)Backtrack(t+1);59实

16、现迭代算法void nQueen(int nn)n=nn;sum=0;x=new intn+1;for(int i=0;i0)xk+=1;while(xk=n)&!(place(k)xk+=1;/搜索可能的放置位置 if(xkn，表示算法搜索到叶结点，表示算法搜索到叶结点 得到一个新的方案，当前找到的m可着色方案数加1；当当in时，表示当前扩展结点为时，表示当前扩展结点为解解空间树的内部空间树的内部结点，该结点有结点，该结点有xi=1,2,m共共m个子结点个子结点 对该结点的每一个子结点，根据邻接矩阵根据邻接矩阵a和两个顶和两个顶点的着色，判断其可行性点的着色，判断其可行性；如果可行如果可行，

17、继续按深度优先方式递归地对可行子树进行搜索；否则否则，将以该子结点为根结点的子树中的所有结点都设置为死结点，算法回溯到为活结点的最近的父结点处继续按深度优先方式进行搜索；剪枝函数剪枝函数69解向量：(x1,x2,xn)表示顶点i所着颜色xi 可行性约束函数：顶点i与已着色的相邻顶点颜色不重复。类Coloring记录解空间中结点信息void Color:Backtrack(int t)if(tn)sum+;for(int i=1;i=n;i+)cout xi ;cout endl;else for(int i=1;i=m;i+)xt=i;if(Ok(t)Backtrack(t+1);xt=0;b

18、ool Color:Ok(int k)/检查颜色可用性 for(int j=1;jn时时，算法搜索到叶结点，得到新的圆排列方案并计算当前圆排列长度；如果小于当前已知的最优解，则将该解定为当前已知的最优解；否则，舍弃；当当in时时，表示当前扩展结点为结空间树的内部结点，此时算法要选择下一个要排列的圆，并计算相应的下界函数下界函数。如果满足下界约束（小于设定的阈值），继续按深度优先方式递归地对相应子树进行搜索；否则，剪去该子树，算法回溯到为活结点的最近的父结点处继续按深度优先方式进行搜索；76算法实现void Circle:Backtrack(int t)if(tn)compute();compu

19、te();elsefor(int j=t;j=n;j+)Swap(rt,rj);float centerx=Center(t);Center(t);if(centerx+rt+r1min)/下界约束xt=centerx;Backtrack(t+1);Swap(rt,rj);已经找到一个新的圆排列已经找到一个新的圆排列方案，计算该方案的圆排方案，计算该方案的圆排列长度列长度计算当前所选择的圆的圆心计算当前所选择的圆的圆心横坐标（取最小值返回）横坐标（取最小值返回）77算法实现Float Circle:Center(int t)float temp=0;for(int j=1;jtemp)temp

20、=valuex;2)()(22jrtrjrtrjrtr242x记录当前圆排列中各圆的圆心横坐标78算法实现float Circle:Compute(void)float low=0,high=0;for(int i=1;i=n;i+)if(xi-rihigh)high=xi+ri;if(high-lowmin)min=high low;low/high记录当前圆排列中各圆的最左/右横坐标79算法复杂性分析)!1(nO析圆排列的算法复杂性分80回溯法的效率分析回溯法的效率分析回溯法的效率分析影响回溯法效率的主要因素1.产生xk的时间2.满足显约束的xk值的个数3.计算约束函数constrain的

21、时间4.计算上界函数bound的时间5.满足约束函数和上界函数约束的所有xk的个数好的约束函数可以明显降低生成结点的数量，但往往需要较大的计算量。在选择约束函数时，通常采取在生成结点数和约束函数计算量之间取折衷。解空间的结构一旦选定，影响回溯法效解空间的结构一旦选定，影响回溯法效率的前三个因素就可以确定，剩下的就率的前三个因素就可以确定，剩下的就是考虑回溯过程中生成结点的个数。是考虑回溯过程中生成结点的个数。随问题的具体内容以及结点的随问题的具体内容以及结点的不同生成方式而变动不同生成方式而变动81对于许多问题而言，在搜索试探时选取xi的值顺序是任意的。在其它条件相当的前提下，让可取值最少的在

22、其它条件相当的前提下，让可取值最少的xi优先优先。从图中关于同一问题的2棵不同解空间树，可以体会到这种策略的潜力。图(a)中，从第1层剪去1棵子树，则从所有应当考虑的3元组中一次消去12个3元组。对于图(b)，虽然同样从第1层剪去1棵子树，却只从应当考虑的3元组中消去8个3元组。前者的效果明显比后者好。(a)(b)82存在的困难 存在的困难存在的困难 对回溯法在解具体问题时所产生的结点数的估计 即使对两个非常相近的实例，其产生的结点数也会存在很大的差别 可参考性不理想可参考性不理想 解决的方法：概率方法概率方法83用概率方法估计将产生的接点数 用概率方法估计将产生的结点数用概率方法估计将产生的

23、结点数 主要思想主要思想 在解空间树上产生一条随机路径，然后沿该路径估算解空间中满足约束条件的结点树m。直到延伸到叶节点或所有子节点都不满足约束条件为止84public int estimate(int n)public int estimate(int n)int m=1,r=1,k=1;int m=1,r=1,k=1;while(k=n)while(k=n)T=xk T=xk的满足约束条件的可取值集合；的满足约束条件的可取值集合；if(T.size=0)return m;if(T.size=0)return m;r r*=T.size;=T.size;m+=r;m+=r;xk=T.choo

24、se();xk=T.choose();k+;k+;return m;return m;采用概率方法估算回采用概率方法估算回溯法产生节点的数量溯法产生节点的数量随机随机从T.size个子节点中选择一个作为下一步移动的方向假设其他节点也具有相同大小的满足约束条件的可取值集合85存在的问题 存在的问题存在的问题 使用静态约束函数，在某些情况下产生的估计较为保守。解决方案解决方案 多选取几条不同的路径，分别计算m，然后平均，这样的估算结果会更准确些。86本章小结 本章小结本章小结 回溯法的基本思想 问题解空间的定义与组织 剪枝函数的设计 掌握利用回溯法求解问题的方法 效率分析1.有4个城市的旅行商问题，其费用矩阵如图所示，矩阵的每个元素aij分别为相应i到j城市的旅费代价，表示无意义或无通路。求从第一个城市出发，最后回到城市1的最短路线。请画出解空间树，给出最优解。87纸质作业题(第9周作业)882.设计一个回溯算法，确定是否 K个王后能够攻击一个n*n 棋盘的所有位置。3.用回溯算法，请画出搜索树，说明最短路径的搜索过程。编程实现题(第10周作业)5-1，5-7，5-17