《搜索搜索2章节》由会员分享，可在线阅读，更多相关《搜索搜索2章节（43页珍藏版）》请在金锄头文库上搜索。
1、搜索算法回溯法,2,迷宫老鼠问题,出口,(1,1),(2,1),(3,1),(4,1),(5,1),(6,1),(7,1),(8,1),3,回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。 这种以“深度优先”的方式系统地搜索问题地解的算法称为回溯法。,回溯法,4,有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。 回溯法的基本做法是搜索，或是一种组织得井井有
2、条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。,回溯法,5,问题的解空间,问题的解向量：回溯法希望一个问题的解能够表示成一个n元式(x1,x2,xn)的形式。 显约束：对分量xi的取值限定。 隐约束：为满足问题的解而对不同分量之间施加的约束。 解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。,6,n=3时的0-1背包问题用完全二叉树表示的解空间,7,生成问题状态的基本方法,扩展结点:一个正在产生儿子的结点称为扩展结点 活结点:一个自身已生成但其儿子还没有全部生成的节点称做活结点 死结点:一个所有儿子已经产生的结点称做死结
3、点,8,生成问题状态的基本方法,深度优先的问题状态生成法：如果对一个扩展结点R，一旦产生了它的一个儿子C，就把C当做新的扩展结点。在完成对子树C（以C为根的子树）的穷尽搜索之后，将R重新变成扩展结点，继续生成R的下一个儿子（如果存在） 回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(bounding function)来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。,9,回溯法,回溯法是一种通用性解法，可以将回溯法看作是带优化的穷举法。 回溯法的基本思想是在一棵含有问题全部可能解的状态空间树上进行深度优先搜索。搜索过程中，每到达一个结点时，则判断该结点为
4、根的子树是否含有问题的解，如果可以确定该子树中不含有问题的解，则放弃对该子树的搜索，退回到上层父结点，继续下一步深度优先搜索过程。 在回溯法中，并不是先构造出整棵状态空间树，再进行搜索，而是在搜索过程，逐步构造出状态空间树，即边搜索，边构造。,10,0-1背包问题,n=3时，0-1背包问题解空间树 w=16,15,15，p=45,25,25，背包容量C=30,11,旅行售货员问题,4,12,递归回溯,回溯法对解空间作深度优先搜索，因此，在一般情况下用递归方法实现回溯法。,void backtrack (int t) if (tn) output(x); else for (int i=f(n,
5、t);i=g(n,t);i+) xt=h(i); if (constraint(t) ,13,子集树:当所给问题是从n个元素的集合S中找出满足某种性质的子集时,相应的解空间为子集树。(0-1背包),14,遍历子集树需O(2n)计算时间,void backtrack (int t) if (tn) output(x); else for (int i=0;i=1;i+) xt=i; if (legal(t) backtrack(t+1); ,子集树,15,排列树:当所给问题是确定n个元素满足某种性质的排列时,相应的解空间为排列树。(旅行售货员问题),16,遍历排列树需要O(n!)计算时间,voi
6、d backtrack (int t) if (tn) output(x); else for (int i=t;i=n;i+) swap(xt, xi); if (legal(t) backtrack(t+1); swap(xt, xi); ,排列树,17,回溯法的基本思想,(1)针对所给问题，定义问题的解空间； (2)确定易于搜索的解空间结构，并构造结果判断函数； (3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。,18,回溯法的基本思想,常用剪枝函数： 用约束函数在扩展结点处剪去不满足约束的子树； 用限界函数剪去得不到最优解的子树。,19,回溯算法框架 问题的解空间深
7、度优先遍历判断结果的函数剪枝函数,20,用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n)。而显式地存储整个解空间则需要O(2h(n)或O(h(n)!)内存空间。,21,装载问题,有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且,装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。,22,装载问题,容易证明，如果一个给定装载问题有解，则采用下面的策略可得
8、到最优装载方案。 (1)首先将第一艘轮船尽可能装满； (2)将剩余的集装箱装上第二艘轮船。 将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和最接近。由此可知，装载问题等价于以下特殊的0-1背包问题。,23,装载问题,用回溯法设计解装载问题的O(2n)计算时间算法。,24,装载问题,解空间：子集树 可行性约束函数(选择当前元素)： 上界函数(不选择当前元素)： 当前载重量cw+剩余集装箱的重量r当前最 优载重量bestw,25,void backtrack (int i) / 搜索第i层结点 if (i n) / 到达叶结点 更新最优解bestx,bestw;ret
9、urn; r -= wi; if (cw + wi bestw) xi = 0; / 搜索右子树 backtrack(i + 1); r += wi; ,26,批处理作业调度,给定n个作业的集合J1,J2,Jn。每个作业必须先由机器1处理，然后由机器2处理。作业Ji需要机器j的处理时间为tji。对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间。所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和。 批处理作业调度问题要求对于给定的n个作业，制定最佳作业调度方案，使其完成时间和达到最小。,27,批处理作业调度,这3个作业的6种可能的调度方案是1,2,3；1,3,2；2,1
10、,3；2,3,1；3,1,2；3,2,1；它们所相应的完成时间和分别是19，18，20，21，19，19。易见，最佳调度方案是1,3,2，其完成时间和为18。,28,批处理作业调度,解空间：排列树,void Flowshop:Backtrack(int i) if (i n) for (int j = 1; j f1)?f2i-1:f1)+Mxj2; f+=f2i; if (f bestf) Swap(xi, xj); Backtrack(i+1); Swap(xi, xj); f1- =Mxj1; f- =f2i; ,class Flowshop friend Flow(int*, int,
11、 int ); private: void Backtrack(int i); int *M, / 各作业所需的处理时间 *x, / 当前作业调度 *bestx, / 当前最优作业调度 *f2, / 机器2完成处理时间 f1, / 机器1完成处理时间 f, / 完成时间和 bestf, / 当前最优值 n; / 作业数;,29,符号三角形问题,+ + - + - + + + - - - - + - + + + - - + + - - + - - - +,下图是由14个“+”和14个“-”组成的符号三角形。2个同号下面都是“+”，2个异号下面都是“-”。,30,符号三角形问题,在一般情况下，符号
12、三角形的第一行有n个符号。符号三角形问题要求对于给定的n，计算有多少个不同的符号三角形，使其所含的“+”和“-”的个数相同。,31,符号三角形问题,解向量：用n元组x1:n表示符号三角形的第一行。 可行性约束函数：当前符号三角形所包含的“+”个数与“-”个数均不超过n*(n+1)/4 无解的判断：n*(n+1)/2为奇数,+ + - + - + + + - - - - + - + + + - - + + - - + - - - +,+ + - + - + + + - - - - + - + + + - - + + - - + - - - +,32,符号三角形问题,void Triangle:B
13、acktrack(int t) if (tn) sum+; else for (int i=0;i2;i+) Backtrack(t+1); ,if (counthalf)|(t*(t-1)/2-counthalf) return;,p1t=i; count+=i; for (int j=2;j=t;j+) pjt-j+1=1-pj-1t-j+1pj-1t-j+2; count+=pjt-j+1; ,for (int j=2;j=t;j+) count-=pjt-j+1; count-=i;,33,n后问题,在nn格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同
14、一行或同一列或同一斜线上的棋子。n后问题等价于在nn格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。,34,n后问题,1,2,3,4,5,6,7,8,35,n后问题,四后问题解空间树（按深度优先对结点编号）,36,n后问题,四皇后问题的解空间树 四皇后问题的状态空间树上共有24个叶节点(4!), 就是问题的所有可能解， 树的内部结点代表问题的部分解；例如36为部分 解(x1,x2,x3)=(3,1,2) 结点的编号是按DFS（Deep First Search)方式排列的，其实也就是按回溯方式遍历搜索的次序,37,解向量：(x1, x2, , xn) 显约束：xi=1,2
15、, ,n 隐约束： 1)不同列：xixj 2)不处于同一正、反对角线：|i-j|xi-xj|,n后问题,bool Queen:Place(int k) for (int j=1;jn) sum+; else for (int i=1;i=n;i+) xt=i; if (Place(t) Backtrack(t+1); ,38,n后问题,四后问题解空间树（按深度优先对结点编号）,39,n后问题, 时间代价 空间树共有65个结点，24个叶节点，但在搜索过程中， 只遍历了16个结点，其中2个叶节点 遍历的总结点数肯定大大小于65 空间代价 与树的高度有关，而不是和树的总结点数有 回溯算法中，并不需要真正创建一个解空间树,40,Oil Deposits,The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits. GeoSurvComp works with one large rectangular region of land at a time, and
