《算法课件2015第5章回溯法》由会员分享，可在线阅读，更多相关《算法课件2015第5章回溯法（55页珍藏版）》请在金锄头文库上搜索。
1、1,第5章 回溯法（穷举法）,马志强,2,学习要点,理解回溯法的深度优先搜索策略 掌握用回溯法解题的算法框架 （1）递归回溯 （2）迭代回溯 （3）子集树回溯 （4）排列树回溯,3,学习要点,通过应用范例学习回溯法的设计策略 （1）装载问题； （2）批处理作业调度； （3）符号三角形问题 （4）n后问题； （5）0-1背包问题； （6）最大团问题； （7）图的m着色问题 （8）旅行售货员问题,4,实例 哈尔滨走到罗马 若完全不认识路，会怎样走,回溯法,两类问题 存在性问题 优化问题,5,回溯法,实例罗密欧与朱丽叶问题 迷宫是一些互相连通的交叉路口的集合，给定一个入口、一个出口。当从入口到出口存
2、在通路时，输出选中的一条通路；否则，输出无通路存在。,(a) 交叉路口,路口动作结果 1向前进入2 2向左进入3 3向右进入4 4（死路）回溯进入3 3（死路）回溯进入2 2向前进入5 5（死路）回溯进入2 2向右进入6 6向左进入7,(b)搜索过程,6,针对所给问题，定义问题的解空间； 确定易于搜索的解空间结构； 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。,常用剪枝函数 用约束函数在扩展结点处剪去不满足约束的子树； 用限界函数剪去得不到最优解的子树。,回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。 适用于解一些组合数相当大的问题，具有“通用解题法”之称,回
3、溯法的基本思想,7,0-1背包问题,形式化描述 输入：, , 和C 输出： (x1, x2, , xn)，xi0, 1满足 优化目标： 等价于整数规划问题,8,0-1背包问题,实例 物品个数为 n=3 背包的容量为 C=30 物品的重量分别为 w=16，15，15 物品的价值分别为 v=45，25，25 解空间 (x1, x2, x3)的所有可能取值 (0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1),9,0-1背包问题,解空间树,10,0-1背包问题,搜索解空间（深度优先）,w=16，15，15 v=4
4、5，25，25 物品重量小于30 最大化物品价值,: W=0,x1=1: W=16,x2=1: W=31,x2=0: W=16,x3=1: W=31,x3=0: W=16,最优解: (1,0,0)，V=45,x1=0: W=0,x2=1: W=15,x3=1: W=30,最优解: (0,1,1)，V=50,11,0-1背包问题,剪枝策略 剪去不可行的子树,12,0-1背包问题,子集树 从n个元素的集合S中找出满足某种性质的子集，相应的解空间树称为子集树 子集树搜索代价 叶节点数量为2n，节点总数为2n +1-1 遍历解空间需要 W(2n),13,0-1背包问题,递归算法 void Backtr
5、ack(int t) if (tn) 输出x； else for(i=0; i=1; i+) xt=i; if (所有已选物品的重量C) Backtrack(t+1)； ,14,0-1背包问题,迭代算法 void IterativeBacktrack( ) int t=1; for (i=1; i0) if (tn) 输出x; t-; continue; xt+; if (xt1) t-; else if (已选物品重量小于C) t+; else t-; ,15,0-1背包问题,最优解上界 不过超过一般背包问题的最优解 每种物品可以只取一部分 一般背包问题的最优解 将物品按照单位重量的价值排序
6、 先装价重比最高的物品，直到背包装满为止 最后一个物品可以只装一部分,16,0-1背包问题,实例,背包问题最优解,17,0-1背包问题,回溯法改进 将所有物品按照价重比排序 设当前背包中所有物品的价值为P，背包剩余容量为C，剩余物品为i, , n 那么装入背包的最大价值不会超过bound(i) bound(i)PX X是针对输入i, , n和C的背包问题的最优解,18,0-1背包问题,回溯法改进 bestp保存当前的最优解的价值,void Backtrack(int t) if (tn) if (当前解x的代价bestp) 更新bestp; 输出x; else for(i=0; ibestp)
7、 Backtrack(t+1)； ,19,旅行商问题,输入 完全无向带权图G=(V, E) |V|=n, |E|=m 对于E中的某条边e，其长度为c(e) 输出 最短的哈密尔顿回路 经过每个节点一次且仅一次的回路,NP难问题,20,旅行商问题,解空间树,21,旅行商问题,实例 解空间 1,2,4,3,1 1,3,2,4,1 1,4,3,2,1 共(n-1)!个,22,旅行商问题,回溯法,最优解: (1,2,3,4,1)，代价=59,最优解: (1,3,2,4,1)，代价=25,23,旅行售货员问题,剪枝策略 如果当前搜索节点处的代价超过已找到的最优解代价，剪去其子树,24,旅行售货员问题,排列
8、树 问题的解是n个元素满足某种性质的排列时，解空间树称为排列树 排列数搜索代价 叶节点n! 遍历解空间需要 W(n!),25,旅行售货员问题,递归算法 初始时：xn=（1,2,3,n） void Backtrack(int t) if (tn) 输出x； else for(i=t; i=n; i+) Swap(xt, xi); if (现有路径长度小于已得到的最优值) Backtrack(t+1) ； Swap(xt, xi); ,26,旅行售货员问题,迭代算法 /yt记录xt选择了t到n中的哪个元素,初始时yt=t void IterativeBacktrack( ) int t=1; wh
9、ile(t0) if(tn) 输出x; t-; continue; swap(xt, xyt); yt+; if(ytn) t-; else swap(xt, xyt); if(现有路径长度小于已得到的最优值) t+; yt=t; else t-; ,27,回溯法搜索子集树,void Backtrack(int t) if (tn) 输出x； else for(i=0; i=1; i+) xt=i; if (Constraint(t) & Bound(t) /如果当前的部分解可行 且 可能产生最优解 Backtrack(t+1)； ,28,回溯法搜索排列树,初始时：xn=（1,2,3,n） v
10、oid Backtrack(int t) if (tn) 输出x； else for(i=t; i=n; i+) Swap(xt, xi); if (Constraint(t) ,29,回溯法总结,剪枝策略 用约束函数 Constraint(t) 剪去不可行子树 用限界函数 Bound(t) 剪去得不到最优解的子树 时间复杂性 搜索子集树W(2n) 搜索排列数W(n!) 空间复杂性 O(h(n) h(n)为解空间树的高度,30,装载问题,输入 n个集装箱，其中集装箱i的重量为wi 载重量分别为C1和C2的轮船 输出 （是否有）合理的装载方案将所有集装箱装上船,NP难问题 当 时，等价于子集合问
11、题,31,装载问题,如果有解，可以用以下方法获得 将第一艘轮船尽可能装满 然后将剩余的集装箱装上第二艘轮船 问题等价于,s.t.,特殊的0-1背包问题：每种物品的价值等于重量,32,装载问题,解空间树 子集树,33,装载问题,回溯法（搜索子集树）,void Backtrack(int t) if (tn) 输出x； else for(i=0; i=1; i+) xt=i; if (Constraint(t) & Bound(t) /如果当前的部分解可行 且 可能产生最优解 Backtrack(t+1)； ,34,装载问题,剪枝 约束函数 Constraint(t)： 限界函数 Bound(t)
12、 ：,回溯法 时间复杂性：O(2n) 空间复杂性：O(n),35,批处理作业调度,输入 n个作业1, , n 两台机器（M1和M2） 作业 i 在M1和M2上的处理时间分别为 ai 和 bi 每个作业必须现由M1处理，再由M2处理 输出 作业调度方案使得总等待时间最小 作业 i在M1和M2上的完成时间分别为 Ai 和 Bi 总等待时间为,36,批处理作业调度,可能的调度方案 123，132，213， 231，312，321 最佳方案是132（总等待时间：18）,M1,M2,Job 1,Job 1,B1=3,Job 3,Job 3,B3=7,Job 2,Job 2,B2=8,A1=2,A3=4,
13、A2=7,37,批处理作业调度,计算调度J1, J2, , Jn的等待时间 计算BJi 计算AJi=AJi-1 + aJi 比较AJi和BJi1 BJi较大者 + bJi,38,批处理作业调度,解空间树 排列树,39,批处理作业调度,回溯法（搜索排列树）,初始时：xn=（1,2,3,n） void Backtrack(int t) if (tn) 输出x； else for(i=t; i=n; i+) Swap(xt, xi); if (Bound(t) /如果当前的部分解可行 且 可能产生最优解 Backtrack(t+1) ； Swap(xt, xi); ,时间复杂性：O(n!) 空间复杂
14、性：O(n),40,批处理作业调度,剪枝 限界函数 Bound(t)：,41,n后问题,输入 nn的棋盘 n个皇后 输出 n个皇后的放置方案 任意两个皇后都不在同一行、同一列或同一斜线上,42,n后问题,解空间 每行有且仅有一个皇后 用xi表示第i行皇后位于第几列 此皇后的坐标为(i, xi) 问题的解是x1, n，满足 任意两个皇后不在同一列上：xixj 任意两个皇后不在同一斜线上 |i j| |xi xj| x1, , n是1, , n的一个排列,解空间树：排列树,43,n后问题,回溯法,初始时：xn=（1,2,3,n） void Backtrack(int t) if (tn) 输出x；
15、 else for(i=t; i=n; i+) Swap(xt, xi); if ( Constraint(t) ) Backtrack(t+1) ； Swap(xt, xi); ,44,n后问题,剪枝 约束函数 Constraint(t) for (i=1; it; i+) if(|i t| = |xi xt| ) return false; return true; ,回溯法 时间复杂性：O(n*n!) 空间复杂性：O(n),45,图的m着色问题,给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。这个问题是图的m可着色判定问题。,若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。,46,图的m着色问题,实例 5顶点，3着色,解向量：(x1, x2, x3, x4 , x5)
