第6章分支限界法2015

1第6章分支限界法学习要点理解分支限界法的剪枝搜索策略。掌握分支限界法的算法框架（1）队列式(FIFO)分支限界法（2）优先队列式分支限界法通过应用范例学习分支限界法的设计策略。2第6章分支限界法6.1分支界限法的基本思想6.2单源最短路径问题6.3装载问题6.40-1背包问题6.5货郎担问题36.1 分支限界法的基本思想1.分支限界法与回溯法的不同（1）求解策略：回溯法的求解过程属于盲目搜索，而分支限界法的求解过程是有选择地朝有利于获得问题解或最优解的方向搜索。4（2）适用场合：回溯法适用于寻找满足约束条件的所有解，而分支界限法适用于寻找满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。（3）搜索方式：回溯法以深度优先的方式搜索解空间树；分支限界法以广度优先或以最小耗费优先的方式搜索解空间树。5分支限界法的搜索策略是：在扩展结点处，先生成其所有的儿子结点（分支），——从当前的活结点表中选择下一个扩展结点。为有效选择下一扩展结点，加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，尽快找出一个最优解。62.分支限界法基本思想分支限界法采用广度优先或最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次成为扩展结点的机会。活结点一旦成为扩展结点，就一次性产生所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被剪掉，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到满足约束条件的解或活结点表为空时为止。73.常见的两种分支限界法（1）队列式(FIFO)分支限界法按照队列先进先出（FIFO）原则选取下一个结点成为扩展结点。（队列）

（2）优先队列式分支限界法按照优先队列中规定的优先级选取优先级最高的结点成为当前扩展结点。（利用堆排序）8堆具有如下性质：（1）堆是一棵完全二叉树，k1为根结点。（2）堆的根结点是元素序列中的值最小或最大元素。根元素为最小元素的堆称为最小堆，根元素为最大元素的堆称为最大堆。（3）堆中任一子树也是堆。

堆排序是利用堆顶记录的关键值最小（或最大）的性质，从当前待排序列中依次选取关键字最小（或最大）的记录来进行选择排序的一种方法。在堆排序过程中，需要做两方面的工作：(1)怎样将给定的待排序记录构成一个初始堆；（2）输出关键字最小（大）的记录后，如何将剩余记录整理成一个新的堆。9堆是n个元素的序列H={k1,k2,…kn},它满足如下关系：或者根据堆的定义，堆可以看成一棵以k1为根的完全二叉树。元素序列为{1,4,3,5,6,7,9,10,8}914356781064513210优先队列中规定的结点优先级常用一个与该结点相关的数值p来表示，结点优先级的高低与p值的大小相关。最大优先队列中规定p值较大的结点优先级较高。最小优先队列中规定p值较小的结点优先级较高。最大堆实现最小堆实现用优先队列式分支限界法解具体问题时，根据具体问题的特点确定选用最大优先或最小优先队列来表示解空间的活结点表。11用队列式分支限界法解此问题时，用一个队列来存储活结点表。队头队尾活结点队列起始结点为ABC

不可解BECFG

不可解EKFLMGNO对于n=3时的0-1背包问题，考虑下面例子：w=[16,15,15],p=[45,25,25],c=30。12队列式分支限界法搜索解空间树的方式与解空间树的广度优先遍历算法极为类似。唯一不同之处是队列式分支限界法不搜索以不可行结点为根的子树。优先队列式分支限界法也是从根结点A开始搜索解空间树的。用极大堆来表示活结点表的优先队列，该优先队列的优先级定义为活结点所获得的价值。13w=[16,15,15],p=[45,25,25],c=30。初始堆为空，扩展结点A得到它的2个儿子结点B，C。

价值45

价值0

不可解

价值45

不可解

价值45

01114寻求一个最优解时，类似可用剪枝函数来加速搜索。函数给出每一个可行结点相应子树可能获得的最大价值的上界。（如此上界不会比当前最优值更大）说明：相应的子树中不含问题的最优解，可以剪去。另一方面，可将上界函数确定的每个结点的上界值作为优先级，以该优先级的非增序抽取当前扩展结点。可更迅速的找到最优解。15旅行售货员问题：ABCDEFGHIJKLMNOPQ12343444433322221432301020456

