【文档说明】计算机算法设计与分析第6章分支限界法课件.ppt，共(80)页，738.500 KB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-5411.html

以下为本文档部分文字说明：

计算机算法设计与分析DesignandAnalysisofComputerAlgorithms第六章分支限界法Branch-and-BoundAlgorithm第1页，共80页。理解分支限界法的剪枝

搜索策略。掌握分支限界法的算法框架1.队列式(FIFO)分支限界法2.优先队列式分支限界法通过应用范例学习分支限界法的设计策略。1.单源最短路径问题2.装载问题；3.布线问题4.0-1背包问题；5.最大团问题；6.旅行售货员问题7.电路板排列问题8.

批处理作业调度问题学习要点11/13/20222第2页，共80页。提纲一、分支限界法的基本思想二、单源最短路径问题三、装载问题四、0-1背包问题五、最大团问题六、旅行售货员问题11/13/20223第3页，共80页。提纲一、分支限界法的基本思想

二、单源最短路径问题三、装载问题四、0-1背包问题五、最大团问题六、旅行售货员问题11/13/20224第4页，共80页。分支限界法同回溯法类似，它也是在解空间中搜索问题的可行解或最优解，但搜索的方式不同。回溯法采用深度优先的方式，朝纵深方向搜索，直至达到问题的一个可行解，或经判

断沿此路径不会达到问题的可行解或最优解时，停止向前搜索，并沿原路返回到该路径上最后一个还可扩展的结点。从该结点出发朝新的方向纵深搜索。分支定界法则采用宽度优先的方式搜索解空间树，它将活结点存放在一个特殊的表中。其策略是：在扩展结点处，先生成其所有的儿子

结点,将那些导致不可行解或导致非最优解的儿子舍弃，其余儿子加入活结点表中。此后，从活结点表中取出一个结点作为当前扩展结点。并重复上述结点扩展过程。所以，分支限界法与回溯法的本质区别在于搜索方式的不同。

回溯法更适于处理那些求所有可行解的问题，而分支限界法更适于处理那些只确定一个可行解，特别是最优化问题。11/13/20225第5页，共80页。1.1分支限界法与回溯法的比较分支限界法类似于回溯法，也是一种在问题的解空间树T中搜索问题解的算法。分支限界法与回溯法的求解目标（适用范围）

不同：回溯法适用于找出满足约束条件的所有解的情况；分支限界法发誓找出满足条件的一个解，或某种意义下的最优解。搜索方式不同回溯法：深度优先分支限界法：广度优先11/13/20226第6页，共80页。1.2分支限界法的基本思想分支限界

法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加

入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。11/13/20227第7页，共80页。1.3常见的两种分支限界法从活结点表中选择下一扩展结点的不同方式导致不同的分支限界法：队列式(FI

FO)分支限界法：将活结点表组织成一个队列，按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。优先队列式分支限界法：将活结点表组织成一个优先队列，按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。最大优先队列：使

用最大堆，体现最大效益优先最小优先队列：使用最小堆，体现最小费用优先11/13/20228第8页，共80页。队列式分支限界法的搜索解空间树的方式类似于解空间树的宽度优先搜索，不同的是队列式分支限界法不搜索以不可行结点（已经被判定不能导致可行解或不能导致最优解的

结点）为根的子树。这是因为，按照规则，这样的结点未被列入活结点表。11/13/20229第9页，共80页。优先队列式分支限界法的搜索方式是根据活结点的优先级确定下一个扩展结点。结点的优先级常用一个与该结

点有关的数值p来表示。最大优先队列规定p值较大的结点点的优先级较高。在算法实现时通常用一个最大堆来实现最大优先队列，用最大堆的Deletemax运算抽取堆中的下一个结点作为当前扩展结点，体现最大效益优先的原则。类似地，最小优先队列规

