《算法设计与分析-5讲述》由会员分享，可在线阅读，更多相关《算法设计与分析-5讲述（128页珍藏版）》请在金锄头文库上搜索。
1、第第5 5章章 回溯法回溯法 学习要点 回溯法中的深度优先搜索策略 回溯法算法框架 （1）递归回溯 （2）迭代回溯 （3）子集树算法框架 （4）排列树算法框架 应用范例 （1）装载问题； （2） n后问题； （3）图的m着色问题 （5）旅行商问题 略 （1）最大团问题； （2）批处理作业调度； （3） 0-1背包问题； （4）符号三角形问题 特点 n一种通用问题求解策略 1. 实用性广，可求解任意类型问题，对问题本 身不做特殊要求 vs 贪心策略：要求问题满足最优子结构性 质、贪心选择性质 2. 问题求解效率有可能不高，计算代价大 3. 有时无法求得最优解问题规模较大时， 只能得到近似最优解
2、e.g. 旅行商问题 5.1 算法框架 回溯法基本原理如下 n 1. 利用某种数据结构形式化地表示问题解 e.g.1 n个物品的最优0-1背包问题： n个物品，重量,价值,背包容量C ，问题解表示为长度为n的0-1向量 e.g.2 旅行商问题 n个城市组成的带权无向图G=(V,E)，顶点V对应于城市，边E 对应于城市间路径，要求找出一条旅行线路，每个城市只经 历一次，且总路径长度最短 问题解/周游路径： n+1维向量，向量中元素为依次 经历的城市，例如 n2. 问题各种解组成了问题解空间最优解、次优解/可行解 、错误/不可行解、部分解 e.g. 最优解: , ，路径长度=25 次优解/可行解:
3、 ，路径长度=59 错误/不可行解：, , 部分解： , 1 3 2 4 30 610 20 5 4 问题解应满足的条件称为约束，包括 1）显约束：对解空间中分量xi的取值限定 e.g. 0-1背包为题xi只能取0、1 2）隐约束：为满足问题的解而对不同分量之间施加的 约束 e.g. 背包问题中，放入包中的物品总重量不能超过C 旅行商问题中，每个城市只能经过一次 n3. 解空间中各个解根据相互间关系和解的构造顺序，组成 解空间树 叶结点对应1个可行解; 非叶节点代表部分解,表示解的构造过 程 e.g.1 3种物品的0-1背包问题，解表示, 解空间 , , , , , , , , , 根据背包容
4、量和各个物体重量，可判断上述各个解的性质 ：最优、次优、不可行解、部分解 A B DE C FG HIJKLMNO 1 1 11 1 11 0 0 0 0 00 1）共有n+1层， 2）第i到第i+1层的编号给出了对第i个物品的安排, i=1,2,.,n 3) 非叶结点对应部分解 4）叶节点对应最优解、可行解、不可行解 e.g.2 4个城市的旅行商问题 B C F E L 2 3 4 4 A 1 G M 3 4 D H N 2 4 I O 2 4 3 H N 2 3 I O 2 3 第1步 第2步 第3步 第4步 1） 非叶结点对应部分解 2）叶节点对应最优解、可行解 n4. 对解空间中的解，
5、引入定量指标，作为优 化依据 e.g.1 0-1背包问题：放入背包中的物品价值最 大化 e.g.2 旅行商问题：旅游路径总长最短 n5. 解的构造过程 1）以深度优先的方式，从树根结点开始，依次扩展树结点， 直到达到叶结点搜索过程中动态产生解空间 深度优先目的：尽可能快地获得可行解 e.g. B C F E L 2 3 4 4 A 1 G M 3 4 D H N 2 4 I O 2 4 3 H N 2 3 I O 2 3 第1步 第2步 第3步 第4步 n2）扩展过程中，碰到可行非叶结点（部分解），可进一步扩 展 e.g. 结点C对应部分解 可进一步扩展为: F= G= B C F E L 2
6、 3 4 4 A 1 G M 3 4 D H N 2 4 I O 2 4 3 H N 2 3 I O 2 3 3）碰到不可行非叶/叶结点（不可行（部分）解），需要返回 到上一层结点回溯 e.g. 对C结点，下一步的扩展有 4种可能选择：3、4、1、2，每种选 择都可以继续扩展子树； 但只有其中2种选择 是合理的，对后2种选择 不再继续扩展， 而是返回C结点 4 B C F E L 2 3 4 A 1 G M 3 4 1 2 H N 2 3 I O 2 3 4）为了提高搜索效率，用剪枝函数（面向具体问题）避免无效 搜索，即避免不可行解对应的子树或结点 n6. 问题求解过程体现为对解空间的带有回溯
7、 的深度优先树搜索。 从算法实现角度，可采用2种回溯控制策略： 1. 递归回溯： P141算法描述 2. 迭代回溯： P142算法描述 递归回溯递归回溯 回溯法对解空间作深度优先搜索，因此，在一般情况下用 递归方法实现回溯法。 1）t: 递归深度，当前解在解空间树中深度. E.g. 结点B, t=2 2） f(n,t)、 g(n,t)：当前扩展结点处未搜索的子树的起始编号、终止编号 3） h(i): 当前扩展结点处的第i个可选值，e.g. h(i)=C, D, E 4） constraint(t): 当前扩展结点处的约束函数，e.g. 不允许城市重复出现；判断 当前结点是否满足约束，决定是否舍
8、弃当前结点对应分支 5）bound(t): 当前扩展结点的限界函数； 判断当前结点是否越界，决定是否舍 弃当前结点对应分支 B C F E L 2 3 4 4 A 1 G M 3 4 D H N 2 4 I O 2 4 3 H N 2 3 I O 2 3 第1步 第2步 第3步 第4步 旅行商问题 void backtrack (int t) /假设t=2，对应于结点B与 其部分解 if (tn) output(x); else for (int i=f(n,t);i0) if (f(n,t)=g(n,t) /* t=1时，f(n,1)=g(n,1)=起始城市1, 只能选起始城市 for (i
9、nt i=f(n,t);i=0) /外层循环，控制解分量构造x0,x1,xt,xn-1 6. while (ktmt) /控制第t层同一父亲的兄弟子 树的搜索 7. xt=a(t, kt); /为解分量xt选择kt个值, 部分解 ; 开始时，t=0，选择第1个值a0,0 8. if (constraint(X) break; /如果是1个最终解，退出内循环 11. 12. else /如果还不是最终解，只是一个部分可行解 13. t=t+1; kt=0 /从当前结点开始，向下扩展1层， 处理xt+1，并为其选择St+1中第1个值a(t+1, 0); 做准备，控制返回内循环顶 部（第7步）， 从t+1层的第1个子树开始搜索 14. /内层if 语句结束 15. 16. else kt=kt+1; /当前部分解不可行或不满足界约束，舍弃 该结点对应的子树，返回内层循环顶部， 搜索xt 的其它值 A B DE C FG HIJKLMNO 1 1 11 0 0 0 0 00 t=0, x0=1 t=1, x1=1