初始扩展结点CDECFGDHIEJKFL

费用为5916ABCDEFGHIJKLMNOPQ1234344443332222用极小堆来存储活结点表，其优先级是结点当前的费用。

初始扩展结点1432301020456结点E被扩展。17可以用一个限界函数在搜索过程中裁剪子树，减少活结点。此剪枝函数是当前结点扩展后得到的最小费用的一个下界。如果在当前扩展结点处，这个下界不比当前最优值更小，则以该结点为根的子树可以剪去。另一方面，也可以把每个结点的下界作为优先级，依非减序从活结点优先队列中抽取下一个扩展结点。186.2 单源最短路径问题单源最短路径问题：在下图所给的有向图G中，每一边都有一个非负边权。求图G的从源顶点①到目标顶点⑤之间的最短路径。123452144358111113323445Dijkstra算法过程19队列式（FIFO）分支限界法123452144358135254452488936511队列：41325455520优先队列式分支限界法123452144358123545428365923524552555利用堆依据优先级选择21算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。22下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。23剪枝策略在算法扩展结点的过程中，一旦发现一个结点的下界不小于当前找到的最短路长，则算法剪去以该结点为根的子树。在算法中，利用结点间的控制关系进行剪枝。从源顶点s出发，2条不同路径到达图G的同一顶点。由于两条路径的路长不同，因此可以将路长长的路径所对应的树中的结点为根的子树剪去。24float[]dist:从源点到各顶点的最短路径int[]p:路径中当前顶点的前驱结点初始化堆，dist[]=∞；while(true){for(j=1;j<n;j++){if(顶点i到顶点j可达，且更短

){dist[j]=保留路径长度；p[j]=i;

将顶点j加入堆中；

}}if(堆空)break;else出堆；}伪语言优先队列式分支限界法25