定p值较小的结点的优先级较高。在算法实现时，常用一个最小堆来实现，用最小堆的Deletemin运算抽取堆中下一个结点作为当前扩展结点，体现最小优先的原则。11/13/202210第10页，共80页。采用优先队列式分支定界算法解决具体问题时，应根据问

题的特点选用最大优先或最小优先队列，确定各个结点的p值。11/13/202211第11页，共80页。1.4实例0-1背包问题n=3,c=30,w=[16,15,15],p=[45,25,25]11/13/202212第

12页，共80页。实例分析－0-1背包问题n=3,c=30,w=[16,15,15],p=[45,25,25]队列式分支限界法：[A]B,C=>B,C[B,C]D,E=>E[C,E]F,G=>F,G[E,F,G]J,K=>K(45)[1,0,0][F,G]L,M=>L(50

)[0,1,1]M(25)[G]N,0=>N(25),O(0)不搜索以不可行结点为根的子树优先队列式分支限界法：[A]B,C=>B(45),C(0)[B,C]D,E=>E(45)[E,C]J,K=>K(45)[1,0,0][C]

F,G=>F(25),G(0)[F,G]L,M=>L(50),[0,1,1]M(25)[G]N,O=>N(25),O(0)可用剪枝函数加速搜索11/13/202213第13页，共80页。1.5实例－TSP问题1234206305410ABCDEFGHIJKLMNOPQ

1234344342322423问题描述：某售货员要到若干城市去推销商品，一直各城市之间的路程，他要选定一条从驻地出发，经过每个城市一遍，最后回到住地的路线，使总的路程最短。11/13/202214第14页，共80页。实例分析－TSP问题队列式分支限界法：[B]C,D,

E[C,D,E]F,G[D,E,F,G]H,I[E,F,G,H,I]J,K[F,G,H,I,J,K]L(59)[1,2,3,4,1][G,H,I,J,K]M(66)[H,I,J,K]N(25)[1,3,2,4,1][I,J,K]1-3-4(26)[J,K]P(25)

[K]Q(59)优先队列式分支限界法：[B]C,D,E=>C(30),D(6),E(4)[E,D,C]J,K=>J(14),K(24)[D,J,K,C]H,I=>H(11),I(26)[H,J,K,I,C]N=>N(25)

[1,3,2,4,1][J,K,I,C]P=>P(25)[K,I,C]Q=>Q(59)[I,C]I,C被限界掉1234206305410ABCDEFGHIJKLMNOPQ123434434232242311/13/202215第15页，共80页。1

.6应用分支限界法的关键如何确定合适的限界函数？如何组织活结点表？如何确定最优解中的各个分量？好的限界函数不仅计算简单，还要保证最优解在搜索空间中，更重要的是能在搜索的早期对超出目标函数界的结点进行丢弃，减少搜

索空间，从而尽快找到问题的最优解。通常采用最大堆或最小堆来实现优先队列式分支限界法求解问题。可以用如下方法求得最优解中的分量：1）对每个扩展结点保存该结点到根结点的路径；2）在搜索过程中构建搜索经过的树结构，在求得最优解时，从叶子结点不断回溯到根结点，以确定最优解中

的各个分量。11/13/202216第16页，共80页。提纲一、分支限界法的基本思想二、单源最短路径问题三、装载问题四、0-1背包问题五、最大团问题六、旅行售货员问题11/13/202217第17页，共80页。2.1单源最短路径问题定义在有向图G中，每一边都有一个

非负边权。求图G的从源顶点s到目标顶点t之间的最短路径。11/13/202218第18页，共80页。用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。有向图G的单源最短路径问题产生的解空间

树11/13/202219第19页，共80页。2.2单源最短路径问题算法思想用一最小堆来存储活结点表。其优先级是结点所对应的当前路长。算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点

，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点

优先队列为空时为止。11/13/202220第20页，共80页。2.3剪枝策略在算法扩展结点的过程中，一旦发现一个结点的下界（即结点所对应的当前路长）不小于当前找到的最短路长，则算法剪去以该结点为根的子树。在算法中，还可以利用结点间的控制关系进行剪枝。从源顶点s出发，2条不同路径到

