《算法设计与分析Chapter5Veron》由会员分享，可在线阅读，更多相关《算法设计与分析Chapter5Veron（61页珍藏版）》请在金锄头文库上搜索。
1、回溯法（穷举法）,Veron,学习要点,理解回溯法的深度优先搜索策略 掌握用回溯法解题的算法框架 （1）递归回溯 （2）迭代回溯 （3）子集树回溯 （4）排列树回溯,学习要点,通过应用范例学习回溯法的设计策略 （1）装载问题； （2）批处理作业调度； （3）符号三角形问题 （4）n后问题； （5）0-1背包问题； （6）最大团问题； （7）图的m着色问题 （8）旅行售货员问题,回溯法基础,回溯法,用来搜索问题解空间的方法 可以枚举问题的所有解 通用解题法 深度优先搜索 可以解决 搜索问题的一个可行解 搜索到第一个可行解则停止搜索 搜索问题的最优解 遍历解空间找到最优解,回溯法,定义问题的解空间
2、 搜索解空间,0-1背包问题,0-1背包问题,形式化描述 输入：, , 和C 输出： (x1, x2, , xn)，xi0, 1满足 优化目标： 等价于整数规划问题,0-1背包问题,实例 物品个数为 n=3 背包的容量为 C=30 物品的重量分别为 w=16，15，15 物品的价值分别为 v=45，25，25 解空间 (x1, x2, x3)的所有可能取值 (0,0,0), (0,1,0), (0,0,1), (1,0,0), (0,1,1), (1,0,1), (1,1,0), (1,1,1),0-1背包问题,解空间树,0-1背包问题,搜索解空间（深度优先）,w=16，15，15 v=45，
3、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,0-1背包问题,剪枝策略 剪去不可行的子树,0-1背包问题,子集树 从n个元素的集合S中找出满足某种性质的子集，相应的解空间树称为子集树 子集树搜索代价 叶节点数量为2n，节点总数为2n +1-1 遍历解空间需要 W(2n),0-1背包问题,递归算法 void Backtrack(int t)
4、if (tn) 输出x； else for(i=0; i=1; i+) xt=i; if (所有已选物品的重量C) Backtrack(t+1)； ,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-; ,0-1背包问题,最优解上界 不过超过一般背包问题的最优解 每种物品可以只取一部分 一般背包问题的最优解 将物品按照单位重量的价值排序 先装价重比最高的物品，知道背包装
5、满为止 最后一个物品可以只装一部分,背包问题最优解,17,实例,背包问题最优解,0-1背包问题,回溯法改进 将所有物品按照价重比排序 设当前背包中所有物品的价值为P，背包剩余容量为C，剩余物品为i, , n 那么装入背包的最大价值不会超过bound(i) bound(i)PX X是针对输入i, , n和C的背包问题的最优解,0-1背包问题,回溯法改进 bestp保存当前的最优解的价值,void Backtrack(int t) if (tn) if (当前解x的代价bestp) 更新bestp; 输出x; else for(i=0; ibestp) Backtrack(t+1)； ,旅行商问题
6、,旅行商问题,输入 完全无向带权图G=(V, E) |V|=n, |E|=m 对于E中的某条边e，其长度为c(e) 输出 最短的哈密尔顿回路 经过每个节点一次且仅一次的回路,NP难问题,旅行商问题,实例 解空间 1,2,4,3,1 1,3,2,4,1 1,4,3,2,1 共(n-1)!个,旅行商问题,解空间树,旅行商问题,回溯法,最优解: (1,2,3,4,1)，代价=59,最优解: (1,3,2,4,1)，代价=25,旅行商问题,剪枝策略 如果当前搜索节点处的代价超过已找到的最优解代价，剪去其子树,旅行商问题,排列树 问题的解是n个元素满足某种性质的排列时，解空间树称为排列树 排列数搜索代价
7、 叶节点n! 遍历解空间需要 W(n!),旅行商问题,递归算法 初始时：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); ,旅行商问题,迭代算法 /yt记录xt选择了t到n中的哪个元素,初始时yt=t void IterativeBacktrack( ) int t=1; while(t0) if(tn) 输出x; t-; continue; swap(xt, xyt);
8、yt+; if(ytn) t-; else swap(xt, xyt); if(现有路径长度小于已得到的最优值) t+; yt=t; else t-; ,回溯法算法框架,回溯法搜索子集树,void Backtrack(int t) if (tn) 输出x； else for(i=0; i=1; i+) xt=i; if (Constraint(t) & Bound(t) /如果当前的部分解可行 且 可能产生最优解 Backtrack(t+1)； ,回溯法搜索排列树,初始时：xn=（1,2,3,n） void Backtrack(int t) if (tn) 输出x； else for(i=t;
9、 i=n; i+) Swap(xt, xi); if (Constraint(t) ,回溯法总结,剪枝策略 用约束函数 Constraint(t) 剪去不可行子树 用限界函数 Bound(t) 剪去得不到最优解的子树 时间复杂性 搜索子集树W(2n) 搜索排列数W(n!) 空间复杂性 O(h(n) h(n)为解空间树的高度,装载问题,装载问题,输入 n个集装箱，其中集装箱i的重量为wi 载重量分别为C1和C2的轮船 输出 （是否有）合理的装载方案将所有集装箱装上船,NP难问题 当 时，等价于子集合问题,装载问题,如果有解，可以用以下方法获得 将第一艘轮船尽可能装满 然后将剩余的集装箱装上第二艘
10、轮船 问题等价于,s.t.,特殊的0-1背包问题：每种物品的价值等于重量,装载问题,解空间树 子集树,装载问题,回溯法（搜索子集树）,void Backtrack(int t) if (tn) 输出x； else for(i=0; i=1; i+) xt=i; if (Constraint(t) & Bound(t) /如果当前的部分解可行 且 可能产生最优解 Backtrack(t+1)； ,装载问题,剪枝 约束函数 Constraint(t)： 限界函数 Bound(t) ：,回溯法 时间复杂性：O(2n) 空间复杂性：O(n),批处理作业调度,批处理作业调度,输入 n个作业1, , n
11、两台机器（M1和M2） 作业 i 在M1和M2上的处理时间分别为 ai 和 bi 每个作业必须现由M1处理，再由M2处理 输出 作业调度方案使得总等待时间最小 作业 i在M1和M2上的完成时间分别为 Ai 和 Bi 总等待时间为,批处理作业调度,可能的调度方案 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,A2=7,批处理作业调度,计算调度J1, J2, , Jn的等待时间 计算BJi 计算AJi=AJi-1 + aJi
12、 比较AJi和BJi1 BJi较大者 + bJi,批处理作业调度,解空间树 排列树,批处理作业调度,回溯法（搜索排列树）,初始时：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!) 空间复杂性：O(n),批处理作业调度,剪枝 限界函数 Bound(t)：,n后问题,n后问题,输入 nn的棋盘 n个皇后 输出 n个皇后的放置
13、方案 任意两个皇后都不在同一行、同一列或同一斜线上,n后问题,解空间 每行有且仅有一个皇后 用xi表示第i行皇后位于第几列 此皇后的坐标为(i, xi) 问题的解是x1, n，满足 任意两个皇后不在同一列上：xixj 任意两个皇后不在同一斜线上 |i j| |xi xj| x1, , n是1, , n的一个排列,解空间树：排列树,n后问题,回溯法,初始时：xn=（1,2,3,n） void Backtrack(int t) if (tn) 输出x； else for(i=t; i=n; i+) Swap(xt, xi); if ( Constraint(t) ) Backtrack(t+1)
14、； Swap(xt, xi); ,n后问题,剪枝 约束函数 Constraint(t) for (i=1; it; i+) if(|i t| = |xi xt| ) return false; return true; ,回溯法 时间复杂性：O(n*n!) 空间复杂性：O(n),图的m着色问题,图的m着色问题,输入 无向连通图G m种颜色 输出 顶点着色方案 任意两个相邻顶点都有不同颜色,图的m着色问题,解空间 xi表示顶点i的颜色 xi1, , m 每个xi有m种不同取值 x1,n有mn种不同取值,图的m着色问题,解空间树(m=3) 类似于子集树，每个xi有m个取值,图的m着色问题,回溯法,
15、void Backtrack(int t) if (tn) 输出x； else for(i=1; i=m; i+) xt=i; if (Constraint(t) Backtrack(t+1)； ,图的m着色问题,剪枝 约束函数 Constraint(t) for (i=1; it; i+) if(存在(i, t)且xi=xt) return false; return true; ,回溯法 时间复杂性：O(n*mn) 空间复杂性：O(n),回溯法效率分析,回溯法效率分析,回溯法的效率取决于 解空间中解的数量 即满足显约束的x1, n的值的个数 计算约束函数Constraint(t)所需时间 计算限界函数Bound(t)所需时间 满足约束函数和限界函数的解的数量 x1,n的选取顺序,回溯法效率分析,好的约束（限界）函数能显著地减少所生成的结点数。但这样的约束（限界）函数往往