while(true){//搜索问题的解空间

for(intj=1;j<=n;j++){if(a[enode.i][j]<MAX_VALUE&&enode.length+a[enode.i][j]<dist[j]){//顶点i到顶点j可达，且满足控制约束

dist[j]=enode.length+a[enode.i][j];p[j]=enode.i;HeapNode*node=newHeapNode(j,dist[j]);heap.put(&node);//加入活结点优先队列}

}if(heap.isEmpty())break;elseenode=(HeapNode)heap.removeMin();}路径长度length结点编号i堆结点结构266.3装载问题1.问题描述有n个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集装箱i的重量为Wi，且装载问题要求确定是否有一个合理的装载方案可以将这些集装箱装上这2艘轮船。如果有，找出一种装载方案。27可以证明：如果装载问题有解，则采用下面的策略可得到装载方案。(1)首先将第1艘轮船尽可能装满；(2)将剩余的集装箱装上第2艘轮船。282.队列式分支限界法在算法中，不断重复下列操作，直到队列空为止。检测当前扩展结点的左儿子结点是否为可行结点。if(可行)将其加入到活结点队列中；将其右儿子结点加入到活结点队列中(右儿子结点一定是可行结点)。注意：当2个儿子都产生后，当前扩展结点被舍弃。29举例：w=[3,5,2,1]c=7012ew=3ew=03478ew=51314ew=61516ew=4561020ew=6ew=5919ew=7ew=81122ew=321ew=2122423ew=11817ew=830建立一个用于存放活结点的队列queue，又称为活结点队列。队列中元素的值表示活结点对应的当前载重量(ew)。为了便于处理，在解空间树中，在同层最后一个结点之后，在队列中添加一个-1。31活结点队列中的队首元素被取出作为当前扩展结点，由于队列中每一层结点之后都有一个尾部标记-1，故在取队首元素时，活结点队列一定不空。当取出的元素是-1时，再判断当前队列是否为空。如果队列非空，则将尾部标记-1加入活结点队列，算法开始处理下一层的活结点。32while(true){

if(ew+w[i]<=c)enQueue(ew+w[i],i);//检查左儿子结点

enQueue(ew,i);ew=queue.front();//取下一扩展结点queue.pop();

if(ew==-1){if(queue.isEmpty())returnbestw;queue.push(-1);//同层结点尾部标志

ew=queue.front();//取下一扩展结点queue.pop();

i++;//进入下一层

}}voidenQueue(intwt,inti){if(i==n){//到叶子结点更新bestwif(wt>bestw)bestw=wt;}elsequeue.push(wt);}33举例：n=3,w=[8,6,2],W=1234举例：n=3,w=[8,6,2],W=12初始化队列如图(a)所示。此时，队列非空，节点B和C依次进入队列。如图(b)所示。值得注意的是，实际进入队列的是数值8和0，这里用节点B和C分别代替8和0，每个节点所代表的数值见其旁边矩形中的数字，也就是约束函数值。B节点约束函数值为8，表示当前目标函数的下界为8。-1出队列，而且此时队列非空，因此-1进队列，同时节点B出队列，如图(c)所示。展开节点B，由于B节点的1分支节点的约束函数值为14，大于船的载重量12，因此1分支被剪支，B节点的0分支节点E无条件进队列，如图(d)所示。分支限界C节点出队列，该节点为扩展节点，如图(e)所示。展开节点C，C节点的两个分支节点F和G均可以进入队列，如图(f)所示。从队列中取出扩展节点E，如图(g)所示。将节点E展开，其两个分支节点J和K均为叶节点，不再展开。如图(h)所示。此时，E节点的1分支节点J的约束函数值为10，表示当前目标函数值的下界更新为10，得到一个解[1,0,1]，其重量为10。从队列中依次取出扩展节点F和G，将其展开，其分支节点为叶子，如图(i)所示。此时队列为空，搜索停止。如图(j)所示。373.算法的改进结点的左子树表示将此集装箱装上船，右子树表示不将此集装箱装上船。设bestw是当前最优解；ew是当前扩展结点所相应的重量；r是剩余集装箱的重量。当ew+r>bestw时，才有可能存在更优解，否则将其右子树剪去。38算法的改进//检查左儿子结点intwt=ew+w[i];if(wt<=c){//可行结点//加入活结点队列

if(i<n)queue.push(wt);}//检查右儿子结点

if(ew+r>bestw&&i<n)//可能含最优解

queue.push(ew);ew=queue.front();queue.pop();//取下一扩展结点

……..;39算法的改进//检查左儿子结点intwt=ew+w[i];if(wt<=c){//可行结点

if(wt>bestw)bestw=wt;

//加入活结点队列

if(i<n)queue.push(wt);}//检查右儿子结点

if(ew+r>bestw&&i<n)//可能含最优解

queue.push(ew);ew=queue.front();queue.pop();//取下一扩展结点

……….;为了尽早剪掉无用的右子树，可以在每次进入左子树时更新bestw的值。40举例（同前例）：n=3,w=[8,6,2],W=1241举例：n=3,w=[8,6,2],W=12最初解空间树如图(a)所示。图(b)中，两个节点B和C是活节点，B的最大收益值是16，因此B是扩展节点。优先扩展B，得到图(c)。由于节点D不满足约束条件，因此不会放入活节点表，即它被杀死，当前活节点为C和E。由于E具有更大的上界函数值，因此E被优先扩展，得到图(d)。E的1分支节点J已经是叶节点，J不会放入活节点表，被杀死。此时J获得载重量为10，等于其上界函数值10，而J的上界函数值是当前活节点中上界值最大的，因此，扩展其他节点不会得到比10还大的载重量。因此，分支限界搜索被终止。获得最优解[1,0,1]，其最优载重量为10。434.构造最优解为了在算法结束后能构造出最优解，必须存储相应子集树中从活结点到根的路径。为此，可在每个结点处设置指向父结点的指针，同时设置左、右儿子标志。

structQNode{

QNodeparent;//父结点booleanleftChild;//左儿子标志intweight;//结点所相应的载重量};44找到最优值后，可以根据parent，从叶子结点回溯到根结点，找到最优解。//构造当前最优解for(intj=n;j>0;j--){bestx[j]=(e.leftChild)?1:0;e=e.parent;}455.优先队列式分支限界法解装载问题的优先队列式分支限界法用最大优先队列存储活结点表。活结点x在优先队列中的优先级定义为ew+r。46优先队列中优先级最大的活结点成为下一个扩展结点。以结点x为根的子树中所有结点相应的路径的载重量不超过它的优先级。子集树中叶结点所相应的载重量与其优先级相同。在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。此时终止算法。47举例：n=3,w=[8,6,2],W=1248举例：n=3,w=[8,6,2],W=12496.40-1背包问题算法的思想首先，对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。

在优先队列分支限界法中，结点的优先级为：

由已装入的物品价值+剩余的最大单位重量价值的物品装满剩余容量的价值和。

50算法处理过程：首先检查当前扩展结点的左儿子结点是否可行。如果左儿子是可行结点，将其加入到活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入到活结点优先队列。当扩展到叶结点时得到问题的最优值。51计算上界函数bound(i)//n表示物品总数，cleft为剩余重量=c-cwwhile(i<=n&&w[i]<=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为上界值52

while(i<=n){//非叶结点wt=cw+w[i];if(wt<=c){//左儿子结点为可行结点

if(cp+p[i]>bestp)bestp=cp+p[i];addLiveNode(up,cp+p[i],cw+w[i],i+1,enode,true);}up=bound(i+1);if(up>=bestp)//检查右儿子结点addLiveNode(up,cp,cw,i+1,enode,false);

//取下一个扩展节点（略）}bestp:当前最优价值cp:当前总价值cw:当前总重量536.5货郎担问题1.问题描述

某售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费)。要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费)最小。

