算法第5章回溯法.ppt

第5章回溯法,学习要点理解回溯法的深度优先搜索策略掌握用回溯法解题的算法框架（1）递归回溯最优子结构性质（2）迭代回溯贪心选择性质（3）子集树算法框架（4）排列树算法框架,通过应用范例学习回溯法的设计策略。（1）装载问题；（2）批处理作业调度；（3）符号三角形问题（4）n后问题；（5）0-1背包问题；（6）最大团问题；（7）图的m着色问题（8）旅行售货员问题（9）圆排列问题（10）电路板排列问题（11）连续邮资问题,用计算机求解问题,问题空间,现实求解过程,实际解,状态空间,对象的定义,机器求解过程,算法与程序的设计,机内解,计算机求解的过程,在状态空间寻找机内解,可以看成是从初始状态出发,搜索目标状态(解所在的状态)的过程。,状态空间,初始状态,目标状态,搜索,搜索的过程可描述为：S0S1Sn，其中S0为初态，Sn为终态。或者说(S0)且(Sn)，这里称为初始条件，称为终止条件。,6,求解是状态空间的搜索,求解的过程可以描述为对状态空间的搜索,S0,S11,S12,S1k,Sn1,Sni,Snm,其中S0为初始状态，不妨设Sni为终止状态,S0,Sni,问题求解就是通过搜索，寻找出一条从初始状态S0到终止状态Sni的路径。,7,几种搜索方法,状态空间的搜索实际上是一种树/DAG（DirectedAcyclicGraph）的搜索，常用的方法有：,广度优先搜索深度优先搜索启发式搜索,从初始状态开始，逐层地进行搜索。,从初始状态开始，逐个分枝地进行搜索。,从初始状态开始，每次选择最有可能达到终止状态的结点进行搜索。,8,三种搜索的优劣之处,一般来说，三种搜索方法各有优劣之处：广度优先搜索和深度优先搜索优点：一定能找到解；缺点：时间复杂性大。启发式搜索优点：一般来说能较快地找到解，即其时间复杂性小；缺点：需要设计一个评价函数，并且评价函数的优劣决定了启发式搜索的优劣。,当需要找出问题的解集，或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。在问题的解空间树中，回溯法按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。,回溯法,5.1回溯法的算法框架5.1.1问题的解空间,应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应至少包含问题的一个(最优)解。通常将解空间组织成树或图的形式。问题的解向量：回溯法希望一个问题的解，能够表示成一个n元式(x1,x2,xn)的形式。显约束：对分量xi的取值限定隐约束：为满足问题的解，而对不同分量之间施加的约束。解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。例如，对于有n种可选物品的0-1背包问题，其解空间由长度为n的0-1向量组成。,5.1.2回溯法的基本思想,扩展结点:一个正在产生儿子的结点活结点:一个自身已生成但其儿子还没有全部生成的节点死结点:一个所有儿子已经产生的结点深度优先的问题状态生成法：如果对一个扩展结点R，一旦产生了它的一个儿子C，就把C当做新的扩展结点。在完成对子树C（以C为根的子树）的穷尽搜索之后，将R重新变成扩展结点，继续生成R的下一个儿子（如果存在）宽度优先的问题状态生成法：在一个扩展结点变成死结点之前，它一直是扩展结点。回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(boundingfunction)来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。具有限界函数的深度优先生成法称为回溯法。,基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前扩展结点，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。,示例10-1背包问题,n=3,C=30,w=16,15,15,v=45,25,25开始时，Cr=C=30，V=0，A为唯一活结点，也是当前扩展结点扩展A，先到达B结点Cr=Cr-w1=14，V=V+v1=45此时A、B为活结点，B成为当前扩展结点扩展B，先到达DCr45，皆得到一个可行解x=(0,1,1)，V=50L不可扩展，成为死结点，返回到F再扩展F到达MM是叶结点，且2550，不是最优解M不可扩展，成为死结点，返回到FF没有可扩展结点，成为死结点，返回到C再扩展C到达GCr=30，V=0，活结点为A、C、G，G为当前扩展结点扩展G，先到达N，N是叶结点，且25n时已搜索到一个叶结点,output(x)对得到的可行解x进行记录或输出处理.elsefor(inti=f(n,t);i0)if(f(n,t)n)for(intj=1;jf1)?f2i-1:f1)+Mxj2;f+=f2i;if(fhalf)|(t*(t-1)/2-counthalf)return;if(tn)sum+;/搜索至叶结点,得到+-号相同的符号三角形,三角形数增1.elsefor(inti=0;i2;i+)p1t=i;count+=i;for(intj=2;j=t;j+)pjt-j+1=pj-1t-j+1pj-1t-j+2;count+=pjt-j+1;Backtrack(t+1);for(intj=2;j=t;j+)count-=pjt-j+1;count-=i;,+-+-+-+-+-+-+-+,复杂度分析计算可行性约束需要O(n)时间，在最坏情况下有O(2n)个结点需要计算可行性约束，故解符号三角形问题的回溯算法所需的计算时间为O(n2n)。,5.5n后问题,在nn格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在nn格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。,解向量：(x1,x2,xn),xi表示皇后i放在棋盘的第i行的第xi列上.解空间:排列树显约束：xi=1,2,n(列的取值范围)隐约束：1)不同列：xixj2)不处于同一正、反对角线上：|i-j|xi-xj|事实上,如果用(i,j)表示棋盘上第i行与第j列交叉的位置,则在同一条平行于主对角线的对角线上的两点(i,j)和(k,l)满足关系式i-j=k-l;而处于同一条平行于副对角线的对角线上的两点(i,j)和(k,l),则满足关系式i+j=k+l.将这两个关系式略作变形即得两种情况的统一表示：|i-k|=|j-l|(*)反之,如果棋盘上的两点(i,j)和(k,l)满足关系式(*),则它们一定位于同一条对角线上.,设计函数Place来测试:若将皇后k放在xk列,是否与前面已放置的k-1个皇后都不在同一列,且不在同一斜线上.回溯法解n后问题,用一棵完全n叉树来表示其解空间.用可行性约束函数place可剪去不满足行、列和斜线约束的子树.,boolQueen:Place(intk)for(intj=1;jn)sum+;/sum为已找到的可行方案数elsefor(inti=1;in)sum+;for(inti=1;i=n;i+)coutxi;coutendl;elsefor(inti=1;i=m;i+)xt=i;if(Ok(t)Backtrack(t+1);,boolColor:Ok(intk)/检查颜色可用性for(intj=1;jn)Compute();/完成所有圆，计算排列长度elsefor(intj=t;j=n;j+)/考虑各种排列Swap(rt,rj);floatcenterx=Center(t);/求得第t个圆的圆心相对第1个圆的圆心的横坐标if(centerx+rt+r1min)/判断此时排列长度是否已超过当前解，未超过继续递归xt=centerx;/修改圆t的圆心坐标Backtrack(t+1);Swap(rt,rj);/还原排列,51,voidCircle:Compute(void)/计算当前圆排列的长度floatlow=0,/low表示圆排列的最左端坐标high=0;/high表示圆排列的最右端坐标/此时的坐标是相对第一个圆的圆心建立的for(inti=1;ihigh)high=xi+ri;/计算最右端if(high-low0且nowjtotalj,59,计算插槽i和i1的连线密度例如i=2,此刻now1=now2=now3=now4=1,total1=3,total2=total3=total4=2,N1,N2,N3,N4的连线都跨越电路板2和3,60,算法效率在每个结点处,函数Backtrack花费O(m)时间计算每个儿子结点的密度.排列树的搜索时间为O(n!).算法耗费为O(mn!).,61,5.12连续邮资问题,假设国家发行了n种不同面值的邮票，并且规定每张信封上最多只允许贴m张邮票。,连续邮资问题要求:对于给定的n和m的值，给出邮票面值的最佳设计，使得在1张信封上可贴出从邮资1开始，增量为1的最大连续邮资区间。,62,例如:当n=5和m=4时，设解为X=,其中x1=1,并且满足：x1,则邮资连续区间为1-4.,63,算法设计：解向量：用n元组x1:n表示n种不同的邮票面值，并约定它们从小到大排列。x1=1是唯一的选择。此时最大连续邮资区间是1:m.x2的取值范围是2:m+1可行性约束函数：已选定x1:i-1，其最大连续邮资区间是1:r，接下来xi的取值范围是xi-1+1:r+1。方法：回溯法，用一棵树来表示解空间。树结点的度随x的值变化代码程序见p171-173,64,5.13回溯法效率分析,通过前面具体实例的讨论容易看出，回溯算法的效率在很大程度上依赖于以下因素：产生xk的时间；满足显约束的xk值的个数；计算约束函数constraint的时间；计算上界函数bound的时间；满足约束函数和上界函数约束的所有xk的个数。好的约束函数能显著地减少所生成的结点数。但这样的约束函数往往计算量较大。选择约束函数时,通常存在生成结点数与约束函数计算量之间的折衷。,65,重排原理,在搜索试探时，选取xi的值顺序是任意的。在其它条件相当的前提下，让可取值最少的xi优先。下图中关于同一问题的2棵不同解空间树，可以体会到这种策略的潜力。,图(a)中，从第1层剪去1棵子树，则从所有应当考虑的3元组中一次消去12个3元组(叶结点)。对于图(b)，虽然同样从第1层剪去1棵子树，却只从应当考虑的3元组中消去8个3元组。前者的效果明显比后者好。,(a),(b),66,估计回溯算法的结点数目和平均效率蒙特卡罗方法主要思想:在解空间树上产生一条随机的路径,并沿此路径估算解空间树中满足约束条件的结点总数.MonteCarlo方法的算法步骤:1从根开始，随机选择一条路经，直到不能分支为止,从x1,x2,依次对xi赋值，每个xi的值是从当时的路径中随机选取，直到向量不能扩张为止.2假定搜索树的其他分支与以上随机选出的路径一样，计算搜索树的结点数。3重复步骤1和2，将结点数进行概率平均。,67,算法MonteCarlo1sum0;/sum为t次结点平均数2fori1totdo/取样次数t3.mEstimate(n);/m为本次结点总数4.sumsum+m;5.sumsum/t;,68,m为本次取样结点总数，k为层数，r为本层分支数,n为树的层数,mi为第i层满足约束条件的结点数.算法Estimate(n)/估算回溯法生成的结点数1.m1;r1;k1;2.Whilekndo3.SetTypeT=xk/满足约束的可取值集合；4.ifT=thenreturnm;5.r|T|*r;6.mm+r;6.xk随机选择T的元素；7.kk+1;回溯法生成的满足约束条件的结点总数：1+m0+m0m1+m0m1m2+,69,MonteCarlo方法估计四后问题的效率：1+4+42+42*1=211+m0+m0m1+m0m1m2+,70,回溯法小结（1）回溯法的实质是检测所有可能的解，也就是穷尽所有的可能情况，从中寻求问题的答案。因此，其时间复杂度与穷尽法相同。在人工智能中应用回溯法求解时，要用启发信息、启发函数来判断每一个可能的动作，按其函数值的大小将所有可能的动作排成一列。,71,把导致成功可能性大的动作排在前面，于是很可能很快就得到了问题的答案。但回溯法提供了一种规律性求解的方法，一般说来，时间复杂度是比较高的。（2）回溯法可以用来求一个解，也可以用来求出所有的解。,72,课后作业,第三版：算法分析题：5-3，5-5算法实现题（作为分析题）：5-4，5-13，5-18第四版：算法分析题：5-3，5-5算法实现题（作为分析题）：5-4，5-13，5-18,73,习题5-30-1背包问题的最优解重写0-1背包问题的回溯法,使算法运行结束后能输出最优解.提示:为