搜索
第7章分枝限界法7.1引言分枝限界法是另一种系统搜索解空间的方法。类似于回溯法，分枝限界法在搜索解空间时，也经常使用树形结构来组织解空间。然而与回溯法不同的是，回溯法是使用深度优先方法搜索树结构，而分枝限界一般使用宽度优先或优先队列搜索方法来搜索这些树。并且在搜索过程中，也是通过跳过那些肯定不包含所要寻找的解结点的子树的搜索（即剪枝）来提高搜索效率。一、分枝限界法的基本思想7.1引言分枝限界法可以系统地搜索一个问题的解空间，它也是一种既带有系统性又带有跳跃性的搜索方法。系统性——使用宽度优先搜索法或优先队列搜索方法来搜索解空间树跳跃性——剪枝。搜索到任一个结点时，总是要判断以该结点为根的子树中是否包肯定不含有问题的解。若肯定不包含，则跳过对该子树的搜索（剪枝），向上逐层回溯；否则进入该子树，继续搜索。一、分枝限界法的基本思想7.1引言分枝限界法的适用问题类型与回溯法基本相同，一般也是下面两种类型：1.存在性问题2.最优化问题二、分枝限界法的适用问题三、分枝限界算法的基本框架1.基本要素解空间的树形表示。例如，0/1背包问题：子集树；n皇后问题：满n叉树；旅行商问题：排列树；等等。7.1引言剪枝操作。根据约束条件、目标函数的界来设计剪枝操作。优先队列。设计待检测结点的优先级。二、分枝限界算法的基本框架2．分枝限界法的基本思想树的优先队列优先搜索+剪枝7.1引言二、分枝限界算法的基本框架3．分枝限界算法形式及终止条件•算法形式：一般是迭代形式。•算法终止的条件：求存在性问题时，找到问题的一个解即可结束；在求优化问题时，一般要求优先队列为空时才结束，但是在满足一定条件时可在找到一个解即可结束（该解即为最优解）。7.1引言二、分枝限界算法的基本框架4．分枝限界法的特性•时间性能：最坏的情况要搜索整个解空间，是复杂度是指数型。但如果启发式信息强且剪枝操作有力的话，平均性能往往很好。•空间性能：优先队列往往需要较大的空间开销。生成问题状态的基本方法扩展结点:一个正在产生儿子的结点称为扩展结点活结点:一个自身已生成但其儿子还没有全部生成的节点称做活结点死结点:一个所有儿子已经产生的结点称做死结点深度优先的问题状态生成法：如果对一个扩展结点R，一旦产生了它的一个儿子C，就把C当做新的扩展结点。在完成对子树C（以C为根的子树）的穷尽搜索之后，将R重新变成扩展结点，继续生成R的下一个儿子（如果存在）宽度优先的问题状态生成法：在一个扩展结点变成死结点之前，它一直是扩展结点回溯法：每当出现死节点就进行回溯，通过继续扩展父节点产生新的活节点，直至找到最优解。分支限界法：每个活节点有且只有一次机会变成扩展节点、当一个节点变为扩展节点时，则生成所有的子节点（分支）。生成问题状态的基本方法分支限界法：在生成的节点中，抛弃哪些不可能导出可行解（最优解）的节点，其余节点加入活动结点表，然后从表中选择一个节点作为下一个扩展节点，从活动节点表中取出所选择的节点并进行扩充，直到找到解或活动节点表为空，扩充过程才结束。（1）队列式(FIFO)分支限界法按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。（2）优先队列式分支限界法按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。0-1背包问题算法的思想首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。在下面描述的优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时为问题的最优值。0-1背包问题上界函数while(i=n&&w[i]=cleft)//n表示物品总数，cleft为剩余空间{cleft-=w[i];//w[i]表示i所占空间b+=p[i];//p[i]表示i的价值i++;}if(i=n)b+=p[i]/w[i]*cleft;//装填剩余容量装满背包returnb;//b为上界函数0-1背包问题PrivatestaticdoublebbKnapsack(){//优先队列返回最大价值，bestx返回最优解//初始化bestp为当前最优值；up为价值上限Nodeenode=null;inti=1;doublebestp=0.0;doubleup=bound(1);//搜索子集空间树while(i!=n+1){//非叶结点//检查当前扩展结点的左儿子结点Typewwt=cw+w[i];if(wt=c){//左儿子结点为可行结点if(cp+p[i]bestp)bestp=cp+p[i];AddLiveNode(up,cp+p[i],cw+w[i],true,i+1);}//将一个新的活节点插入到优先队列up=Bound(i+1);//检查当前扩展结点的右儿子结点if(up=bestp)//右子树可能含最优解AddLiveNode(up,cp,cw,false,i+1);//取下一个扩展节点HeapNodenode=(HeapNode)heap.removeMax();enode=node.liveNode;cw=node.weight;cp=node.profit;up=node.upperProfit;i=node.level;}}分支限界搜索过程0-1背包问题//构造当前最优解for(intj=n;j0;j--){bestx[j]=(enode.leftChild)?1:0;enode=enode.parent;}returncp;}privatestaticvoidaddLiveNode(doubleup,doublepp,doubleww,intlev,BBnodepar,booleanch){//将一个新的活节点插入到子集树和最大堆H中BBnodeb=newBBnode(par,ch);HeapNodenode=newHeapNode(b,up,pp,ww,lev);heap.put(node);}旅行售货员问题1.问题描述某售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费)。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费)最小。路线是一个带权图。图中各边的费用（权）为正数。图的一条周游路线是包括V中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。旅行售货员问题的解空间可以组织成一棵树，从树的根结点到任一叶结点的路径定义了图的一条周游路线。旅行售货员问题要在图G中找出费用最小的周游路线。旅行售货员问题1.问题描述各个城市之间可能是有向连通的、无向连通的、以及存在某个城市不连通的情况，你的程序应该能够处理所有可能的情况。如下图表示各个城市间无向连通。输入：第一行为一个整数n(n=10)，表示城市的总个数。接下来是一个n*n的矩阵，用来表示城市间的连通情况以及花费，例如path[i][j]=len，len=-1表示从城市i到城市j没有通路，len0表示从i到j的路程长度为len。对于上面图示的问题我们可以按照下面方式输入：4-1306430-151065-12041020-1旅行售货员问题2.问题分析可能解空间：可能解集合S={1,∏,1}∏是{2,3,……,n}的一个排列；所以可能解的总数|S|=(n-1)!。当n=4时，其状态解空间一共有3!=6条路径。对此设计代价函数：1）C(x)=从根到节点x的距离（x为叶子）2）C(x)=x的子树中最小代价的叶子节点的代价（x为内部节点）旅行售货员问题3.算法描述1）活动节点表：设计活动节点表：L[1..n];初始时，L={1},只含起始节点；运行中，根据活动节点的代价函数，决定下次搜索的节点—扩展节点；再扩展该节点的子节点，在表中取代该节点，再选择在扩展。当活节点表为空，搜索结束。旅行售货员问题3.算法描述2）搜索过程举例：（图参看讲义)1.将初始节点①放入队列；2.取出节点①，它是可扩展的节点，扩展得到它的所有孩子节点②③④均放入队列中，并按照c(x)从小到大排列；3.取出耗费最小的节点④，扩展得到⑤，它是可行解，且先前没有可行解，故记录下来并令u(x)=它的长度；4.取出节点③，它的长度大于u(x)，抛弃；5.取出节点②，它的长度大于u(x)，抛弃；6.队列为空，记录的可行解⑤就是最优解。旅行售货员问题3.算法描述Node*TSP(T,C){将邻接矩阵的上三角元素按升序排序，存入一维数组中dist[]中，创建一个记录节点CurBest，记录最优可行解；u(CurBest)=Max;Creat(Q);取dist的前n个元素，创建一个初始节点T；insert（T，Q）；while(!Empty(Q)){e=deletMin(Q);//出队if(e的路径长度u(curBest))while((d=e的下一个孩子节点)!=NULL){if(d是可行解){if(d的路径长度cruBest所记录的长度)curBest=d;}}else{计算c(d);insert(d,Q);}}returncurBest;}//旅行售货员问题，用分支限界法实现Javaimportjava.util.Scanner;publicclassMain{//Mainpublicstaticvoidmain(Stringargs[]){Scanners=newScanner(System.in);intn=0;//结点的个数Stringline=s.nextLine();//读入nn=Integer.parseInt(line);a=newfloat[n][n];int[]vv=newint[n];for(inti=0;in;i++){line=s.nextLine();String[]sArray=line.split(“”);for(intj=0;jsArray.length;j++){a[i][j]=Integer.parseInt(sArray[j]);}}System.out.println(bbTsp(vv));}//Mainstaticfloat[][]a;//图的邻接矩阵//staticfloata[][]={{-1,-1,-1,2},{2,-1,-1,-1},{1,3,-1,-1},{-1,-1,1,-1}};privatestaticclassHeapNodeimplementsComparable{floatlcost,//子树费用下界cc,//当前费用rcost;//X[s:n-1]中顶点最小出边费用和ints;//根节点到当前结点的路径为X[0:s]int[]x;//需要进一步搜索的结点是x[s+1:n-1]//HeapNode的构造函数HeapNode(floatlc,floatccc,floatrc,intss,int[]xx){lcost=lc;cc=ccc;s=ss;x=xx;}//HeapNode构造函数publicintcompareTo(Objectx){floatxlc=((HeapNode)x).lcost;if(lcostxlc)return-1;if(lcost==xlc)return0;return1;}}//classHeapNodepublicstaticintbbTsp(int[]v){intn=v.length;MinHeapheap=newMinHeap(100);float[]minOut=newfloat[n];//minOut[i]是顶点i的最小出边费用floatminSum=0;//最小出边费用和//计算最小出边费用和for(inti=0;in;i++){floatmin=Float.MAX_VALUE;for(intj=0;jn;j++){if(a[i][j]!=-1&&a[i][