54路线是一个带权图。图中各边的费用（权）为正数。图的一条周游路线是包括V中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。

123430620105455货郎担问题的解空间可以组织成一棵排列树，从树的根结点到任一叶结点的路径定义了图的一条周游路线。货郎担问题要在图G中找出费用最小的周游路线。56

4城市货郎但问题的解空间是一棵排列树。利用优先队列式分支限界法求解，可用一极小堆来存储活结点表。其优先级是结点的当前费用。算法从排列树的结点B和空优先队列开始。结点B被扩展后，他的3个儿子结点被一次插入堆中。此时，由于E是堆中具有最小当前费用的结点，所以处于堆顶的位置，他自然成为下一个扩展结点。结点E被扩展后，其儿子结点J和K被插入当前堆中，他们的费用分别为14和24。此时堆顶元素为D，他成为下一个扩展结点。他的2个儿子结点被插入堆中。此时堆中含有结点C,H,I,J,K。结点H具有最小费用，从而成为下一个扩展结点。扩展结点H后得到一条回路（1，3，2，4，1）,相应的费用为25。接下来结点J成为扩展结点，由此得到另一条费用25的回路（1，4，2，3，1）。此后的两个扩展结点是K和I。由结点k得到的可行解费用高于当前最优解，结点I、C本身的费用已高于当前最优解，从而他们都不能得到更好的解。最后，优先队列为空，算法终止。463010520572.算法描述（最小权值分支界限法）

首先，创建一个最小堆，用于表示活结点优先队列。堆中每个结点存储从根结点到该活结点的相应路径长度。堆结点中包括：

int[]x:用于记录当前解

s:结点在排序树中的层次，从0到s的路径为x[0:s]

cc:表示当前费用

lcost：子树费用的下界,是队列的优先级

rcost：是x[s:n-1]中最小出边费用和58在实现过程中，用邻接矩阵表示给的图G。每个结点的lcost作为优先队列的优先级。基本处理过程为：计算图中每个顶点的最小费用出边并用minout记录。如果所给的有向图中某个顶点没有出边，则该图不可能有回路，算法结束，否则继续后续的处理。59//第一个扩展结点是Bwhile(没有到叶子结点）{//完成对排列树内部结点的扩展。

