《【教学课件】第5章回溯法.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第5章回溯法.ppt（82页珍藏版）》请在三一办公上搜索。
1、,第5章 回溯法,学习要点5.1 回溯法概述5.2 回溯法的典型示例5.3 回溯法的效率分析本章小结,5.1 回溯法概述,5.1.1 问题的解空间问题的解空间两类典型的解空间5.1.2 回溯法的基本思想回溯法的基本思想算法的框架例：排列与组合小结,问题的解空间,复杂问题的求解复杂问题常常有很多的可能解，这些可能解构成了问题的解空间。解空间也就是进行穷举的搜索空间，所以，解空间中应该包括所有的可能解。问题解的求解方法搜索问题的解空间，获得问题的解，依据搜索策略的不同，可以分为：回溯法分支限界法,问题的解向量：问题的解可以表示成一个n元式(x1,x2,xn)的形式。问题的解空间E=(x1,x2,x
2、n)|xi si,si为有限集 称为问题的解空间约束条件,问题的解空间,问题的解空间,问题的解空间由笛卡儿积AS1S2Sn构成，且第1层的根结点有|S1|棵子树，第2层共有|S1|个结点，第3层共有|S1|S2|个结点，依此类推，第n1层共有|S1|S2|Sn|个结点，他们都是叶子结点，代表问题的所有可能解。显式图和隐式图,两类典型的解空间,两类典型的解空间子集树排列树,子集树,例1：0-1背包问题(0-1 Knapsack Problem)分析：可能解由一个等长向量（x1,x2,xn）组成，其中xi1(1in)表示物品i装入背包xi0(1in)表示物品i没有装入背包如：当n3时，其解空间是：
3、(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1),子集树,可以用一棵满二叉树表示解空间树,例如：W(20,15,15)，V(40,25,25)，C30问题的求解过程：相当于在解空间树中搜索满足条件的叶结点。,子集树,例2：集合Aa1,a2,an，求A的所有子集合（如n3）。,子集树,子集树（Subset Trees）当所给问题是从n个元素的集合中找出满足某种性质的子集时，相应的解空间树称为子集树。在子集树中，一般地：|S1|S2|Sn|2，即每个结点有2棵的子树。解空间为：（0，0，0，0）（0，0，0，1）（1，1
4、，1，1）,子集树,所以，解空间有2n个元素。若表示为树形结构就是一棵有2n个叶结点的二叉树，遍历子集树需(2n)的计算时间。,排列树,排列树（Permutation Trees）：当所给问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。在排列树中，通常情况下，|S1|n，|S2|n1，|Sn|1，解空间为：（1，2，3，n1，n）（2，1，3，n1，n）（n，n1，3，2，1）,排列树,所以：解空间有n!个元素若表示为树形就是一个n度树，这样的树有n!个叶结点，遍历排列树需(n!)计算时间。,排列树,例：旅行商问题问题提出：某售货员要到若干个城市去推销商品。已知各个城市之间的
5、路程（或旅费）。要选定一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使得总的路程（或总旅费）最小。,排列树,分析求赋权图G的具有最小权的Hamilton圈解空间：,当起点1固定时，上图有3!个周游路线（排列问题）,回溯法的基本思想,回溯法回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。,回溯法的基本思想,主要应用解决一些复杂问题在求解的过程中，需要经过若干步骤，而每一个步骤都有若干种可能的分支，为了完成这一过程，又必须遵守一些规
6、则，但这些规则又无法精确地用数学公式或语言来描述的一类问题中。,1.基本思想设问题的解可表示为n元组(x1,x2,xn),xisi,si为有限集,设已有满足约束条件的部分解(x1,x2,xi)添加xi+1 si+1,若(x1,x2,xi xi+1)满足约束条件,则继续添加xi+2；若所有可能的xi+1 si+1均不满足约束条件,则去掉xi,回溯到(x1,x2,xi-1),添加尚未考虑过的xi；如此反复进行,直到(x1,x2,xk)kn满足所有的约束条件或证明无解。,回溯法的基本思想,回溯法的基本思想,2.求解过程求解过程可表示为在一棵解空间树作深度优先搜索。具体过程：搜索按深度优先策略从根开始
7、,当搜索到任一结点时，判断该点是否满足约束条件D(剪枝函数)，若满足则继续向下深度优先搜索，否则跳过该结点以下的子树(剪枝)，向上逐级回溯。,回溯法的基本思想,3.回溯法解题的步骤：(1)针对所给问题，定义问题的解空间；(2)确定易于搜索的解空间结构；(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。,例：排列与组合,计算排列数如何找出m个自然数(1,2,3,m)中n个数的所有排列。分析设(x1,x2,xn）一组解约束条件：显约束：1xim隐约束：xi xj(1ijn)参考程序：,例：排列与组合,计算组合数,例：排列与组合,计算组合数：找出m个自然数(1,2,3,m)中n个
8、数的组合。要求：输入：m,n5 3输出：,例：排列与组合,分析：设(x1,x2,xn）一组解约束条件：显约束：1xim隐约束：x1x2 xn i xi mni 即：xi-1 xi mni 参考程序：,算法的框架,递归回溯的一般框架void backtrack(int i)if(in)output(x);else for(int j=f(n,i);j=g(n,i);j+)xi=h(j);if(constraint(i),剪枝函数,算法的框架,一般来说，非递归回溯（迭代回溯）的算法过程：1.数据初始化2.如果当前状态合法 判断是否到达目标：是，打印结果；然后换下一种情况 不是，则继续向前探索 否则
9、：选择下一种可能；检查是否合法4.重复上述过程，直至所有情况都搜索完毕，结束。,算法的框架,迭代回溯的一般框架void iterativeBacktrack()int i=1;while(i0)if(f(n,i)=g(n,i)for(int j=f(n,i);j=g(n,i);j+)xi=h(j);if(constraint(i)/while/iterativeBacktrack,小结,回溯法解题的特征在深度优先搜索过程中动态产生问题的解空间。几个术语扩展结点:一个正在产生儿子的结点称为扩展结点活结点:一个自身已生成但其儿子还没有全部生成的结点称做活结点死结点:一个所有儿子已经产生的结点称做死
10、结点。需要注意的是：问题的解空间树是虚拟的，并不需要在算法运行时构造一棵真正的树结构。在任何时刻，算法只保存从根结点到当前扩展结点的路径。,小结,避免无效搜索的策略回溯法的搜索过程涉及的结点（称为搜索空间）只是整个解空间树的一部分，在搜索过程中，通常采用两种策略避免无效搜索：用约束条件（约束函数）剪去得不到可行解的子树；用目标函数（限界函数）剪去得不到最优解的子树。这两类函数统称为剪枝函数（Pruning Function）。,5.2 回溯法的典型用例,几个应用专题图问题中的回溯法组合问题中的回溯法其他应用,应用专题一,图问题中的回溯法例1：n后问题排列树的算法框架例2：图的m着色问题例3：T
11、SP问题,例1：n后问题,问题描述：在nn格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在nn格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。,例1：n后问题,例如：88棋盘的一个可行放置。,分析：解向量：(x1,x2,xn)约束条件显约束：xi=1,2,n隐约束：不同列：xixj不处于同一正、反对角线：|ij|xi-xj|过程演示,例1：n后问题,例1：n后问题,法1：4后问题解空间的搜索过程（nn）,法2：4后问题的解空间（排列树）,例1：n后问题,排列树的算法框架,遍历排列树需要O(n!
12、)计算时间void backtrack(int i)if(in)output(x);else for(int j=i;j=n;j+)swap(xj,xi);if(legal(i)backtrack(i+1);swap(xj,xi);,例2：图的m着色问题,问题描述：给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。这个问题是图的m可着色判定问题。若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。,例2：图的m着色问题,分析
13、：本题实际上就是著名的“地图四色”问题。无论地图多么复杂，只需用四种颜色就可以将相邻的区域分开。,例2：图的m着色问题,数据结构:为了解题方便，我们可以把每一个区域看成一个顶点，若两个区域相邻，则相应的顶点间用一条边相连，这样，该问题就转化为图的问题了。,例2：图的m着色问题,例如：,例2：图的m着色问题,分析：解向量：(x1,x2,xn)约束条件显约束：1xim隐约束：顶点i与已着色的相邻顶点的颜色不重复(aki=1)&(xk=xi)算法设计回溯法参考程序,例3：TSP问题,问题提出：分析解空间：排列树,例3：TSP问题,分析：解向量x=(x1,x2,xn)约束条件：显约束：1xin隐约束：
14、xixj(ij)目标函数：回路的代价最短剪枝函数：用约束函数在扩展结点处剪去不满足约束的子树；用限界函数剪去得不到最优解的子树。,例3：TSP问题,回溯法的求解过程,算法设计参考程序Travle.cpp,例3：TSP问题,应用专题二,组合问题中的回溯法子集树的算法框架例1：子集问题例2：01背包问题例3：符号三角形问题,子集树的算法框架,遍历子集树需O(2n)计算时间 void backtrack(int i)if(in)output(x);else for(int j=0;j=1;j+)xi=j;if(legal(i)backtrack(i+1);,例1：子集问题,问题描述集合Aa1,a2,
15、an，求A的所有子集合。问题分析子集树空间算法设计回溯法参考程序子集合.cpp,例2：0-1背包问题,问题描述：给定n个物品和一个背包，物品 i 的重量为wi,其价值为pi,背包的容量为c。问如何装物品，使得装入背包中物品总价值最大？,解空间：子集树可行性约束函数：,例2：0-1背包问题,例如：n=3,c=30,w=(16,15,15),p=(45,25,25),例2：0-1背包问题,例2：0-1背包问题,参考程序（tryload1.cpp）进一步的改进加入限界函数如果扩展结点和它的子孙所导致的最好可行解的上界不大于至今为止所确定的最好解之值，就可以剪去该右子树。,例如：n=3,c=30,w=
16、(16,15,15),p=(45,25,25),例2：0-1背包问题,问题：如何设计限界函数Bound(i,cw,cp)参考程序tryload2.cpp思考：n=4,c=7,w=(3,5,2,1),p=(9,10,7,4)的0-1背包问题的解空间，及搜索回溯过程。,例2：0-1背包问题,例3：符号三角形问题,问题描述下图是由14个“”号和14个“”号组成的符号三角形。2个同号下面是“”号，2个异号下面是“”号。,例3：符号三角形问题,一般情况下，符号三角形的第一行有n个符号。符号三角形问题要求对于给定的n，计算有多少个不同的符号三角形，使“”和“”号相同。注意：在符号三角形的第一行的前t个符号
17、(x1,x2,xt)确定后，就确定了一个由 t*(t+1)/2 个符号组成的符号三角形。在确定xt+1的值后，只要在前面已确定的符号三角形的右边加一条边，就可以扩展为(x1,x2,xt+1)所对应的符号三角形。,例3：符号三角形问题,分析解向量x=(x1,x2,xn)约束条件显约束：xt 0，1xt1：符号三角形的第一行的第t个元素为“”；xt0：符号三角形的第一行的第t个元素为“”；隐约束：显然：(x1,x2,xn)确定的符号三角形总符号数为：total n(n+1)/2。于是符合条件的符号三角形中“+”和“”个数不超过half n(n+1)/4，若超过half，则剪去不满足条件的子树,例3
18、：符号三角形问题,解空间由于xt是二值的，故该问题的解空间为子集树。数据结构设计：三角矩阵参考程序：trytriangle.cpp,应用专题三,其他应用例1：批处理作业调度问题例2：工作安排问题例3：整数的划分问题例4：棋盘覆盖问题例5：八数码难题例6：迷宫问题例7：马踏棋盘问题,例1：批处理作业调度问题,问题描述给定n个作业的集合J1,J2,Jn。每个作业必须先由机器1处理，然后由机器2处理。作业Ji需要机器j的处理时间为tij。对于一个确定的作业调度，设Fij是作业i在机器j上完成处理的时间。所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和。批处理作业调度问题要求对于给定的n个
19、作业，制定最佳作业调度方案，使其完成时间和达到最小。,例1：批处理作业调度问题,例如：,这3个作业的6种可能的调度方案 1,2,3；1,3,2；2,1,3；2,3,1；3,1,2；3,2,1；它们所相应的完成时间和分别是19，18，20，21，19，19。易见，最佳调度方案是1,3,2，其完成时间和为18。,例1：批处理作业调度问题,分析：排列树空间搜索算法描述,void Backtrack(int i)if(i n)for(int j=1;j f1)?f2i-1:f1)+Mxj2;f+=f2i;if(f bestf)Swap(xi,xj);Backtrack(i+1);Swap(xi,xj)
20、;f1-=Mxj1;f-=f2i;,例2：工作安排问题,问题描述设有n项工作要安排给n个人去完成。让第i个人去完成第j项工作产生的效益为aij。试设计一个算法，为每个人安排一件不同的工作，并使总效益最大。例如：,例2：工作安排问题,分析：思路：每个人选择n项工作中的一项，在各种选择的组合中，找到效益最大的一种组合输出。解向量x=(x1,x2,xn)解空间：排列树空间参考程序,例3：整数的划分问题,问题提出：将一个正整数n表示成形如下式的一系列正整数的和，称为n的一个划分。nn1n2nk(ni1,i1,2,k,k1且nn1n2nk 1,例3：整数的划分问题,例如：整数6的分划数有11种:6；5+
21、1；4+2，4+1+1；3+3，3+2+1，3+1+1+1；2+2+2，2+2+1+1，2+1+1+1+1；1+1+1+1+1+1;,分析解向量x=(x1,x2,xn)约束条件显约束：1xi n隐约束：nx1x2xk(xi1,i1,2,k,k1)nx1x2xk 1问题的解空间参考程序,例3：整数的划分问题,例4：棋盘覆盖问题,问题描述：在一个nn个方格组成的棋盘中，要用图示的4种不同形态的L型骨牌覆盖给定的棋盘上的所有方格，且任何2个L型骨牌不得重叠覆盖。（必要时，需要挖掉1块）,例如：,例4：棋盘覆盖问题,例4：棋盘覆盖问题,考虑几个问题L型骨牌的表示方式约束条件求解过程参考程序：,例5：八
22、数码难题,问题描述：求解过程示意图：程序实现：,例6：迷宫问题,问题描述问题分析过程演示算法设计,例7：马踏棋盘问题,问题描述在n x n棋盘（有n x n个格点的棋盘）的某个格点上有一个中国象棋马，马走日字。求一条周游棋盘的路径，使得马能够从起始位置起沿着该路径每个格点恰好走一次最后回到出发位置。输入n(棋盘规格)输出周游路线分析回溯+贪心,例如：66,例如：1616,5.3 回溯法效率分析,影响回溯法效率的几个因素：生成结点所花费的时间；计算约束条件所花费的时间；计算目标函数的界所花费的时间；所生成的结点个数。,解向量中分量排列顺序的影响重排原理解向量中分量的取值范围不同时，在解向量中的不
23、同排列顺序，其对应的状态空间树的结构也不同。在其他条件相当的前提下，让可取值最少的xi。例如：从下图中关于同一问题的2棵不同解空间树，可以体会到这种策略的潜力。,5.3 回溯法效率分析,解空间：(x1,x2,x3)|xi si,i=1,2,3,|s1|=3,|s2|=4,|s3|=2解空间树1：对应于(x1,x2,x3)|的状态空间树如图 所示，第一层三棵子树各对应8个可能解，剪去其中一棵子树，只减少8个可能解。,5.3 回溯法效率分析,5.3 回溯法效率分析,解空间树2：对应于(x3,x1,x2)|的状态空间树如图 所示，第一层二棵子树各对应12个可能解，剪去其中一棵子树，只减少12个可能解。,本章小结,本章小结回溯法的设计思想解空间及解空间的搜索策略回溯法求解的典型用例,
