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

《数据结构与算法---山东大学课程中心30》由会员分享，可在线阅读，更多相关《数据结构与算法---山东大学课程中心30（46页珍藏版）》请在金锄头文库上搜索。

1、复杂问题解法的提示 16.1 回溯算法的思想 16.2 回溯算法的应用 货箱装船 旅行商问题（TSP问题）,Chapter16 回溯,2019/11/2,1,1、寻求问题解的常规思路,首先列出所有候选解 然后依次检查每一个解，直到找到所需的解 【可行性前提】：候选解数量有限，并且能够通过检查所有或部分候选解得到所需的解,2019/11/2,2,示例1：百元百鸡问题,使用枚举法求解：百元买百鸡问题 公鸡每只5元，母鸡每只3元，小鸡3只1元 x+y+z=100 5x+3y+z/3=100 1=x=20，1=y=33 解法：枚举所有满足条件的候选解 缺点：运算量大；改进：找到限定规则,2019/11

2、/2,3,对候选解进行系统检查的常用方法,回溯 分支定界 避免对很大的候选解集合进行检查，同时能够保证算法运行结束可以找到所需要的解； 通常能够用来求解规模很大的问题。,2019/11/2,4,回溯算法思想,回溯算法，也叫试探算法。 是一种系统的搜索问题的解的方法。 【基本思想】从一条路往前走，能进则进，不能进则退回来，换一条路再试。,2019/11/2,5,示例2：n皇后问题,在 n 行 n 列的国际象棋棋盘上，若两个皇后位于同一行、同一列、同一对角线上，则称它们为互相攻击。 【n皇后问题】找到这 n 个皇后的互不攻击的布局。,2019/11/2,6,查找时间与问题规模相关,2019/11/

3、2,7,用回溯算法解决问题的一般步骤,一、定义一个解空间，这个解空间必须至少包含问题的一个解（可能最优）； 二、用易于搜索的方式组织该解空间。典型的组织方式是图（如迷宫）或树（如0/1背包）。 三、按深度优先法从开始节点进行搜索。 四、利用限界函数避免移动到不可能产生解的子空间。,【回溯算法重要特性】问题的解空间通常是在搜索问题的解的过程中动态产生的。,2019/11/2,8,示例：3*3迷宫问题（图16-1）,1、定义解空间： 包含从入口到出口的所有路径； 2、组织解空间： 用图的形式给出。 从点(1,1)到(3,3)的每一条路径都定义了3*3迷宫解空间中的一个元素； 3、搜索解空间： 从开