达图G的同一顶点。由于两条路径的路长不同，因此可以将路长长的路径所对应的树中的结点为根的子树剪去。例如，从源点s出发，经过边a,e,q（路长为5）和经过边c,h（路长为6）的2条路径到达图G的同一顶点。故可将后一条路径剪掉。11/13/202221第21页，共80页。剪

枝策略下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树的剪枝情况。BA优于B，B可剪枝经过不同的路径到达相同的顶点A11/13/202222第22页，共80页。2.4算法描述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;//加入活结点优先队列MinHeapNode<Type>N;N.i=j;N.length=di

st[j];H.Insert(N);}try{H.DeleteMin(E);}//取下一扩展结点catch(OutOfBounds){break;}//优先队列空}}顶点i和j间有边，且此路径长小于原先从源点到j的路径长11/13/202223第23页，共80页。实例计算从源顶点1到其它顶

点间最短路径11/13/202224第24页，共80页。1230V2V0V1V4V33825420510计算从源顶点V0到其它顶点间最短路径练习11/13/202225第25页，共80页。提纲一、分支限界法

的基本思想二、单源最短路径问题三、装载问题四、0-1背包问题五、最大团问题六、旅行售货员问题11/13/202226第26页，共80页。3.1问题定义有一批共个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集装箱i的重量为wi，且∑wi≤C1+C2装载问题要求确定是

否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。容易证明：如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。(1)首先将第一艘轮船尽可能装满；(2)将剩余的集装箱装上第二艘轮船。1

1/13/202227第27页，共80页。解装载问题的队列式分支限界法只求出所要求的最优值，稍后将进一步讨论求出最优解。函数MaxLoading具体实施对解空间的分支限界搜索。其中队列Q用于存放活结点表。在队列Q的元素值表示每个活结点所相应的当前载重量。当其值为—1时，表示队

列已到达解空间树同一层结点的尾部。3.2队列式分支限界法11/13/202228第28页，共80页。函数EnQueue用于将活结点加入到活结点队列中。该函数首先检查i是否等于n。如果i＝n，则表示当前活结点为

一个叶结点。由于叶结点不会被进一步扩展，因此不必加入到活结点队列中。此时只要检查该叶结点表示的可行解是否优于当前最优解，并适时更新当前最优解。当i＜n时，当前活结点是一个内部结点，应加入到活结点队列中。11/13/202229第29

页，共80页。voidEnQueue(&Q,Typewt,Type&bestw,inti,intn)//该函数负责加入活结点{//如果不是叶结点，则将结点权值wt加入队列Qif(i==n){//可行叶子结点if(wt>bestw)b

estw=wt;}elseQ.Add(wt);//不是叶子}11/13/202230第30页，共80页。函数MaxLoading在开始时将i初始化为1，bestw初始化为0。此时活结点队列为空。将同层结点尾部标志—1加入到活结点队列中，表

示此时位于第1层结点的尾部。Ew存储当前扩展结点所相应的重量。11/13/202231第31页，共80页。队列式分支限界法在算法的while循环中，首先检测当前扩展结点的左儿子结点是否为可行结点。如果是则将其加入到活结点队列中。然后将其右儿子结点加入到活

结点队列中(右儿子结点一定是可行结点)。2个儿子结点都产生后，当前扩展结点被舍弃。活结点队列中的队首元素被取出作为当前扩展结点，由于队列中每一层结点之后都有一个尾部标记-1，故在取队首元素时，活结点队列一定不空。当取出的元素是-1时，再判断当前队列是否为空。如果队列非空，则将尾部

