数据结构与算法---山东大学课程中心30ppt课件

2020/5/11,.,1,复杂问题解法的提示16.1回溯算法的思想16.2回溯算法的应用货箱装船旅行商问题（TSP问题）,Chapter16回溯,2020/5/11,.,2,1、寻求问题解的常规思路,首先列出所有候选解然后依次检查每一个解，直到找到所需的解【可行性前提】：候选解数量有限，并且能够通过检查所有或部分候选解得到所需的解,2020/5/11,.,3,示例1：百元百鸡问题,使用枚举法求解：百元买百鸡问题公鸡每只5元，母鸡每只3元，小鸡3只1元x+y+z=1005x+3y+z/3=1001=x=20，1c1，则表示以O为根的子树不能产生一个可行的解答，避免移动。,2020/5/11,.,26,n=4时，求解过程,w=8，6，2，3，C1=12,cw=8,cw=10,cw=8,cw=11,最优解x:1,0,0,1,2020/5/11,.,27,第一种回溯算法-代码分析,Page498：程序16-1注意：一个可行节点的右孩子总是可行时间复杂度：O(2n)递归栈空间：O(n),第二种回溯算法：优化,如果当前节点的右子树不可能包含比当前最优解更好的解时，就不移动到右子树上！设bestw为当前最优解，Z为解空间树的第i层的一个节点限界函数：为剩余货箱的重量；当cw+r1时，perm(E)=e1.perm(E1)+e2.perm(E2)+e3.perm(E3)+en.perm(En)即采用n个perm(X)来定义perm(E)，其中每个X包含n-1个元素。【例】当n=3，并且E=a，b，c则，perm(E)=a.perm(b,c)+b.perm(a,c)+c.perm(a,b)perm(b,c)=b.perm(c)+c.perm(b)a.perm(b,c)=ab.perm(c)+ac.perm(b)=ab.c+ac.b=(abc,acb),2020/5/11,.,33,使用递归函数生成排列（P7例1-3）,a.perm(b,c)包含两个排列式：abc和acb，a是它们的前缀，perm(b,c)是它们的后缀同样，ac.perm(b)表示前缀ac，后缀为perm(b)的排列方式。,程序1-10输出所有前缀为list0:k-1，后缀为listk,m的排列方式。,2020/5/11,.,34,使用递归函数生成排列（程序1-10）,templatevoidPerm(Tlist,intk,intm)/Generateallpermutationsoflistk:i;if(k=m)/输出一个排列方式for(i=0;i=m;i+)coutlisti;coutendl;,2020/5/11,.,35,使用递归函数生成排列（程序1-10）,else/listk:mhasmorethanonepermutation/generatetheserecursivelyfor(i=k;i=m;i+)Swap(listk,listi);Perm(list,k+1,m);Swap(listk,listi);,2020/5/11,.,36,预处理程序：TSP,templateTAdjacencyWDigraph:TSP(intv)x=newintn+1;保存到当前节点的路径for(inti=1;i=n;i+)xi=i;bestc=NoEdge;bestx=v;保存最优解路径cc=0;tSP(2);搜索x2:n的各种排列deletex;returnbestc;返回最优解耗费,2020/5/11,.,37,tSP函数,结构与Perm函数相同。当i=n时，处在排列树的叶节点的父节点上，并且需要验证从xn-1到xn有一条边，从xn到起点x1也有一条边。若两边都存在，则发现一个新旅行。若发现的旅行是目前发现的最优旅行，则将旅行和它的耗费分别存入bestx和bestc中。当in时，检查当前i-1层节点的孩子节点，并且仅当以下情况出现时，移动到孩子节点之一：（1）有从xi-1到xi的一条边（如果是的话，x1:i定义了网络中的一条路径）；（2）路径x1:i的耗费小于当前的最优解的耗费.变量cc保存目前所构造的路径的耗费。,2020/5/11,.,38,迭代回溯算法：tSP,templateaNN表示两个节点之间是否有边voidAdjacencyWDigraph:tSP(inti)if(i=n)位于叶子节点的父节点if(axn-1xn!=NoEdge,2020/5/11,.,39,迭代回溯算法：tSPcont.,elsefor(intj=i;j=n;j+)判断是否能移到子树xjif(axi-1xj!=NoEdge,2020/5/11,.,40,本章小结,回溯算法的基本思想限界函数的使用回溯算法的应用货箱装船旅行商问题,2020/5/11,.,41,复杂问题解法的提示,很多情况下，我们需要找到某个问题的候选集的一个子集或者一种排列这些求解过程通常需要满足一定的约束条件，并且要优化一些目标函数通常解法：将解空间组织成一棵树，并通过对这棵树的系统性搜索，以获取问题的解,2020/5/11,.,42,子集问题,求解过程是寻找n个元素的一个子集子集必须满足一定约束条件，并且尽可能地优化某些目标函数应用示例PartitionSubsetsum0/1背包Satisfiability(findsubsetofvariablestobesettotruesothatformulaevaluatestotrue).,2020/5/11,.,43,子集问题的解空间,当要求解的问题需要根据n个元素的一个子集来优化某些函数时，解空间树被称作子集树（SubsetTree）。对有n个对象的0/1背包问题来说，它的解空间就是一个子集树。一棵树有2n个叶节点，全部节点有2n+1-1个。每一个对树中所有节点进行遍历的算法都必须耗时(2n)。,2020/5/11,.,44,排列问题,求解过程是寻找n个元素的一个排列排列必须满足一定约束条件，并且尽可能地优化某些目标函数应用示例TSP：旅