第五章2 图的搜索算法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第五章 图的搜索算法,5,5,分支限界法,5,5,1,分枝搜索算法,5,5,2,分枝,-,限界搜索算法,5,5,3,算法框架,5,6,图的搜索算法小结,5,5,1,分枝搜索算法,1,基本思想,分支搜索法也是一种在问题解空间上进行尝试搜索算法。所谓“分支”是采用广度优先的策略，依次生成,E-,结点所有分支，也就是所有的儿子结点。和回溯法一样，在生成的节点中，抛弃那些不满足约束条件（或者说不可能导出最优可行解）的结点，其余节点加入活节点表。然后从表中选择一个节点作为下一个,E-,节点。选择下一个,E-,节点的方式不同导致几种不同的分支搜索方式：,1,FIFO,搜索,2,LIFO,搜索,3,优先队列式搜索,上一页,下一页,返回首页,5.5.2,5.5.3,5.6,1,FIFO,搜索,一开始，根结点是唯一的活结点，根结点入队。从活结点队中取出根结点后，作为当前扩展结点。对当前扩展结点，先从左到右地产生它的所有儿子，用约束条件检查，把所有满足约束函数的儿子加入活结点队列中。再从活结点表中取出队首结点（队中最先进来的结点）为当前扩展结点，直到找到一个解或活结点队列为空为止。,返回,上一页,下一页,返回首页,LIFO,搜索,优先队列式搜索,5.5.2,5.5.3,5.6,2,LIFO,搜索,一开始，根结点入栈。从栈中弹出一个结点为当前扩展结点。对当前扩展结点，先从左到右地产生它的所有儿子，用约束条件检查，把所有满足约束函数的儿子入栈，再从栈中弹出一个结点（栈中最后进来的结点）为当前扩展结点，直到找到一个解或栈为空为止。,返回,上一页,下一页,返回首页,FIFO,搜索,优先队列式搜索,5.5.2,5.5.3,5.6,3,优先队列式搜索,为了加速搜索的进程，应采用有效地方式选择,E-,结点进行扩展。优先队列式搜索，对每一活结点计算一个优先级（某些信息的函数值），并根据这些优先级，从当前活结点表中优先选择一个优先级最高（最有利）的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。这种扩展方式要到下一节才用的到。,返回,上一页,下一页,返回首页,FIFO,搜索,LIFO,搜索,5.5.2,5.5.3,5.6,5,5,2,分枝,-,限界搜索算法,【例,2,】,有两艘船，,n,个货箱。第一艘船的载重量是,c1，,第二艘船的载重量是,c2，,wi,是货箱,i,的重量,且,w 1+w2+,wn,c1+c2。,我们希望确定是否有一种可将所有,n,个货箱全部装船的方法。若有的话，找出该方法,FIFO,限界搜索算法,优先队列式分支限界法,上一页,下一页,返回首页,5.5.1,5.5.3,5.6,算法,1,的缺点有,:,1,）在可解的情况下，没有给出每艘装载物品的方案。而要想记录第一艘船最大装载的方案，象回溯法中用,n,个元素的数组是不能实现的，可以象,5.2.2,小节中的例子用数组队列下标记录解方案。,这里采用构造二叉树的方法，和,5.2.2,小节中的例题一样只需要记录最优解的叶结点，这样二叉树就必需有指向父结点的指针，以便从叶结点回溯找解的方案。又为了方便知道当前结点对物品的取舍情况，还必须记录当前结点是父结点的哪一个儿子。,数据结构,：由此，树中结点的信息包括：,weight;parent;,LChild,;。,同时这些结点的地址就是抽象队列的元素，队列操作与算法1相同.,上一页,下一页,返回首页,优先队列式分支限界法,5.5.1,5.5.3,5.6,2,）算法,1,是在对子集树进行盲目搜索，我们虽然不能将搜索算法改进为多项式复杂度，但在算法中加入了,“,限界,”,技巧，还是能降低算法的复杂度。,一个简单的现象，若当前分支的,“,装载上界,”,，比现有的最大装载小，则该分支就无需继续搜索。而一个分支的,“,装载上界,”,，也是容易求解的，就是假设装载当前物品以后的所有物品。,举一个简单的例子，,W=50，10，10，C1=60，,所构成的子集树就无需搜索结点2的分支，因为扩展结点1后，就知道最大装载量不会小于50；而扩展结点2时，发现此分支的,“,装载上界,”,为,w2+w3=2050，,无需搜索此分支，结点2不必入队。,上一页,下一页,返回首页,优先队列式分支限界法,5.5.1,5.5.3,5.6,数据结构,：相应地，当前最大装载,bestw,不仅仅对叶结点计算，每次搜索装载情况（搜索左儿子）时，都重新确定,bestw,的值。为了方便计算一个分支的,“,装载上界,”,，用变量,r,记录当前层以下的最大重量。,公共变量的定义：,float,bestw,w100,bestx,100,;,int,n；,Queue Q;,struct QNode,float weight;,QNode,*parent;,QNode LChild,;,上一页,下一页,返回首页,优先队列式分支限界法,5.5.1,5.5.3,5.6,算法如下：,main(),int,c1,c2,n,s=0,i;,input(c1,c2，n);,for(i=1;i=n;i+),input(wi)；s=s+wi；,if(s=c1 or sc1+c2)print(,“,no solution,”,);return;,上一页,下一页,返回首页,优先队列式分支限界法,5.5.1,5.5.3,5.6,MaxLoading,(c1);,if(s-,bestw,=c2);,print(,“,The first ship loading,”,bestw,，,“,chose：,”,);,for(i=1;i=n;i+),if(,bestx,i=1,),print(i，,“,，,”,);,print(,“,换行符,The second ship loading,”,s-,bestw,“,chose,”,);,for(i=1;i,bestw,)/,目前的最优解/,bestE,=E;,bestx,n=,ch,;/,bestx,n,取值为,ch,return;,b=new,QNode,;/,不是叶子,添加到队列中,b-weight=wt;,b-parent=E;,b-,LChild,=,ch,;/,新节点是左孩子时,add(Q,b);,上一页,下一页,返回首页,优先队列式分支限界法,5.5.1,5.5.3,5.6,3,MaxLoading,(,int,n,int bestx,),Qnode,*E;,int,i=1;,E=new,QNode,;add(Q,0);/0,代表本层的尾部,E-weight=0;E-parent=null;E-,Lchild,=0;add(Q,E);,bestw,=0;r=0;/E-,节点中余下的重量,Ew,=E-weight;,for(,int,j=2;j weight+wi;/,检查,E-,节点的左孩子,if(wt,bestw,),bestw,=wt;,AddLiveNode,(wt,i,E,1);,if(,Ew,+r,bestw,)/,检查右孩子,AddLiveNode,(,Ew,i,E,0);,Delete(Q,E);/,下一个,E-,节点,上一页,下一页,返回首页,优先队列式分支限界法,5.5.1,5.5.3,5.6,4,if(!E)/,层的尾部,if(Empty(Q),break;,add(Q 0);/,层尾指针,Delete(Q,E);/,下一个,E-,节点,i+;/E-,节点的层次,r=r-wi;/E-,节点中余下的重量,Ew,=E-w e i g h t;/,新的,E-,节点的重量,/沿着从,b e s t E,到根的路径构造,x，x n,由,AddLiveNode,来设置,for(j=n-1;j 0;j-),bestx,j=,bestE,-,LChild,;/,从,b o o l,转换为,i n t,bestE,=,bestE,-parent;,return,bestw,;,上一页,下一页,返回首页,优先队列式分支限界法,5.5.1,5.5.3,5.6,上一节介绍的优先队列式扩展方式，若不加入限界策略其实是无意义的。因为要说明解的最优性，不搜索完所有问题空间是不能下结论的，而要对问题空间进行完全搜索，考虑优先级也就没有意义了。,优先队列式搜索通过结点的优先级，可以使搜索尽快朝着解空间树上有最优解的分支推进，这样当前最优解一定较接近真正的最优解。其后我们将当前最优解作为一个“界”，对上界（或下界）不可能达到（大于）这个界的分支则不去进行搜索，这样就缩小搜索范围，提高了搜索效率。这种搜索策略称为优先队列式分支限界法,LC-,检索。,上一页,下一页,返回首页,FIFO,限界搜索算法,5.5.1,5.5.3,5.6,算法设计,3,：用优先队列式分支限界法解决,【,例,2,】,的问题,1）结点扩展方式：无论那种分支限界法，都需要有一张活结点表。优先队列的分支限界法将活结点组织成一个优先队列，并按优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。,2）结点优先级确定：优先队列中结点优先级常规定为一个与该结点相关的数值,p，,它一般表示其接近最优解的程度，本例题就以当前结点的所在分支的装载上界为优先值。,3,）优先队列组织：结点优先级确定后，简单地按结点优先级进行排序，就生成了优先队列。排序算法的时间复杂度较高，考虑到搜索算法每次只扩展一个结点，回忆数据结构中堆排序，适合这一特点且比较交换的次数最少。此题应该采用最大堆来实现优先队列。,数据结构设计：,1,）要输出解的方案，在搜索过程中仍需要生成解结构树，其结点信息包括指向父结点的指针和标识物品取舍（或是,父结点的左、右孩子,）。,2）堆结点首先应该包括结点优先级信息：结点的所在分支的装载上界,uweight,；,堆中无法体现结点的层次信息（,level），,只能存储在结点中；,AddLiveNode,用于把,bbnode,类型的活节点加到子树中，并把,HeapNode,类型的活节点插入最大堆。,3,）不同与算法,2,，由于扩展结点不是按层进行的计算结点的所在分支的装载上界时，要用数组变量,r,记录当前层以下的最大重量，这样可以随时方便使用各层结点的装载上界。,算发设计,3,（,3,）：,算法3如下：,HeapNode,H1000;,struct bbnode,bbnode,*parent;/,父节点指针,int LChild,;/,当且仅当是父节点的左孩子时，取值为1,struct HeapNode,bbnode,*,ptr,;/,活节点指针,float,uweight,;/,活节点的重量上限,int,level;/,活节点所在层,同样为了突出算法本身的思想，对堆操作也只进行抽象的描述：,用,HeapNode,代表队列类型，则,HeapNode,H；,定义了一个堆,H，,相关操作有：,Insert(Q，),表示入堆；,DeleteMax,(Q，);,表示出堆。,算发设计,3,（,4,）,AddLiveNode,(float wt,int lev,bbnode,*E,int ch,),bbnode,*b=new,bbnode,;,b-parent=E;,b-,LChild,=,ch,;,HeapNode,N;,N.,uweight,=wt;,N.level=,lev,;,N.,ptr,=b;,Insert(H，N);,上一页,下一页,返回首页,FIFO,限界搜索算法,5.5.1,5.5.3,5.6,算发设计,3,（,5,）,MaxLoading,(float c,int,n,int bestx,),froat,r100,Ew,，,bestw,=0;rn=0;,for(,int,j=n-1;j 0;j-)rj=rj+1+wj+1;,int,i=1;,bbnode,*E=0;,Ew,=0;/,搜索子集空间树,while(i!=n+1)/,不在叶子上,if(,Ew,+wi=c)/,可行的左孩子,AddLiveNode,(E,Ew,+wi+ri,1,i+1);,if(,bestw,Ew,+wi),bestw,=,Ew,+wi;,if(,bestw,0;j-),bestx,j=E-,LChild,;E=E-parent;,return,Ew,;,算法说明：,算法的复杂度仍为,O（2,n,），,但通过限界策略，并没有搜索子集树中的所有结点，且，由于每次都是选取的最接近最优解的结点扩展，所以一当搜索到叶结点作,E,结点时算法就可以结束了。算法结束时堆并不一定为空。,上一页,下一页,返回首页,5.5.1,5.5.3,5.6,小结讨论：,FIFO,搜索或,LIFO,搜索也可以通过加入“限界”策略加速搜索吗？,那与优先队列式分支限界法,LC,检索的区别在哪儿呢？,答案：由于,FIFO,搜索或,LIFO,搜索是盲目扩展地结点，当前最优解距真正的最优解距离较大，作为“界”所起到的剪枝作用很有限，不能有效提高搜索速度。其实看了下面的例子大家会发现，优先队列式扩展结点的过程，一开始实际是在进行类似“深度优先”的搜索。,例如：,W=10,，,30,，,50,，,C1=60,，,所,构成的子集树如下图所表示：,上一页,下一页,返回首页,5.5.1,5.5.3,5.6,FIFO,限界搜索过程为：,上一页,下一页,返回首页,例,1,1）,初始队列中只有结点,A；,2）,结点,A,变为,E-,结点扩充,B,入队，,bestw,=10；,结点,C,的装载上界为30+50=80,bestw,，,也入队；,3）,结点,B,变为,E-,结点扩充,D,入队，,bestw,=40；,结点,E,的装载上界为60,bestw,，,也入队；,4）,结点,C,变为,E-,结点扩充,F,入队，,bestw,仍为40；,结点,G,的装载上界为50,bestw,，,也入队；,5）,结点,D,变为,E-,结点，叶结点,H,超过容量，,叶结点,I,的装载为40，,bestw,仍为40；,6）,结点,E,变为,E-,结点，叶结点,J,装载量为60，,bestw,为60；,叶结点,K,被剪掉；,7）,结点,F,变为,E-,结点，叶结点,L,超过容量，,bestw,为60；,叶结点,M,被剪掉；,8）,结点,G,变为,E-,结点，叶结点,N、O,都被剪掉；,此时队列空算法结束。,LC-,搜索的过程如下：,1）,初始队列中只有结点,A；,2）,结点,A,变为,E-,结点扩充,B,入堆，,bestw,=10；,结点,C,的装载上界为30+50=80,bestw,，,也入堆；堆中,B,上界为90在优先队列首。,3）,结点,B,变为,E-,结点扩充,D,入堆，,bestw,=40；,结点,E,的装载上界为60,bestw,，,也入堆；此时堆中,D,上界为90为优先队列首。,4）,结点,D,变为,E-,结点，叶结点,H,超过容量，叶结点,I,的装载为40入堆，,bestw,仍为40；此时堆中,C,上界为80为优先队列首。,5）,结点,C,变为,E-,结点扩充,F,入堆，,bestw,仍为40；,结点,G,的装载上界为50,bestw,，,也入堆；此时堆中,E,上界为60为优先队列首。,6）,结点,E,变为,E-,结点，叶结点,J,装载量为60入堆，,bestw,变为60；,叶结点,K,上界为10,bestw,被剪掉；此时堆中,J,上界为60为优先队列首。,7）,结点,J,变为,E-,结点，扩展的层次为4算法结束。,虽然此时堆并不空，但可以确定已找到了最优解。,上一页,下一页,返回首页,5.5.1,5.5.3,5.6,FIFO,限界算法搜索解空间的过程是按图,5-26,子集树中字母序进行的，而优先队列限界搜索解空间的过程是：,A-B-D-C-E-J,看了上面的例子大家会发现，优先队列法扩展结点的过程，一开始实际是在进行类似,“,深度优先,”,的搜索。,5,5,3,算法框架,上一小节的例子是求最大值的最优化问题，下面我们以求找最小成本的最优化问题，给出,FIFO,分支搜索算法框架。,假定问题解空间树为,T,，,T,至少包含一个解结点（即答案结点）。,u,为当前的最优解，初值为一个较大的数,;E,表示当前扩展的活结点，,x,为,E,的儿子，,s(x),为结点,x,下界函数，当其值比,u,大时，不可能为最优解，不继续搜索此分支，该结点不入队；当其值比,u,小时，可能达到最优解，继续搜索此分支，该结点入队；,cost,（,X,）,为当前叶结点所在分支的解。,算法框架如下：,上一页,下一页,返回首页,5.5.1,5.5.2,5.6,2,）：,上一页,下一页,返回首页,5.5.1,5.5.2,5.6,search,（,T,）,/,为找出最小成本答案结点检索,T,。,leaf=0;,初始化队；,ADDQ,（,T,）；,/,根结点入队,parent,（,E,）,=0,；,/,记录扩展路径，当前结点的父结点,while,（,队不空）,DELETEQ(E)/,队首结点出队为新的,E,结点；,for,（,E,的每个儿子,X,）,if(s,（,X,）,u),/,当是可能的最优解时入队,ADD Q,（,X,）；,parent,（,X,）,=E;,if(X,是解结点,)/,x,为叶结点,U=min,（,cost,（,X,），,u,）,;,leaf=x;,/,方案的叶结点存储在,leaf,中,3,）：,上一页,下一页,返回首页,5.5.1,5.5.2,5.6,print,（,”least cost=,，,u,）；,while,（,leaf0,）,/,输出最优解方案,print,（,leaf,）；,leaf=parent,（,leaf,）；,找最小成本的,LC,分支,-,限界算法,框架,与,F,IFO,分支,-,限界算法,框架结构大致相同，只是扩展结点的顺序不同，因而存储活结点的数据结构不同。,F,IFO,分支,-,限界算法用队,存储活结点，,LC,分支,-,限界算法用堆,存储活结点，以保证比较优良的结点先被扩展。且对于,LC,分支,-,限界算法，一当扩展到叶结点就已经找到最优解，可以停止搜索。,5,6,图的搜索算法小结,1,深度优先搜索与广度优先搜索算法有何区别,通常深度优先搜索法不全部保留结点，扩展完的结点从数据存储结构栈中弹出删去，这样，一般在数据栈中存储的结点数就是解空间树的深度，因此它占用空间较少。所以，当搜索树的结点较多，用其它方法易产生内存溢出时，深度优先搜索不失为一种有效的求解方法。,广度优先搜索算法，一般需存储产生的所有结点，占用的存储空间要比深度优先搜索大得多，因此，程序设计中，必须考虑溢出和节省内存空间的问题。但广度优先搜索法一般无回溯操作，即入栈和出栈的操作，所以运行速度比深度优先搜索要快些。,上一页,下一页,返回首页,5.5,2.,2回溯与分支限界法,回溯法以深度优先的方式搜索解空间树,T，,而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树,T。,由于它们在问题的解空间树,T,上搜索的方法不同，适合解决的问题也就不同。一般情况下，回溯法的求解目标是找出,T,中满足约束条件的所有解的方案，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使用某一目标函数值达到极大或极小的解，即在某种意义下的最优解。,相对而言，分支限界算法的解空间比回溯法大得多，因此当内存容量有限时，回溯法成功的可能性更大。,下表列出了回溯法和分支限界法的一些区别：,上一页,下一页,返回首页,5.5,3.,上一页,下一页,返回首页,5.5,4.,在处理最优问题时，采用穷举法、回溯法或分支限界法都可以通过利用当前最优解和上界函数加速。仅就对限界剪支的效率而言，优先队列的分支限界法显然要更充分一些。在穷举法中通过上界函数与当前情况下函数值的比较可以直接略过不合要求的情况而省去了更进一步的枚举和判断；回溯法则因为层次的划分，可以在上界函数值小于当前最优解时，剪去以该结点为根的子树，也就是节省了搜索范围；分支限界法在这方面除了可以做到回溯法能做到的之外，同时若采用优先队列的分支限界法，用上界函数作为活结点的优先级，一旦有叶结点成为当前扩展结点，就意味着该叶结点所对应的解即为最优解，可以立即终止其余的过程。在前面的例题中曾说明，优先队列的分支限界法更象是有选择、有目的地进行深度优先搜索，时间效率、空间效率都是比较高的。,上一页,下一页,返回首页,5.5,5.,3,动态规划与搜索算法,撇开时空效率的因素不谈，在解决最优化问题的算法中，搜索可以说是“万能”的。所以动态规划可以解决的问题，搜索也一定可以解决。动态规划要求阶段决策具有无后向性，而搜索算法没有此限止。,动态规划是自底向上的递推求解，而无论深度优先搜索或广度优先搜索都是自顶向下求解。利用动态规划法进行算法设计时，设计者在进行算法设计前已经用大脑自己构造好了问题的解空间，因此可以自底向上的递推求解；而搜索算法是在搜索过程中根据一定规则自动构造，并搜索解空间树的。由于在很多情况下，问题的解空间太复杂用大脑构造有一定困难，仍然需要采用搜索算法。,上一页,下一页,返回首页,5.5,另外动态规划在递推求解过程中，需要,用数组存储有关信息，而数组的下标只能是整数，所以要求问题中相关的数据必须为整数（如,4.5.3,节,【例,2,】“资源分配问题”中的资金就必须为,整数），对于这类信息非整数或不便于转换为整数的问题，同样,需要采用搜索算法,。,一般说来，动态规划算法在时间效率上的优势是搜索无法比拟的，但动态规划总要遍历所有的状态，而搜索可以排除一些无效状态。更重要的是搜索还可以剪枝，可能剪去大量不必要的状态，因此在空间开销上往往比动态规划要低很多。如何协调好动态规划的高效率与高消费之间的矛盾呢？有一种折衷的办法就是记忆化搜索算法,记忆化限界搜索算法在求解时，还是按着自顶向下的顺序，但是每求解一个状态，就将它的解保存下来，以后再次遇到这个状态的时候，就不必重新求解了。这种方法综合了搜索和动态规划两方面的优点，因而还是很有实用价值的。记忆化限界搜索。它以搜索算法为核心，只不过使用“记录求过的状态”的办法，来避免重复搜索，这样，记忆化搜索的每一步，也可以对应到动态规划算法中去。记忆化搜索有优化方便、调试容易、思维直观的优点，但是效率上比循环的动态规划差一个常数，但是时间和空间复杂度是同一数量级的（尽管空间上也差一个常数，那就是堆栈空间）。当,n,比较小的时候，我们可以忽略这个常数，从而记忆化搜索可以和动态规划达到完全相同的效果。,