标记-1加入活结点队列，算法开始处理下一层的活结点。11/13/202232第32页，共80页。队列式分支限界法while(true){//检查左儿子结点if(Ew+w[i]<=c)//x[i]=1En

Queue(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++;}//进入下一层}}11/13/202233第33页，共80页。3.3算法的改进节点的左子树表示将此集装箱装上船，右子树表示不将此集装箱装上船。设bestw是当前最优解；ew是当前扩展结点所相应的重量；r

是剩余集装箱的重量。则当ew+rbestw时，可将其右子树剪去。算法MaxLoading初始时将bestw置为0，直到搜索到第一个叶结点时才更新bestw。因此在算法搜索到第一个叶结点之前，总有bestw＝0，r＞0，故Ew十r＞be

stw总是成立。也就是说，此时右子树测试不起作用。另外，为了确保右子树成功剪枝，应该在算法每一次进入左子树的时候更新bestw的值。11/13/202234第34页，共80页。算法的改进//检查左儿子结点Typewt=Ew+w[i];//左儿子结

点的重量if(wt<=c){//可行结点if(wt>bestw)bestw=wt;//加入活结点队列if(i<n)Q.Add(wt);}提前更新bestw//检查右儿子结点if(Ew+r>bestw&&i<n)Q.Add(Ew);//可能含最优解Q.

Delete(Ew);//取下一扩展结点右儿子剪枝11/13/202235第35页，共80页。算法的改进while(true){//检查左儿子结点Typewt=Ew+w[i];//左儿子结点的重量if(wt<=c){//可行结点if(wt>best

w)bestw=wt;//加入活结点队列if(i<n)Q.Add(wt);}//检查右儿子结点if(Ew+r>bestw&&i<n)Q.Add(Ew);//可能含最优解Q.Delete(Ew);//取下一扩

展结点if(Ew==-1){//同层结点尾部if(Q.IsEmpty())returnbestw;Q.Add(-1);//同层结点尾部标志Q.Delete(Ew);//取下一扩展结点i++;//进入下一层r-=w[i];}}}11/13/2

02236第36页，共80页。3.4构造最优解classQNode{QNode*parent;//指向父结点的指针boolLChild;//左儿子标志Typeweight;//结点所相应的载重量}为了在算法结束后能方便地构造出与最优值相应的最优解，算法必须存储相应子集树中从活结点到根结点的路径。

为此目的，可在每个结点处设置指向其父结点的指针，并设置左、右儿子标志。11/13/202237第37页，共80页。//构造当前最优解for(intj=n-1;j>0;j--){bestx[j]=bestE->LChild

;bestE=bestE->parent;}找到最优值后，可以根据parent回溯到根结点，找到最优解。构造最优解11/13/202238第38页，共80页。3.5优先队列式分支限界法解装载问题的优先队列式分支限界法用最大优先队列存储活结点表。活结点x在优先队列中的优先级定义

为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和。优先队列中优先级最大的活结点成为下一个扩展结点。以结点x为根的子树中所有结点相应的路径的载重量不超过它的优先级。子集树中叶结点所相应的载重量与其优先级相同。在优先队列式分支限界法中，一旦有一个

叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。此时可终止算法。11/13/202239第39页，共80页。上述策略可以用两种不同的方式实现。第一种方式在结点优先队列的每一个活结点中保存从解空间树的根结

点到该活结点的路径，在算法确定了达到最优值的叶结点时，就在该叶结点处同时得到相应的最优解。第二种策略在算法的搜索进程中保存当前已构造出的部分解空间树，这样在算法确定了达到最优值的叶结点时，就可以在解空间树中从该叶结点开始向根结点回溯，构造出相应的最优解。在下面

的算法中，我们采用第二种策略。11/13/202240第40页，共80页。第i十1层结点的剩余重量r[i]定义为r[i]＝。变量E指向子集树中当前扩展结点,Ew是相应的重量。算法开始时，i＝1，Ew＝0，子集树的根结点是

扩展结点。//定义剩余重量数组rint*r=(int*)malloc(sizeof(int)*(n+1));r[n]=0;for(intj=n-1;j>0;j--)r[j]=r[j+1]+w[j+1];11/13/202241第41页，共80页。intMaxLoading(intw[],in

tc,intn){//优先队列式分支限界法，返回最优载重量，bestx返回最优解//定义最大堆的容量为1000//MaxHeap<HeapNode<Type>>H(1000);head=(HeapNode*)malloc(sizeof(HeapNode));

if(head==NULL){printf("没有足够的空间分配\n");return1;}head->level=0;head->next=NULL;head->ptr=NULL;head->uweight=0;//定义剩余重量数组rint*r=(int*)malloc(sizeof(i

nt)*(n+1));r[n]=0;for(intj=n-1;j>0;j--)r[j]=r[j+1]+w[j+1];//初始化inti=1;//当前扩展结点所处的层bbnode*E=0;//当前扩展结点intE