if(扩展结点是叶子结点的父结点（n-2)){

if(有回路且更优){记录最优值，并将该叶结点插入到优先队列中

}

}else{依次产生当前扩展结点的所有儿子结点。由于当前扩展结点所相应的路径是x[0:s]，其可行儿子结点从剩余顶点x[s+1:n-1]中选取x[i]，且(x[s]，x[i])是所给有向图G中的一条边。对于当前扩展结点的每一个可行儿子结点，如果有可能产生更优解，将其插入优先队列中。

}

从优先队列中取下一个结点作为新的扩展结点}606.6作业分配问题n个操作员以n种不同时间完成n种不同作业。要求分配每位操作员完成一项工作，使完成n项工作的总时间最少。利用分支限界法解作业分配问题。方便起见，把n个操作员编号为0,1,...,n-1，把n个作业也编号为0,1,...,n-1。用矩阵c来描述每位操作员完成每个作业时所需的时间。例如，元素cij

表示第i位操作员完成第j号作业所需的时间。下图是4个操作员完成4个作业所需的时间表。求解作业最优分配方案。

613841291213587931276801230123（作业）

第0行的4个数据分别表示第0位操作员完成4个作业所需时间。当把第0号作业分配给第0位操作员时，c00=3.

而1号作业分别由其余3位操作员单独完成时，最短时间是7，第2号作业最短时间为6，第3号作业最短时间为3。因此当把第0号作业分配给第0位操作员时，所需时间至少不会少于3+7+6+3=19，可以把它看成是在根节点下第0个儿子节点的下界。如果把第0号作业分配给第1位操作员时，所需时间至少不会小于9+7+4+3=23，可以把它看成是在根节点下第1个儿子节点的下界。62令tik表示在某个搜索深度k下，把作业k分配给操作员i时的时间下界。则当k=0时，有t00=3+7+6+3=19t10=9+7+4+3=23t20=8+7+4+5=24t30=12+7+4+3=26于是在根节点下建立4个儿子节点2、3、4、5，对应于把第0号作业分别分配给第0、1、2、3号操作员，其下界分别为19，23，24，26。把这些节点都插入最小堆中，这时节点2的下界最小。把它从堆顶取下，并由它向下继续搜索，生成3个儿子节点，分别为6、7、8。……524316211234311020301923242678112100229101232211113213841291213587931276801230123636.7布线问题问题的提出：印刷电路板将布线区域划分成n*m个方格阵列，要求确定连接方格a的中点到方格b的中点的最短布线方案。在布线时，电路只能沿直线或直角布线，为了避免线路相交，已布了线的方格做了封锁标记，其他线路不允许穿过被封锁的方格。ab641.算法思想讨论用队列分支限界法来解布线问题。布线问题的解空间是一个图。解此问题的队列式分支限界法从起始位置a开始将它作为第一个扩展结点。与该扩展结点相邻并且可达的方格成为可行结点被加入到活结点队列中，并且将这些方格标记为1，即从起始方格a到这些方格的距离为1。65接着，算法从活结点队列中取出队首结点作为下一个扩展结点，并将与当前扩展结点相邻且未标记过的方格标记为2，并存入活结点队列。这个过程一直继续到算法搜索到目标方格b或活结点队列为空时为止。即加入剪枝的广度优先搜索。66Positionoffset[4];offset[0].row=0;offset[0].col=1;//右

offset[1].row=1;offset[1].col=0;//下

offset[2].row=0;offset[2].col=-1;//左

offset[3].row=-1;offset[3].col=0;//上定义移动方向的相对位移67设置边界的围墙

for(inti=0;i<=m+1;i++)grid[0][i]=grid[n+1][i]=1;//顶部和底部

for(inti=0;i<=n+1;i++)grid[i][0]=grid[i][m+1]=1;//左翼和右翼68for(inti=0;i<NumOfNbrs;i++){nbr.row=here.row+offs