算法设计和分析第6章.

第6章分支限界法学习要点理解分支限界法的剪枝搜索策略。掌握分支限界法的算法框架（1）队列式(FIFO)分支限界法（2）优先队列式分支限界法通过应用范例学习分支限界法的设计策略。（1）单源最短路径问题（2）装载问题；（3）布线问题（4）0-1背包问题；（5）最大团问题；（6）旅行售货员问题（7）电路板排列问题（8）批处理作业调度问题6.1分支限界法的基本思想分支限界法与回溯法（1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值极大或极小的解,在某种意义下的最优解。（2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。6.1分支限界法的基本思想此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。6.1分支限界法的基本思想常见的两种分支限界法（1）队列式(FIFO)分支限界法将活节点表组织成一个队列，按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。（2）优先队列式分支限界法将活节点表组织成一个优先队列，按照优先队列中规定的优先级来选择当前的扩展节点。优先队列一般分为两种：最大优先队列和最小优先队列，节点优先级常用一个与该结点相关的数值p来表示。在算法实现时通常用最大堆来实现最大优先队列，用最大堆的deletemax运算抽取堆中下一个结点成为当前扩展节点，体现最大费用优先的原则。相应地，用最小堆来实现最小优先队列，用最小堆的deletemin运算抽取堆中下一个结点成为当前扩展节点，体现最小费用优先的原则。例1：考虑n=3时0-1背包问题的一个实例：w=[16,15,15],p=[45,25,25],c=30.其解空间树是图5-1中的子集树。下面考虑用队列法和优先队列法来求解。类似于回溯法，我们可以用剪枝函数来加速搜索。请考察下例。例2：4城市旅行售货员问题。解此问题的队列式分支界限法以排列树中节点B作为初始扩展节点。同样可用队列式和优先队列式（最小堆）来解决。412343061020546.2单源最短路径问题1.问题描述下面以一个例子来说明单源最短路径问题：在下面所给的有向图G中，每一边都有一个非负边权。问题：求图G的从源顶点s到目标顶点t之间的最短路径。6.2单源最短路径问题1.问题描述下图是用优先队列式分支限界法求解有向图G的单源最短路径问题时产生的解空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。6.2单源最短路径问题2.算法思想考虑用优先队列式分支限界法用极小堆来存储活结点表。其优先级是结点所对应的当前路长。算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。6.2单源最短路径问题3.剪枝策略在算法扩展结点的过程中，一旦发现一个结点的下界不小于当前找到的最短路长，则算法剪去以该结点为根的子树。在算法中，利用结点间的控制关系进行剪枝。从源顶点s出发，2条不同路径到达图G的同一顶点。由于两条路径的路长不同，因此可以将路长长的路径所对应的树中的结点为根的子树剪去。6.2单源最短路径问题TemplateclassTypeClassGraph{friendvoidmain(void);public:voidShortestPaths(int);private:intn,//图G的顶点数*prev;//前驱顶点数组Type**c,//图G的邻接矩阵*dist;//最短距离数组}TemplateclassTypeClassMinHeapNode{friendGraphType;public:operatorint()const{returnlength;}private:inti;//顶点编号Typelength;//当前路长}TemplateclassTypeVoidGraphType::ShortestPaths(intv){//定义最小堆的容量为1000MinheapMinHeapNodeTypeH(1000);//定义源为初始扩展结点MinHeapNodeTypeE;E.i=v;E.length=0dist[v]=0;while(true){for(intj=1;j=n;j++)if((c[E.i][j]inf)&&(E.length+c[E.i][j]dist[j])){//顶点i到顶点j可达，且满足控制约束dist[j]=E.length+c[E.i][j];prev[j]=E.i;//加入活结点优先队列MinHeapNodeTypeN;N.i=j;N.length=dist[j];H.Insert(N);}try{H.DeleteMin(E);//取下一扩展结点}catch(OutOfBounds){break;}//优先队列空}顶点I和j间有边，且此路径长小于原先从原点到j的路径长6.3装载问题1.问题描述有一批共个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集装箱i的重量为Wi，且装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。容易证明：如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。(1)首先将第一艘轮船尽可能装满；(2)将剩余的集装箱装上第二艘轮船。2.队列式分支限界法在具体搜索解空间树时，首先检测当前扩展结点的左儿子结点是否为可行结点。如果是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点队列中(右儿子结点一定是可行结点)。2个儿子结点都产生后，当前扩展结点被舍弃。活结点队列中的队首元素被取出作为当前扩展结点，队列中每一层结点之后都用一个-1作为尾部标记，故在取队首元素时，活结点队列一定不空。当取出的元素是-1时，再判断当前队列是否为空。如果队列非空，则将尾部标记-1加入活结点队列，算法开始处理下一层的活结点。while(true){//检查左儿子结点if(Ew+w[i]=c)//x[i]=1EnQueue(Q,Ew+w[i],bestw,i,n);//右儿子结点总是可行的EnQueue(Q,Ew,bestw,i,n);//x[i]=0Q.Delete(Ew);//取下一扩展结点if(Ew==-1){//同层结点尾部if(Q.IsEmpty())returnbestw;Q.Add(-1);//同层结点尾部标志Q.Delete(Ew);//取下一扩展结点i++;}//进入下一层}}TemplateclassTypeVoidEnQueue(QueueType&Q,Typewt,Type&bestw,inti,intn){//将活结点加入到活结点队列Q中if(i==n){//可行叶结点if(wtbestw)bestw=wt;}elseQ.Add(wt);//非叶结点}TemplateclassTypeTypeMaxLoading(Typew[],Typec,intn){//队列式分支限界法，返回最优载重量QueueTypeQ;//活节点队列Q.Add(-1);//同层结点尾部标志inti=1;//当前扩展结点所处的层TypeEw=0，//扩展结点所相应的载重量bestw=0;//当前最优载重量3.算法的改进节点的左子树表示将此集装箱装上船，右子树表示不将此集装箱装上船。设bestw是当前最优解；ew是当前扩展结点所相应的重量；r是剩余集装箱的重量。则当ew+rbestw时，可将其右子树剪去，因为此时若要船装最多集装箱，就应该把此箱装上船。另外，为了确保右子树成功剪枝，应该在算法每一次进入左子树的时候更新bestw的值。TemplateclassTypeTypeMaxLoading(Typew[],Typec,intn){//队列式分支限界法，返回最优载重量QueueTypeQ;//活节点队列Q.Add(-1);//同层结点尾部标志inti=1;//当前扩展结点所处的层TypeEw=0，//扩展结点所相应的载重量bestw=0,//当前最优载重量r=0;//剩余集装箱重量for(intj=2;j=n;j++)r+=w[i];While(true){//检查左儿子结点Typewt=Ew+w[i];//左儿子结点的重量if(wt=c){//可行结点if(wtbestw)bestw=wt;//加入活结点队列if(in)Q.Add(wt);}//检查右儿子结点if(Ew+rbestw&&in)Q.Add(Ew);//可能含最优解Q.Delete(Ew);//取下一扩展结点if(Ew==-1){//同层结点尾部if(Q.IsEmpty())returnbestw;Q.Add(-1);//同层结点尾部标志Q.Delete(Ew);//取下一扩展结点i++;r-=w[i];}}}4.构造最优解为了在算法结束后能方便地构造出与最优值相应的最优解，算法必须存储相应子集树中从活结点到根结点的路径。为此目的，可在每个结点处设置指向其父结点的指针，并设置左、右儿子标志。TemplateclassTypeclassQnode{friendvoidEnQueue(QueueQnodetype*&,type,int,int,Type,QnodeType*,QnodeType*&,int*,bool);friendTypeMaxloading(Type*,Type,int,int*);private:QNode*parent;//指向父结点的指针boolLChild;//左儿子标志Typeweight;//结点所相应的载重量}TypeMaxLoading(Typew[],Typec,intn,intbestx){//队列式分支限界法，返回最优载重量QueueQnodeTypeQ;//活节点队列Q.Add(0);//同层结点尾部标志inti=1;//当前扩展结点所处的层TypeEw=0，//扩展结点所相应的载重量bestw=0;//当前最优载重量r=0;for(intj=2;j=n;j++)r+=w[i];QnodeType*E=0,bestE;//当前扩展结点while(true){//检查左儿子结点Typewt=Ew+w[i]；if(wt=c)//可行结点EnQueue(Q,wt,i,n,bestw,E,bestE,bestx,true);if(Ew+rbestw)//右儿子结点总是可行的EnQueue(Q,Ew,i,n,bestw,E,bestE,bestx,false);Q.Delete(E);//取下一扩展结点if(!E){//同层结点尾部if(Q.IsEmpty())break;Q.Add(0);//同层结点尾部标志Q.Delete(E);//取下一扩展结点i++;r-=w[i];}Ew=E-weight;}//构造当前最优解for(intj=n-1;j0;j--){bestx[j]=bestE-LChild;bestE=bestE-parent;}}TemplateclassTypevoidEnQueue(QueueQnodetype*&Q,typewt,inti,intn,Typebest