w=0;//扩展结点所相应的载重量11/13/202242第42页，共80页。优先队列式分支限界法While循环体产生当前扩展结点的左右儿子结点。如果当前扩展结点的左儿子结点是可行结点，即它所相应的重量末超过船载容量，

则将它加入到子集树的第i十1层上，并插入最大堆。扩展结点的右儿子结点总是可行的，故直接插入子集树的最大堆中。接着算法从最大堆中取出最大元素作为下一个扩展结点。如果此时不存在下一个扩展结点，则相应的问题无可行解。如果下一个扩展结点是

一个叶结点，即子集树中第n十1层结点，则它相应的可行解为最优解。该最优解所相应的路径可由子集树中从该叶结点开始沿结点父指针逐步构造出来。具体算法可描述如下：11/13/202243第43页，共80页。while

(i!=n+1){//非叶结点//检查当前扩展结点的儿子结点if(Ew+w[i]<=c){//左儿子结点为可行结点AddLiveNode(E,Ew+w[i]+r[i],true,i+1);}AddLiv

eNode(E,Ew+r[i],false,i+1);//右儿子结点HeapNode*N;//取下一扩展结点DeletMax(N);//非空i=N->level;E=N->ptr;Ew=N->uweight-r[i-1];//优先权uwei

ght=Ew+r[i-1];}11/13/202244第44页，共80页。for(j=n;j>0;j--){//构造当前最优解{bestx[j]=E->LChild;E=E->parent;}returnEw;}构造当前最

优解11/13/202245第45页，共80页。提纲一、分支限界法的基本思想二、单源最短路径问题三、装载问题四、0-1背包问题五、最大团问题六、旅行售货员问题11/13/202246第46页，共80页。4.1问题定义给定n种物品和一个背包，物品i的重量是wi

，价值pi,背包容量为C，问如何选择装入背包的物品，使装入背包中的物品的总价值最大？对于每种物品只能选择完全装入或不装入，一个物品至多装入一次。11/13/202247第47页，共80页。4.2算法思想首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小

进行排列。在优先队列分支限界法中，节点的优先级由已装入背包的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子

结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时即为问题的最优值。11/13/202248第48页，共80页。4.3上界函数template<classTypew,classTypep>TypepKnap<Typew,Typep>::Bou

nd(inti){//计算结点所相应价值的上界Typewcleft=c-cw;//剩余容量Typepb=cp;//价值上界//以物品单位重量价值递减序装满剩余背包容量while(i<=n&&w[i]<=cleft){cleft-=w[i];b+=p[i];i++;}//装填剩余

容量至装满背包if(i<=n)b+=p[i]/w[i]*cleft;returnb;}11/13/202249第49页，共80页。4.4算法描述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);//取下一个扩展节点（略）}分支限界搜索过程11/13/202250第50页，共80页。提纲一、分支限界法的基本思想二、单源最短路径问题三、装载问题四、0-1背包

问题五、最大团问题六、旅行售货员问题11/13/202251第51页，共80页。5.1问题定义给定无向图G=(V，E)。如果UV，且对任意u，vU有(u，v)E，则称U是G的完全子图。G的完全子图U是G的团当且仅当U不包含在G的更大的完全子

