第7章 分支限界法精选PPT.ppt

第7章分支限界法第1页，本讲稿共28页7.1 7.1 引言引言 分枝限界法是另一种系统搜索解空间的方法。类似分枝限界法是另一种系统搜索解空间的方法。类似于回溯法，分枝限界法在搜索解空间时，也经常使用树于回溯法，分枝限界法在搜索解空间时，也经常使用树形结构来组织解空间。形结构来组织解空间。然而与回溯法不同的是，回溯法是使用深度优先方然而与回溯法不同的是，回溯法是使用深度优先方法搜索树结构，而分枝限界一般使用宽度优先或优先队法搜索树结构，而分枝限界一般使用宽度优先或优先队列搜索方法来搜索这些树。并且在搜索过程中，也是通列搜索方法来搜索这些树。并且在搜索过程中，也是通过跳过那些肯定不包含所要寻找的解结点的子树的搜索过跳过那些肯定不包含所要寻找的解结点的子树的搜索（即剪枝）来提高搜索效率。（即剪枝）来提高搜索效率。一、分枝限界法的基本思想一、分枝限界法的基本思想第2页，本讲稿共28页7.1 7.1 引言引言 分枝限界法可以系统地搜索一个问题的解空间，它也是一种既带有系统性又带有跳跃性的搜索方法。系统性使用宽度优先搜索法或优先队列搜索方法来搜索解空间树跳跃性剪枝。搜索到任一个结点时，总是要判断以该结点为根的子树中是否包肯定不含有问题的解。若肯定不包含，则跳过对该子树的搜索（剪枝），向上逐层回溯；否则进入该子树，继续搜索。一、分枝限界法的基本思想第3页，本讲稿共28页7.1 7.1 引言引言 分枝限界法的适用问题类型与回溯法基本相同，一般也是下面两种类型：1.存在性问题 2.最优化问题二、分枝限界法的适用问题三、分枝限界算法的基本框架 1.基本要素 解空间的树形表示。例如，0/1背包问题：子集树；n皇后问题：满n叉树；旅行商问题：排列树；等等。第4页，本讲稿共28页7.1 7.1 引言引言 剪枝操作。根据约束条件、目标函数的界来设计剪枝操作。优先队列。设计待检测结点的优先级。二、分枝限界算法的基本框架2分枝限界法的基本思想 树的优先队列优先搜索+剪枝 第5页，本讲稿共28页7.1 7.1 引言引言 二、分枝限界算法的基本框架二、分枝限界算法的基本框架 3 3分枝限界算法形式及终止条件分枝限界算法形式及终止条件算法形式算法形式：一般是迭代形式。：一般是迭代形式。算法终止的条件算法终止的条件：求存在性问题时，找到问题的一个解即可：求存在性问题时，找到问题的一个解即可结束；在求优化问题时，一般要求优先队列为空时才结束，但结束；在求优化问题时，一般要求优先队列为空时才结束，但是在满足一定条件时可在找到一个解即可结束（该解即为最优是在满足一定条件时可在找到一个解即可结束（该解即为最优解）。解）。第6页，本讲稿共28页7.1 7.1 引言引言 二、分枝限界算法的基本框架二、分枝限界算法的基本框架 4分枝限界法的特性时间性能：时间性能：最坏的情况要搜索整个解空间，是复杂最坏的情况要搜索整个解空间，是复杂 度是指数型。但如果启发式信息强且剪枝操作有力的话，度是指数型。但如果启发式信息强且剪枝操作有力的话，平均性能往往很好。平均性能往往很好。空间性能：空间性能：优先队列往往需要较大的空间开销。优先队列往往需要较大的空间开销。第7页，本讲稿共28页生成问题状态的基本方法v扩展结点扩展结点:一个正在产生儿子的结点称为扩展结点一个正在产生儿子的结点称为扩展结点v活结点活结点:一个自身已生成但其儿子还没有全部生成的节点称做活一个自身已生成但其儿子还没有全部生成的节点称做活结点结点v死结点死结点:一个所有儿子已经产生的结点称做死结点一个所有儿子已经产生的结点称做死结点v深度优先的问题状态生成法：如果对一个扩展结点深度优先的问题状态生成法：如果对一个扩展结点R R，一旦产生，一旦产生了它的一个儿子了它的一个儿子C C，就把，就把C C当做新的扩展结点。在完成对子树当做新的扩展结点。在完成对子树C C（以（以C C为为根的子树）的穷尽搜索之后，将根的子树）的穷尽搜索之后，将R R重新变成扩展结点，继续生成重新变成扩展结点，继续生成R R的的下一个儿子（如果存在）下一个儿子（如果存在）v宽度优先的问题状态生成法：在一个扩展结点变成死结点之前，宽度优先的问题状态生成法：在一个扩展结点变成死结点之前，它一直是扩展结点它一直是扩展结点v回溯法：每当出现死节点就进行回溯，通过继续扩展父节点产生新回溯法：每当出现死节点就进行回溯，通过继续扩展父节点产生新的活节点，直至找到最优解。的活节点，直至找到最优解。v分支限界法：每个活节点有且只有一次机会变成扩展节点、当一个分支限界法：每个活节点有且只有一次机会变成扩展节点、当一个节点变为扩展节点时，则生成所有的子节点（分支）。节点变为扩展节点时，则生成所有的子节点（分支）。第8页，本讲稿共28页生成问题状态的基本方法v分支限界法：在生成的节点中，抛弃哪些不可能导出可行解（最优解）的节点，其余节点加入活动结点表，然后从表中选择一个节点作为下一个扩展节点，从活动节点表中取出所选择的节点并进行扩充，直到找到解或活动节点表为空，扩充过程才结束。（1）队列式(FIFO)分支限界法 按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。（2）优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。第9页，本讲稿共28页0-1背包问题算法的思想首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。在下面描述的优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时为问题的最优值。第10页，本讲稿共28页0-1背包问题上界函数while(i=n&wi=cleft)/n表示物品总数，cleft为剩余空间 cleft-=wi;/wi表示i所占空间 b+=pi;/pi表示i的价值 i+;if(i=n)b+=pi/wi*cleft;/装填剩余容量装满背包 return b;/b为上界函数第11页，本讲稿共28页0-1背包问题Private static double bbKnapsack()/优优先先队队列返回最大价列返回最大价值值，bestx返回最返回最优优解解/初始化初始化 bestp 为为当前最当前最优值优值；up为为价价值值上限上限Node enode=null;int i=1;double bestp=0.0;double up=bound(1);/搜索子集空搜索子集空间树间树while(i!=n+1)/非叶结点非叶结点 /检查当前扩展结点的左儿子结点检查当前扩展结点的左儿子结点 Typew wt=cw+wi;if(wt bestp)bestp=cp+pi;AddLiveNode(up,cp+pi,cw+wi,true,i+1);/将一个新的活节点插入到优先队列将一个新的活节点插入到优先队列 up=Bound(i+1);/检查当前扩展结点的右儿子结点检查当前扩展结点的右儿子结点 if(up=bestp)/右子树可能含最优解右子树可能含最优解 AddLiveNode(up,cp,cw,false,i+1);/取下一个扩展节点取下一个扩展节点 HeapNode node=(HeapNode)heap.removeMax();enode=node.liveNode;cw=node.weight;cp=node.profit;up=node.upperProfit;i=node.level;分支限界搜索过程分支限界搜索过程第12页，本讲稿共28页0-1背包问题/构造当前最优解 for(int j=n;j0;j-)bestxj=(enode.leftChild)?1:0;enode=enode.parent;return cp;privatestaticvoidaddLiveNode(doubleup,doublepp,doubleww,intlev,BBnodepar,booleanch)/将一个新的活节点插入到子集树和最大堆H中BBnodeb=newBBnode(par,ch);HeapNodenode=newHeapNode(b,up,pp,ww,lev);heap.put(node);第13页，本讲稿共28页旅行售货员问题1.问题描述 某售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费)。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费)最小。路线是一个带权图。图中各边的费用（权）为正数。图的一条周游路线是包括V中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。旅行售货员问题的解空间可以组织成一棵树，从树的根结点到任一叶结点的路径定义了图的一条周游路线。旅行售货员问题要在图G中找出费用最小的周游路线。第14页，本讲稿共28页旅行售货员问题1.问题描述 各个城市之间可能是有向连通的、无向连通的、以及存在某个城市不连通的情况，你的程序应该能够处理所有可能的情况。如下图表示各个城市间无向连通。输入：第一行为一个整数n(n0表示从i到j的路程长度为len。对于上面图示的问题我们可以按照下面方式输入：4-1 30 6 430 -1 5 106 5 -1 204 10 20 -1第15页，本讲稿共28页旅行售货员问题2.问题分析可能解空间：可能解集合S=1,1 是2,3,n的一个排列；所以可能解的总数|S|=(n-1)!。当n=4时，其状态解空间一共有3!=6条路径。对此设计代价函数：1）C(x)=从根到节点x的距离（x为叶子）2）C(x)=x的子树中最小代价的叶子节点的代价（x为内部节点）第16页，本讲稿共28页旅行售货员问题3.算法描述1）活动节点表：设计活动节点表：L1.n;初始时，L=1,只含起始节点；运行中，根据活动节点的代价函数，决定下次搜索的节点扩展节点；再扩展该节点的子节点，在表中取代该节点，再选择在扩展。当活节点表为空，搜索结束。第17页，本讲稿共28页旅行售货员问题3.算法描述2）搜索过程举例：（图参看讲义)1.将初始节点放入队列；2.取出节点，它是可扩展的节点，扩展得到它的所有孩子节点均放入队列中，并按照c(x)从小到大排列；3.取出耗费最小的节点，扩展得到，它是可行解，且先前没有可行解，故记录下来并令u(x)=它的长度；4.取出节点，它的长度大于u(x)，抛弃；5.取出节点，它的长度大于u(x)，抛弃；6.队列为空，记录的可行解就是最优解。第18页，本讲稿共28页旅行售货员问题3.算法描述Node*TSP(T,C)Node*TSP(T,C)将邻接矩阵的上三角元素按升序排序，存入一维数组中将邻接矩阵的上三角元素按升序排序，存入一维数组中distdist中，创建一中，创建一个记录节点个记录节点CurBestCurBest，记录最优可行解；，记录最优可行解；u(CurBest)=Max;u(CurBest)=Max;Creat(Q);Creat(Q);取取distdist的前的前n n个元素，创建一个初始节点个元素，创建一个初始节点T T；insertinsert（T T，Q Q）；）；while(!Empty(Q)while(!Empty(Q)e=deletMin(Q);/e=deletMin(Q);/出队出队 if(eif(e的路径长度的路径长度u(curBest)u(curBest)while(d=e while(d=e的下一个孩子节点的下一个孩子节点)!=NULL)!=NULL)if(d if(d是可行解是可行解)if(d if(d的路径长度的路径长度cruBestcruBest所记录的长度所记录的长度)curBest=d;curBest=d;else else计算计算c(d);insert(d,Q);c(d);insert(d,Q);return curBest;return curBest;第19页，本讲稿共28页/旅行售货员问题，用分支限界法实现Javaimportjava.util.Scanner;publicclassMain/Mainpublicstaticvoidmain(Stringargs)Scanners=newScanner(System.in);intn=0;/结点的个数Stringline=s.nextLine();/读入nn=Integer.parseInt(line);a=newfloatnn;intvv=newintn;for(inti=0;in;i+)line=s.nextLine();StringsArray=line.split(“”);for(intj=0;jsArray.length;j+)aij=Integer.parseInt(sArrayj);System.out.println(bbTsp(vv);/Mainstaticfloata;/图的邻接矩阵/staticfloata=-1,-1,-1,2,2,-1,-1,-1,1,3,-1,-1,-1,-1,1,-1;第20页，本讲稿共28页privatestaticclassHeapNodeimplementsComparablefloatlcost,/子树费用下界cc,/当前费用rcost;/Xs:n-1中顶点最小出边费用和ints;/根节点到当前结点的路径为X0:sintx;/需要进一步搜索的结点是xs+1:n-1/HeapNode的构造函数HeapNode(floatlc,floatccc,floatrc,intss,intxx)lcost=lc;cc=ccc;s=ss;x=xx;/HeapNode构造函数publicintcompareTo(Objectx)floatxlc=(HeapNode)x).lcost;if(lcostxlc)return-1;if(lcost=xlc)return0;return1;/classHeapNode第21页，本讲稿共28页publicstaticintbbTsp(intv)intn=v.length;MinHeapheap=newMinHeap(100);floatminOut=newfloatn;/minOuti是顶点i的最小出边费用floatminSum=0;/最小出边费用和/计算最小出边费用和for(inti=0;in;i+)floatmin=Float.MAX_VALUE;for(intj=0;jn;j+)if(aij!=-1&aijmin)min=aij;/有回路/forjif(min=Float.MAX_VALUE)return-1;/无回路/ifminOuti=min;minSum+=min;/fori/初始化intx=newintn;for(inti=0;in;i+)xi=i;HeapNodeenode=newHeapNode(0,0,minSum,0,x);floatbestc=Float.MAX_VALUE;第22页，本讲稿共28页/搜索排列空间树while(enode!=null&enode.sn-1)x=enode.x;if(enode.s=n-2)/叶子结点if(axn-2xn-1!=-1&axn-11!=-1|bestc=Float.MAX_VALUE)/当前最优解还不存在的情况bestc=enode.cc+axn-2xn-1+axn-10;enode.cc=bestc;enode.lcost=bestc;enode.s+;heap.put(enode);/if(enode.s=n-2)第23页，本讲稿共28页else/if(enode.s!=n-2)for(inti=enode.s+1;in;i+)if(axenode.sxi!=-1)floatcc=enode.cc+axenode.sxi;floatrcost=enode.rcost-minOutxenode.s;floatb=cc+rcost;if(bbestc)intxx=newintn;for(intj=0;jn;j+)xxj=xj;xxenode.s+1=xi;xxi=xenode.s+1;HeapNodenode=newHeapNode(b,cc,rcost,enode.s+1,xx);heap.put(node);/if(bbestc)/if可行儿子结点/for/else,if(enode.s!=n-2)enode=(HeapNode)heap.removeMin();/whilefor(inti=0;in;i+)vi=xi;return(int)bestc;/ClassbbTsp第24页，本讲稿共28页/构造最小堆publicstaticclassMinHeapprivateHeapNodeheapArray;/堆容器privateintmaxSize;/堆的最大大小privateintcurrentSize=0;/堆大小/构造函数publicMinHeap(int_maxSize)maxSize=_maxSize;heapArray=newHeapNodemaxSize;currentSize=0;第25页，本讲稿共28页/自上而下调整publicvoidfilterDown(intstart,intendOfHeap)inti=start;intj=2*i+1;/j是i的左子女位置HeapNodetemp=heapArrayi;while(j=endOfHeap)/检查是否到最后位置if(jheapArrayj+1.cc)j+;if(temp.cc0)/沿双亲结点路径向上直达根节点if(heapArrayi.cc=temp.cc)/双亲结点值小，不调整break;else/双亲结点值大，调整heapArrayj=heapArrayi;j=i;i=(i-1)/2;heapArrayj=temp;/回送/filterUp第27页，本讲稿共28页/插入结点publicvoidput(HeapNodenode)HeapNodenewNode=node;heapArraycurrentSize=newNode;filterUp(currentSize);currentSize+;/put/删除堆中的最小值publicHeapNoderemoveMin()HeapNoderoot=heapArray0;heapArray0=heapArraycurrentSize-1;currentSize-;filterDown(0,currentSize-1);returnroot;/classMinHeap/classMain第28页，本讲稿共28页