1、第第5章章 回溯法回溯法计算机算法设计与分析内容提要内容提要每每一步一步都都非常关键，走好每一步！非常关键，走好每一步！1 2 3 理解理解回溯法的深度优先搜索策略回溯法的深度优先搜索策略通用算法、万能算法？通用算法、万能算法？1它在问题的解空间树中，按它在问题的解空间树中，按深度优先策略深度优先策略，从，从根节点出发搜索解空间树。根节点出发搜索解空间树。算法搜索至解空间树的任一结点时，先判断该算法搜索至解空间树的任一结点时，先判断该节点是否包含问题的解。如果肯定不包含，则节点是否包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的搜索，逐层向其跳过对以该结点为根的子树的搜索，逐层向其祖
2、先节点回溯；祖先节点回溯；否则，进入该子树，继续按深度优先策略搜索否则，进入该子树，继续按深度优先策略搜索回溯法回溯法“通用解通用解题题法法”“万能算法万能算法”。回溯回溯法可以系统的搜索一个问题的所有解或任一法可以系统的搜索一个问题的所有解或任一解。解。回溯法是一个即带有系统性又带有跳跃性的搜索回溯法是一个即带有系统性又带有跳跃性的搜索算法。算法。回溯法回溯法回溯法回溯法n扩展结点:一个正在产生孩子的结点称为扩展结点n活结点:一个自身已生成但其孩子还没有全部生成的节点称做活结点n死结点:一个所有孩子已经产生的结点称做死结点n深度优先的问题状态生成法：如果对一个扩展结点R，一旦产生了它的一个孩
3、子C，就把C当做新的扩展结点。在完成对子树C（以C为根的子树）的穷尽搜索之后，将R重新变成扩展结点，继续生成R的下一个孩子（如果存在）n宽度优先的问题状态生成法：在一个扩展结点变成死结点之前，它一直是扩展结点n回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(bounding function)来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。具有限界函数的深度优先生成法称为回溯法 问题的解空间问题的解空间 回溯回溯法的基本思想法的基本思想 递归回溯递归回溯 迭代回溯迭代回溯 子集树与排列树子集树与排列树5.1 回溯法的算法框架回溯法的算法框架1 问题的解空
4、间问题的解空间5.1 回溯算法的基本框架回溯算法的基本框架问题的解空间问题的解空间问题的解空间举例问题的解空间举例回溯法的解空间回溯法的解空间为了用回溯法求解一个具有为了用回溯法求解一个具有n个输个输入的问题，一般情况下，将其可入的问题，一般情况下，将其可能的解表示为满足某个约束条件能的解表示为满足某个约束条件的等长向量的等长向量X=（x1,x2,xn)，其中分量其中分量xi（1=in)output(x);else for(int i=0;in)output(x);else for(int i=t;i=n;i+)swap(xt,xi);if(legal(t)backtrack(t+1);swa
5、p(xt,xi);2回溯法的应用例子回溯法的应用例子装载问题装载问题、作业调度作业调度和和0/1背包问题背包问题33有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且211ccwnii装载问题要求确定：是否有一个合理的装载方案可将这n个集装箱装上这2艘轮船。如果有，找出一种装载方案。nixcxwxwiniiiniii1,1,0s.t.max111n=3，c1=c2=50w1=10,40,40，w2=20,40,40，装载例子装载例子35有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且211ccwnii容易证明，如果一个给
6、定装载问题有解，则采用下面的策略可得到最优装载方案。(1)首先将第一艘轮船尽可能装满；(2)将剩余的集装箱装上第二艘轮船。将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和最接近。由此可知，装载问题等价于以下特殊的0-1背包问题。nixcxwxwiniiiniii1,1,0s.t.max111约束函数？约束函数？在类在类Loading中增加两个私中增加两个私有数据成员有数据成员x和和bestx。X记录记录从根至当前结点的从根至当前结点的路径路径,xi=0/1;1 0 1 1 0Bestx记录当前最优解，算记录当前最优解，算法搜索到达一个叶子结点法搜索到达一个叶子结点
7、处，就修正处，就修正besx的值。的值。构造最优解构造最优解迭代回溯迭代回溯批处理作业调度问题批处理作业调度问题tji机器1机器2作业121作业231作业323批处理作业调度问题批处理作业调度问题批处理作业调度问题批处理作业调度问题批处理作业调度问题批处理作业调度问题批处理作业调度问题批处理作业调度问题解空间？是一个排列树。子树随着作业的减少而减少。批处理作业调度问题批处理作业调度问题class Flowshop friend Flow(int*,int,int);private:void Backtrack(int i);int *M,/各作业所需的处理时间 *x,/当前作业调度 *best
8、x,/当前最优作业调度 *f2,/机器2完成处理时间 f1,/机器1完成处理时间 f,/完成时间和 bestf,/当前最优值 n;/作业数;批处理作业调度问题批处理作业调度问题tji机器1机器2作业121作业231作业323 4皇后问题皇后问题4皇后问题皇后问题4皇后问题皇后问题4皇后问题皇后问题4皇后问题皇后问题0/1背包M图着色问题图着色问题解向量：(x1,x2,xn)表示顶点i所着颜色xi 可行性约束函数：顶点i与已着色的相邻顶点颜色不重复。复杂度分析复杂度分析图m可着色问题的解空间树中内结点个数是对于每一个内结点，在最坏情况下，用ok检查当前扩展结点的每一个儿子所相应的颜色可用性需耗时O(mn)。因此，回溯法总的时间耗费是作业作业分析：分析：5-1；5-2；5-3设计：设计：5-1；5-3