图中。G的最大团是指G中所含顶点数最多的团。下图G中，子集{1，2}是G的大小为2的完全子图。这个完全子图不是团，因为它被G的更大的完全子图{1，2，5}包含。{1，2，5}是G的最大团。{1，4，5}和{2，3，5}也是G的最大团。11/13/202252第52页，共80页。5.2

算法思想子集树的根结点是初始扩展结点，对于这个特殊的扩展结点，其cliqueSize的值为0。算法在扩展内部结点时，首先考察其左儿子结点。在左儿子结点处，将顶点i加入到当前团中，并检查该顶点与当前团中其它顶点之间是否有边相连。当顶

点i与当前团中所有顶点之间都有边相连，则相应的左儿子结点是可行结点，将它加入到子集树中并插入活结点优先队列，否则就不是可行结点。接着继续考察当前扩展结点的右儿子结点。当右儿子结点满足上界函数（upperSize>bestn）时，右子树中可能

含有最优解，此时将右儿子结点加入到子集树中并插入到活结点优先队列中。11/13/202253第53页，共80页。5.3上界函数用变量cliqueSize表示与该结点相应的团的顶点数；level表示结点在子集空间树中所处的层次；用cliqueSize+n-level+

1作为顶点数上界upperSize的值。在此优先队列式分支限界法中，upperSize实际上也是优先队列中元素的优先级。算法总是从活结点优先队列中抽取具有最大upperSize值的元素作为下一个扩展元素。11/13/202254第54页，共80

页。5.4算法描述具体算法略（见课本）。算法的while循环的终止条件是遇到子集树中的一个叶结点(即n+1层结点)成为当前扩展结点。对于子集树中的叶结点，有upperSize＝cliqueSize。此时活结点优先队列中剩余结点的upperSize值均不超过当前扩展结点的upperSiz

e值，从而进一步搜索不可能得到更大的团，此时算法已找到一个最优解。11/13/202255第55页，共80页。提纲一、分支限界法的基本思想二、单源最短路径问题三、装载问题四、0-1背包问题五、最大团问题六、旅行

售货员问题11/13/202256第56页，共80页。6.1问题定义某售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费)。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费)最小。路线是一个带权图。图中各边

的费用（权）为正数。图的一条周游路线是包括V中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。旅行售货员问题的解空间可以组织成一棵树，从树的根结点到任一叶结点的路径定义了图的一条周游路线。旅行售货员问题要在图G中找出费用最

小的周游路线。11/13/202257第57页，共80页。6.2算法思想算法开始时创建一个最小堆，用于表示活结点优先队列。堆中每个结点的子树费用的下界lcost值是优先队列的优先级。接着算法计算出图中每个顶点的最小费用出边并用minout记录。如果所给的有向图中某个顶点没有出边，

则该图不可能有回路，算法即告结束。如果每个顶点都有出边，则根据计算出的minout作算法初始化。算法的while循环体完成对排列树内部结点的扩展。对于当前扩展结点，算法分2种情况进行处理：11/13/202258第58页，共80页。6.2算法思想1、首先

考虑s=n-2的情形，此时当前扩展结点是排列树中某个叶结点的父结点。如果该叶结点相应一条可行回路且费用小于当前最小费用，则将该叶结点插入到优先队列中，否则舍去该叶结点。2、当s<n-2时，算法依次产生当前扩展结点的所有儿子结点。由于当

前扩展结点所相应的路径是x[0:s]，其可行儿子结点是从剩余顶点x[s+1:n-1]中选取的顶点x[i]，且(x[s]，x[i])是所给有向图G中的一条边。对于当前扩展结点的每一个可行儿子结点，计算出其前缀(x[0:s]，x[i])的费用cc和相应的下界lcost。当lcost<bes

tc时，将这个可行儿子结点插入到活结点优先队列中。11/13/202259第59页，共80页。6.2算法思想算法中while循环的终止条件是排列树的一个叶结点成为当前扩展结点。当s=n-1时，已找到