4、始节点（1，1）进行深度优先搜索。,2019/11/2,9,示例：n个对象的0/1背包问题（图16-2）,1、定义解空间： 2n个长度为n的0/1向量集合； n=3时，解空间(0,0,0),(0,1,0),(0,0,1,(1,0,0),(0,1,1),(1,0,1,(1,1,0),(1,1,1) 2、组织解空间： 用树的形式给出。 第i层到第i+1层节点的一条边上的数字：向量x中第i个分量的值xi； 从根节点到叶节点的每一条路径都定义了解空间中的一个元素。 3、搜索解空间： 开始节点为根节点进行深度优先搜索。,2019/11/2,10,活节点、死节点和E-节点,活节点：开始节点是活节点，也是E

5、-节点。 死节点 E-节点（Expansion Node）及回溯 从E节点可移动到一个新的节点； 如果能从当前节点移动到一个新的节点，则这个新节点将变成一个活节点和新的E-节点；旧的E-节点仍然是个活节点。 如果不能够移到一个新节点，则该E-节点成为死节点，只能返回到最近被考察的活节点（回溯），这个活节点变成新的E-节点。 当已经找到答案或者回溯尽了所有的活节点时，搜索过程结束。,2019/11/2,11,限界函数,通过确定一个新近到达的节点能否导致一个比当前最优解还要好的解，可以加速对最优解的搜索。 如果不能，则移动到该节点的任何一个子树都是无意义的，这个节点可被立即杀死。 用来杀死活节点的

6、策略称为：限界函数（Bounding Function）。,2019/11/2,12,解空间图：3*3迷宫老鼠问题 （P185 程序5-13回溯算法）,寻找从(1，1)到(3，3)的一条路径,左图中，从起点到终点的每一条路径都定义了解空间中的一个元素。,搜索结果： (1,1)-(2,1)-(3,1)-(3,2)-(3,3),2019/11/2,13,解空间树：0/1背包问题,从n个物品中选择装入背包的物品 约束条件：,左图为n=3时的解空间树,n=3时，0/1背包问题的求解过程,w=20,15,15, p=40,25,25, c=30,当前最优: ABEK,最优解: ACFL,【限界函数】杀死

7、代表不可行解决方案的节点。,示例：旅行商问题（TSP）,旅行商需要找到一条从家里出发，访问所有城市后返回原处的旅游环路。 要求：路径最短或耗费最小,2019/11/2,16,旅行商问题的定义,顶点：旅行商所要旅行的城市（包括起点） 边的耗费：给出了在两个城市旅行所需的时间（或花费） 旅行：表示当旅行商游览了所有城市再回到出发点时所走的路线,例如：旅行1-3-2-4-1的耗费为25，最小！,2019/11/2,17,解空间描述：排列树,一个旅行：由树中的一条从根到叶的路径表示。 例如：ABCFL表示旅行1-2-3-4-1 树中叶节点的数目（n-1）!,2019/11/2,18,n=4时，旅行商问

8、题的求解过程,【限界函数】如果目前建立的部分的费用大于或等于当前最佳路径的费用，则杀死当前节点。 例如：到达I时，部分旅行耗费1,3,4的耗费为2625，所以，搜索以I为根节点的子树毫无意义。,2019/11/2,19,回溯算法的解空间形式,子集树：当问题解空间树是n个元素的一个子集时，例如：0/1背包问题 子集树有2n个叶节点，遍历耗时 (2n) 排列树：当问题解空间树是n个元素的一个排列时，例如：旅行商问题 排列树有n!个叶节点，遍历耗时 (n!),2019/11/2,20,回溯算法小结,步骤： 定义一个解空间，它包含问题的解； 用适于搜索的方式组织该空间； 用DFS法搜索该空间，并使用限

9、界函数加速对最优解的搜索，避免不必要的移动 在搜索期间的任何时刻，仅保留从开始节点到当前E节点的路径，因此，回溯算法的空间需求为 O（从开始节点起最长路径的长度）； 解空间的大小是该长度的指数或阶乘！全部存储解空间，不够用。,2019/11/2,21,3、回溯算法的应用,货箱装船问题：子集树 旅行商问题：排列树,2019/11/2,22,（1）货箱装船问题,有两艘船，n个货箱。第一艘船的载重量是c1 ，第二艘船的载重量是c2，Wi是货箱i 的重量且 寻求一种将n个货箱全部装船的方法 例如：当n= 3，c1 =c2 = 50，w=10,40,40；可将货箱1 , 2装到第一艘船上，货箱3装到第二

10、艘船上。 再如：w= 20 , 40 , 40，结果如何？,解决策略,存在一种方法能够装载所有n个货箱时，可以验证以下的装船策略可以获得成功： 1) 尽可能地将第一艘船装至它的重量极限 2) 将剩余货箱装到第二艘船 为了尽可能地将第一艘船装满，需要选择一个货箱的子集，它们的总重量尽可能接近c1,2019/11/2,24,第一种回溯算法,思想：寻找 即寻找 一个重量的子集尽量接近c1。 限界函数：定义 表示节点O的当前重量； 若cwc1，则表示以O为根的子树不能产生一个可行的解答，避免移动。,n=4时，求解过程,w=8，6，2，3， C1=12,cw=8,cw=10,cw=8,cw=11,最优解

11、x: 1,0,0,1,2019/11/2,26,第一种回溯算法-代码分析,Page498：程序16-1 注意：一个可行节点的右孩子总是可行 时间复杂度：O(2n) 递归栈空间：O(n),2019/11/2,27,第二种回溯算法：优化,如果当前节点的右子树不可能包含比当前最优解更好的解时，就不移动到右子树上！ 设bestw为当前最优解，Z为解空间树的第i 层的一个节点 限界函数： 为剩余货箱的重量； 当cw+r=bestw时，没有必要去搜索Z 的右子树 Page499：程序16-2,寻找最优子集,Page500：程序16-3 引入bestx，记录当前找到的最优货箱子集 时间复杂度：O(n2n)

12、降低复杂度的两种方法：Page501,2019/11/2,29,（2）旅行商问题,解空间是排列树 可采用Page8的Perm函数，产生n个元素表的所有排列,作为类AdjacencyWDigraph的成员,2019/11/2,30,使用递归函数生成排列（P7 例1-3）,【例】a,b,c的排列方式有：abc，acb，bac，bca，cab，cba。共6种（n个元素的排列方式共有n！种）,令Ee1，en表示n个元素的集合。 令Ei为移去元素i后所得的集合， perm(X)表示集合X中元素的排列方式， ei.perm(X)表示在perm(X)中的每个排列方式的前面均加上ei以后所得到的排列方式。 例

13、如，若E=a,b,c，则E1=b,c,perm(E1)=bc,cb, e1.perm(E1)=abc,acb,2019/11/2,31,使用递归函数生成排列（P7 例1-3）,【递归出口】n=1。当只有一个元素时，只可能产生一种排列方式，即perm(E)=e，其中e是E中唯一的元素。,当n1时，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.per

14、m(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),2019/11/2,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/11/2,33,使用递归函数生成排列（程序1-10）,template void P

15、erm(T list, int k, int m) / Generate all permutations of listk:m. int i; if (k = m) / 输出一个排列方式 for (i = 0; i = m; i+) cout listi; cout endl; ,2019/11/2,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/11/2,35,预处理程序：TSP,template T AdjacencyWDigraph: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/11/2,36,tSP函数,结构与Perm函数相同。