数据结构与算法.ppt

《数据结构与算法.ppt》由会员分享，可在线阅读，更多相关《数据结构与算法.ppt（45页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、复杂问题解法的提示16.1 回溯算法的思想 16.2 回溯算法的应用货箱装船旅行商问题（TSP问题）,Chapter16 回溯,2019/10/23,1,1、寻求问题解的常规思路,首先列出所有候选解然后依次检查每一个解，直到找到所需的解【可行性前提】：候选解数量有限，并且能够通过检查所有或部分候选解得到所需的解,2019/10/23,2,示例1：百元百鸡问题,使用枚举法求解：百元买百鸡问题公鸡每只5元，母鸡每只3元，小鸡3只1元x+y+z=1005x+3y+z/3=1001=x=20，1=y25，所以，搜索以I为根节点的子树毫无意义。,2019/10/23,19,回溯算法的解空间形式,子集树：

2、当问题解空间树是n个元素的一个子集时，例如：0/1背包问题子集树有2n个叶节点，遍历耗时 (2n) 排列树：当问题解空间树是n个元素的一个排列时，例如：旅行商问题排列树有n!个叶节点，遍历耗时 (n!),2019/10/23,20,回溯算法小结,步骤： 定义一个解空间，它包含问题的解； 用适于搜索的方式组织该空间； 用DFS法搜索该空间，并使用限界函数加速对最优解的搜索，避免不必要的移动在搜索期间的任何时刻，仅保留从开始节点到当前E节点的路径，因此，回溯算法的空间需求为O（从开始节点起最长路径的长度）；解空间的大小是该长度的指数或阶乘！全部存储解空间，不够用。,2019/10/23,21,3、

3、回溯算法的应用,货箱装船问题：子集树旅行商问题：排列树,2019/10/23,22,（1）货箱装船问题,有两艘船，n个货箱。第一艘船的载重量是c1 ，第二艘船的载重量是c2，Wi是货箱i 的重量且 寻求一种将n个货箱全部装船的方法例如：当n= 3，c1 =c2 = 50，w=10,40,40；可将货箱1 , 2装到第一艘船上，货箱3装到第二艘船上。再如：w= 20 , 40 , 40，结果如何？,解决策略,存在一种方法能够装载所有n个货箱时，可以验证以下的装船策略可以获得成功： 1) 尽可能地将第一艘船装至它的重量极限2) 将剩余货箱装到第二艘船为了尽可能地将第一艘船装满，需要选择一个货箱的子

4、集，它们的总重量尽可能接近c1,2019/10/23,24,第一种回溯算法,思想：寻找 即寻找一个重量的子集尽量接近c1。限界函数：定义 表示节点O的当前重量；若cwc1，则表示以O为根的子树不能产生一个可行的解答，避免移动。,n=4时，求解过程,w=8，6，2，3， C1=12,cw=8,cw=10,cw=8,cw=11,最优解x: 1,0,0,1,2019/10/23,26,第一种回溯算法-代码分析,Page498：程序16-1注意：一个可行节点的右孩子总是可行时间复杂度：O(2n) 递归栈空间：O(n),2019/10/23,27,第二种回溯算法：优化,如果当前节点的右子树不可能包含比当

5、前最优解更好的解时，就不移动到右子树上！设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.

6、b=(abc,acb),2019/10/23,32,使用递归函数生成排列（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的排列方式。,2019/10/23,33,使用递归函数生成排列（程序1-10）,templatevoid Perm(T list, int k, int m)/ Generate all permutations of listk:m. int i; if (k =

7、m) / 输出一个排列方式 for (i = 0; i = m; i+) cout listi; cout endl; ,2019/10/23,34,使用递归函数生成排列（程序1-10）,else / listk:m has more than one permutation / generate these recursively for (i = k; i = m; i+) Swap(listk, listi); Perm(list, k+1, m); Swap(listk, listi); ,2019/10/23,35,预处理程序：TSP,templateT AdjacencyWDigr

8、aph:TSP(int v ) x = new int n+1; 保存到当前节点的路径 for (int i = 1; i = n; i+) xi = i; bestc = NoEdge; bestx = v; 保存最优解路径 cc = 0; tSP(2); 搜索x2:n的各种排列 delete x; return bestc; 返回最优解耗费,2019/10/23,36,tSP函数,结构与Perm函数相同。当i=n时，处在排列树的叶节点的父节点上，并且需要验证从xn-1到xn有一条边，从xn到起点x1也有一条边。若两边都存在，则发现一个新旅行。若发现的旅行是目前发现的最优旅行，则将旅行和它的

9、耗费分别存入bestx和bestc中。当in时，检查当前i-1层节点的孩子节点，并且仅当以下情况出现时，移动到孩子节点之一：（1）有从xi-1到xi的一条边（如果是的话，x1:i定义了网络中的一条路径）；（2）路径x1:i的耗费小于当前的最优解的耗费.变量cc保存目前所构造的路径的耗费。,2019/10/23,37,迭代回溯算法：tSP,template aNN表示两个节点之间是否有边void AdjacencyWDigraph:tSP(int i) if (i = n) 位于叶子节点的父节点 if (axn-1xn != NoEdge ,2019/10/23,38,迭代回溯算法：tSP co

10、nt.,else for (int j = i; j = n; j+) 判断是否能移到子树xj if (axi-1xj != NoEdge ,2019/10/23,39,本章小结,回溯算法的基本思想限界函数的使用回溯算法的应用货箱装船旅行商问题,2019/10/23,40,复杂问题解法的提示,很多情况下，我们需要找到某个问题的候选集的一个子集或者一种排列这些求解过程通常需要满足一定的约束条件，并且要优化一些目标函数通常解法：将解空间组织成一棵树，并通过对这棵树的系统性搜索，以获取问题的解,2019/10/23,41,子集问题,求解过程是寻找n个元素的一个子集 子集必须满足一定约束条件，并且尽可

11、能地优化某些目标函数应用示例PartitionSubset sum0/1背包Satisfiability (find subset of variables to be set to true so that formula evaluates to true).,2019/10/23,42,子集问题的解空间,当要求解的问题需要根据n个元素的一个子集来优化某些函数时，解空间树被称作子集树（Subset Tree）。对有n个对象的0/1背包问题来说，它的解空间就是一个子集树。一棵树有2n个叶节点，全部节点有2n+1-1个。每一个对树中所有节点进行遍历的算法都必须耗时(2n)。,2019/10/23,43,排列问题,求解过程是寻找n个元素的一个排列排列必须满足一定约束条件，并且尽可能地优化某些目标函数应用示例TSP：旅行商问题N-皇后问题,2019/10/23,44,排列问题的解空间,当要求解的问题需要根据一个n个元素的排列来优化某些函数时，解空间树被称作排列树（Permutation Tree）。这样的树有n!个叶节点；所以每一个遍历树中所有节点的算法都必须耗时(n!)。,2019/10/23,45,