的回路前缀是x[0:n-1]，它已包含图G的所有n个顶点。因此，当s=n-1时，相应的扩展结点表示一个叶结点。此时该叶结点所相应的回路的费用等于cc和lcost的值。剩余的活结点的lcost值不小于已找到的回路的费用。它们都不可能导致费用

更小的回路。因此已找到的叶结点所相应的回路是一个最小费用旅行售货员回路，算法可以结束。算法结束时返回找到的最小费用，相应的最优解由数组v给出。11/13/202260第60页，共80页。6.3算法描述11/13/

202261第61页，共80页。11/13/202262第62页，共80页。11/13/202263第63页，共80页。11/13/202264第64页，共80页。11/13/202265第65页，共80页。算法中while循环的终止条件是排列树的一个叶结点成为当前扩展结点。当s

＝n—1时，已找到的回路前缀是x[0：n—1]，它已包含图G的所有n个顶点。因此，当s＝n—1时，相应的扩展结点表示一个叶结点。此时该叶结点所相应的回路的费用等于cc和lcost的值。剩余的活结点的1cost值不小于己找

到的回路的费用。它们都不可能导致费用更小的回路。因此已找到的叶结点所相应的回路是一个最小费用旅行售货员回路，算法可以结束.11/13/202266第66页，共80页。算法的while循环体完成对排列树内部结点的扩展。对于当前扩展结点，算法分两种情况进行处理。首先；考虑s＝n—2的情形。此时当前扩

展结点是排列树中某个叶结点的父结点。如果该叶结点相应一条可行回路且费用小于当前最小费用，则将该叶结点插入到优先队列中，否则舍去该叶结点。当s＜n-2时，算法依次产生当前扩展结点的所有儿子结点。由于当前扩展结点所相应

的路径是x[0:s]，其可行儿子结。点是从剩余顶点x[s+1:n-1]中选取的顶点xIj]，且(x[s]，x[i])是所给有向图G中的一条边。对于当前扩展结点的每一个可行儿子结点，计算出其前缀(x[0:s]，x[i])的费用cc和相应的下界Lcost。当lcost＜bestc时，将这个可

·行儿子结点插入到活结点优先队列中。11/13/202267第67页，共80页。试写出0/1背包问题的优先队列式分枝限界算法程序，并找一个物品件数为16的例子检验程序的运行情况。上机11/13/202268第68页，共80页。回溯法与分支限界法的用法取向探讨1

.基本思想分析回溯法的基本思想:首先确定解空间的组织结构,接着就从开始结点(根结点)出发,以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点,同时也成为当前的扩展结点。在当前的扩展结点处,搜索向

纵深方向移至一个新结点。这个新结点就成为一个新的活结点,并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动,则当前扩展结点就成为死结点。换句话说,这个结点不再是一个活结点。此时,应往回移动(回溯)至最近的一个活结点处,并

使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索,直至找到所要求的解或解空间中已没有活结点时为止。11/13/202269第69页，共80页。分支限界法的基本思想:确定解空间的组织结构,以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。在搜索问题的解空间树时

,分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中,每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点,就一次性产生其所有儿子结点。在这些儿子结点中,那些导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被子加

入活结点表中。此后,从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。11/13/202270第70页，共80页。用法比较分支限界法类似

于回溯法,也是一种在问题的解空间树T上搜索问题解的算法。但在一般情况下,分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解,即在某种意义下的最优解。

11/13/202271第71页，共80页。由于求解目标不同,导致分支限界法与回溯法在解空间树T上的搜索方式也不相同。回溯法以深度优先的方式搜索解空间树T,而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T

。分支限界法的搜索策略是:在扩展结点处,先生成其所有的儿子结点(分支),然后再从当前的活结点表中选择下一个扩展对点。为了有效地选择下一扩展结点,以加速搜索的进程,在每一活结点处,计算一个函数值(限界),并根据这些已计算出的函数值,从当前活结点表中选择一个最有利的结点作为扩展结点,使搜索朝着解

空间树上有最优解的分支推进,以便尽快地找出一个最优解。11/13/202272第72页，共80页。分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。问题的解空间树是表示问题解空间的一棵有序树,常见的有子集树和排列树。在搜索问题的解空间树时,分支限界法与

回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中,每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点,就一次性产生其所有儿子结点。在这些儿子结点中,那些导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被子

加入活结点表中。此后,从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。11/13/202273第73页，共80页。方法空间树的搜索方式存储

结点的常用数据结构结点存储特性常用应用回溯法深度优先搜索深度优先搜索堆栈活结点的所有可行子结点被遍历后才被从栈中弹出找出满足约束条件的所有解分支限界法广度优先或最小消耗优先搜索队列、优先队列每个结点只有一次成为活结点的机会找出满足约束条件的一个解

或特定意义下的最优解11/13/202274第74页，共80页。用法举例(1)一个比较适合采用回溯法解决的问题-n后问题。(2)一个既可以采用回溯法也可以采用分支限界法解决的问题———0-1背包问题。11/13/202275第75页，共80页。n后问题的解空间树

是一棵排列树,一旦一种组合是一种解,则解与解之间不存在优劣的分别。直到搜索到叶节点时才能确定出一组解。这时我们用回溯法可以系统地搜索问题的全部解,而且由于解空间树是排列树的特性,在最坏的情况下,堆栈的深度不会超过n。如果采取分支限界法,在解空间

树的第一层就会产生n个活结点,如果不考虑剪枝,将在第二层产生n*(n-1)个活节点,如此下去对队列空间的要求太高。n后问题不适合使用分支限界法处理的根源是它需要找处所有解的组合,而不是某种最优解(事实上也没有最优解可言)。11/13/202276

第76页，共80页。0-1背包问题的解空间树是一棵子集树,所要求的解具有最优性质。如果采用回溯法解决这个问题,可采用如下的搜索策略:只要一个结点的左儿子结点是一个可行结点就搜索其左子树;而对于右子树,需要用贪心算法构造一个上界函数,这个函数表明这个结点的子树所能达

到的可能的最大容量(因为只有将0-1背包问题改变为背包问题才可能利用贪心算法,因此这个上界函数在绝大多数情况下不会是上确界函数),只在这个上界函数的值超过当前最优解时才进入搜索。随着搜索进程的推进,最优解不断得到加强,对搜索的限制就越来越严格。11/13/202277第7

7页，共80页。如果采用分支限界法解决这个问题,同样需要用到贪心算法构造的上界函数。所不同的是,这个上界函数的作用不在于判断是否进入一个结点的子树继续搜索,因为在搜索到达叶节点之前,大家也无法知道已经得到的最优解是什么。在这里,可用一个最大堆来实现活结点的优先队列,上界函数

的值将作为优先级,这样一旦有一个叶结点成为扩展结点,就表明已经找到了最优解。11/13/202278第78页，共80页。可以看出,用两种方法处理0-1背包问题都有一定的可行性。相比之下回溯法的思路容易

理解一些,但是这是一个寻找最优解的问题。由于采用了优先队列处理,不同的结点不再像n后问题那样没有相互之间的牵制和联系,用分支限界法处理效果一样很好。11/13/202279第79页，共80页。回溯和分支限界都是以构造一颗状态空间树为基础的,树的节点反映了对一个部

分解所作的特定选择。如果可以保证,节点子孙所对应的选择不可能得出问题的一个解,两种技术都会立即停止处理这个节点。两种技术的区别在于它们能够处理的问题类型不同。分支限界法只能应用于最优问题,因为它基于针对一个问题的目标

函数,计算其可能值的边界。掌握这点,正确选择这两种算法,求解问题将取到事半功倍的效率。11/13/202280第80页，共80页。