计算机算法设计与分析第6章分支限界法课件

1、计算机算法设计与分析 Design and Analysis of Computer Algorithms 第六章 分支限界法Branch-and-Bound Algorithm第1页，共80页。理解分支限界法的剪枝搜索策略。掌握分支限界法的算法框架队列式(FIFO)分支限界法优先队列式分支限界法通过应用范例学习分支限界法的设计策略。单源最短路径问题装载问题；布线问题0-1背包问题；最大团问题；旅行售货员问题电路板排列问题批处理作业调度问题学习要点7/29/20222第2页，共80页。提纲一、分支限界法的基本思想二、单源最短路径问题三、装载问题四、0-1背包问题五、最大团问题六、旅行售货员问题

2、7/29/20223第3页，共80页。提纲一、分支限界法的基本思想二、单源最短路径问题三、装载问题四、0-1背包问题五、最大团问题六、旅行售货员问题7/29/20224第4页，共80页。分支限界法同回溯法类似，它也是在解空间中搜索问题的可行解或最优解，但搜索的方式不同。回溯法采用深度优先的方式，朝纵深方向搜索，直至达到问题的一个可行解，或经判断沿此路径不会达到问题的可行解或最优解时，停止向前搜索，并沿原路返回到该路径上最后一个还可扩展的结点。从该结点出发朝新的方向纵深搜索。分支定界法则采用宽度优先的方式搜索解空间树，它将活结点存放在一个特殊的表中。其策略是：在扩展结点处，先生成其所有的儿子结点

3、,将那些导致不可行解或导致非最优解的儿子舍弃，其余儿子加入活结点表中。此后，从活结点表中取出一个结点作为当前扩展结点。并重复上述结点扩展过程。所以，分支限界法与回溯法的本质区别在于搜索方式的不同。回溯法更适于处理那些求所有可行解的问题，而分支限界法更适于处理那些只确定一个可行解，特别是最优化问题。7/29/20225第5页，共80页。1.1 分支限界法与回溯法的比较分支限界法类似于回溯法，也是一种在问题的解空间树T中搜索问题解的算法。分支限界法与回溯法的求解目标（适用范围）不同：回溯法适用于找出满足约束条件的所有解的情况；分支限界法发誓找出满足条件的一个解，或某种意义下的最优解。搜索方式不同回

4、溯法：深度优先分支限界法：广度优先7/29/20226第6页，共80页。1.2 分支限界法的基本思想分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。7/29/20227第7页，共80页。1.3 常见的两种分支限界法从活结点表中选择下一扩展结点的不同方式

5、导致不同的分支限界法：队列式(FIFO)分支限界法：将活结点表组织成一个队列，按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。优先队列式分支限界法：将活结点表组织成一个优先队列，按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。最大优先队列：使用最大堆，体现最大效益优先最小优先队列：使用最小堆，体现最小费用优先7/29/20228第8页，共80页。 队列式分支限界法的搜索解空间树的方式类似于解空间树的宽度优先搜索，不同的是队列式分支限界法不搜索以不可行结点（已经被判定不能导致可行解或不能导致最优解的结点）为根的子树。这是因为，按照规则，这样的结点未被列入活结点表。7/2

6、9/20229第9页，共80页。优先队列式分支限界法的搜索方式是根据活结点的优先级确定下一个扩展结点。结点的优先级常用一个与该结点有关的数值p 来表示。最大优先队列规定p 值较大的结点点的优先级较高。在算法实现时通常用一个最大堆来实现最大优先队列，用最大堆的Deletemax 运算抽取堆中的下一个结点作为当前扩展结点，体现最大效益优先的原则。类似地，最小优先队列规定p 值较小的结点的优先级较高。在算法实现时，常用一个最小堆来实现，用最小堆的Deletemin 运算抽取堆中下一个结点作为当前扩展结点，体现最小优先的原则。7/29/202210第10页，共80页。 采用优先队列式分支定界算法解决具

7、体问题时，应根据问题的特点选用最大优先或最小优先队列，确定各个结点的p 值。7/29/202211第11页，共80页。1.4 实例0-1背包问题n=3, c=30, w=16,15,15, p=45,25,257/29/202212第12页，共80页。实例分析0-1背包问题n=3, c=30, w=16,15,15, p=45,25,25队列式分支限界法：A B, C = B, CB, C D, E = EC, E F, G = F, GE, F, G J, K = K(45) 1,0,0F, G L, M =L(50) 0, 1, 1 M(25)G N, 0 =N(25), O(0)不搜索以

8、不可行结点为根的子树优先队列式分支限界法：A B, C = B(45), C(0)B, C D, E = E(45)E, C J, K = K(45) 1, 0, 0C F, G = F(25), G(0)F, G L, M = L(50), 0, 1, 1 M(25)G N, O = N(25), O(0)可用剪枝函数加速搜索7/29/202213第13页，共80页。1.5 实例TSP问题1234206305410ABCDEFGHIJKLMNOPQ1234344342322423问题描述：某售货员要到若干城市去推销商品，一直各城市之间的路程，他要选定一条从驻地出发，经过每个城市一遍，最后回到

9、住地的路线，使总的路程最短。7/29/202214第14页，共80页。实例分析TSP问题队列式分支限界法：B C, D, EC, D, E F, GD, E, F, G H, IE, F, G, H, I J, KF, G, H, I, J, K L(59) 1,2,3,4,1G, H, I, J, K M(66)H, I, J, K N(25) 1, 3, 2, 4,1I, 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

10、, I = H(11), I(26)H, J, K, I, C N = N(25) 1, 3, 2, 4,1J, K, I, C P = P(25)K, I, C Q = Q(59)I, C I, C 被限界掉1234206305410ABCDEFGHIJKLMNOPQ12343443423224237/29/202215第15页，共80页。1.6 应用分支限界法的关键如何确定合适的限界函数？如何组织活结点表？如何确定最优解中的各个分量？好的限界函数不仅计算简单，还要保证最优解在搜索空间中，更重要的是能在搜索的早期对超出目标函数界的结点进行丢弃，减少搜索空间，从而尽快找到问题的最优解。 通常采

11、用最大堆或最小堆来实现优先队列式分支限界法求解问题。 可以用如下方法求得最优解中的分量：1）对每个扩展结点保存该结点到根结点的路径；2）在搜索过程中构建搜索经过的树结构，在求得最优解时，从叶子结点不断回溯到根结点，以确定最优解中的各个分量。 7/29/202216第16页，共80页。提纲一、分支限界法的基本思想二、单源最短路径问题三、装载问题四、0-1背包问题五、最大团问题六、旅行售货员问题7/29/202217第17页，共80页。2.1单源最短路径问题定义在有向图G中，每一边都有一个非负边权。求图G的从源顶点s到目标顶点t之间的最短路径。7/29/202218第18页，共80页。用优先队列式

12、分支限界法解有向图G的单源最短路径问题产生的解空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。有向图G的单源最短路径问题产生的解空间树7/29/202219第19页，共80页。2.2单源最短路径问题算法思想用一最小堆来存储活结点表。其优先级是结点所对应的当前路长。算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活

13、结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。7/29/202220第20页，共80页。2.3 剪枝策略在算法扩展结点的过程中，一旦发现一个结点的下界（即结点所对应的当前路长）不小于当前找到的最短路长，则算法剪去以该结点为根的子树。在算法中，还可以利用结点间的控制关系进行剪枝。从源顶点s出发，2条不同路径到达图G的同一顶点。由于两条路径的路长不同，因此可以将路长长的路径所对应的树中的结点为根的子树剪去。例如，从源点s出发，经过边a,e,q（路长为5）和经过边c,h（路长为6）的2条路径到达图G的同一顶点。故可将后一条路径剪掉。7/29/202221第21页，共80页。剪

14、枝策略 下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树的剪枝情况。BA优于B，B可剪枝经过不同的路径到达相同的顶点A7/29/202222第22页，共80页。2.4 算法描述 while (true) for (int j = 1; j = n; j+) if (cE.ijinf)&(E.length+cE.ijdistj) / 顶点i到顶点j可达，且满足控制约束 distj=E.length+cE.ij; prevj=E.i; / 加入活结点优先队列 MinHeapNode N; N.i=j; N.length=distj; H.Insert(N); try H.De

15、leteMin(E); / 取下一扩展结点 catch (OutOfBounds) break; / 优先队列空 顶点i和j间有边，且此路径长小于原先从源点到j的路径长 7/29/202223第23页，共80页。实例计算从源顶点1到其它顶点间最短路径7/29/202224第24页，共80页。1230V2V0V1V4V33825420510计算从源顶点V0 到其它顶点间最短路径练习7/29/202225第25页，共80页。提纲一、分支限界法的基本思想二、单源最短路径问题三、装载问题四、0-1背包问题五、最大团问题六、旅行售货员问题7/29/202226第26页，共80页。3.1 问题定义有一批共

16、个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集装箱i的重量为wi，且wiC1+C2装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。 容易证明：如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。 (1)首先将第一艘轮船尽可能装满；(2)将剩余的集装箱装上第二艘轮船。7/29/202227第27页，共80页。 解装载问题的队列式分支限界法只求出所要求的最优值，稍后将进一步讨论求出最优解。函数MaxLoading具体实施对解空间的分支限界搜索。其中队列Q用于存放活结点表。在队列Q的元素值表示每个活结点所相应的当前载重量。 当其值为1

17、时，表示队列已到达解空间树同一层结点的尾部。3.2 队列式分支限界法7/29/202228第28页，共80页。 函数EnQueue用于将活结点加入到活结点队列中。该函数首先检查i是否等于n。如果in，则表示当前活结点为一个叶结点。由于叶结点不会被进一步扩展，因此不必加入到活结点队列中。此时只要检查该叶结点表示的可行解是否优于当前最优解，并适时更新当前最优解。当in时，当前活结点是一个内部结点，应加入到活结点队列中。7/29/202229第29页，共80页。void EnQueue(&Q,Type wt,Type & bestw, int i, int n) /该函数负责加入活结点 / 如果不是

18、叶结点，则将结点权值wt加入队列Qif (i = n) /可行 叶子结点 if (wtbestw) bestw = wt; else Q.Add(wt); / 不是叶子7/29/202230第30页，共80页。函数MaxLoading在开始时将i初始化为1，bestw初始化为0。此时活结点队列为空。将同层结点尾部标志1加入到活结点队列中，表示此时位于第1层结点的尾部。Ew存储当前扩展结点所相应的重量。7/29/202231第31页，共80页。队列式分支限界法在算法的while循环中，首先检测当前扩展结点的左儿子结点是否为可行结点。如果是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点队

19、列中(右儿子结点一定是可行结点)。2个儿子结点都产生后，当前扩展结点被舍弃。 活结点队列中的队首元素被取出作为当前扩展结点，由于队列中每一层结点之后都有一个尾部标记-1，故在取队首元素时，活结点队列一定不空。当取出的元素是-1时，再判断当前队列是否为空。如果队列非空，则将尾部标记-1加入活结点队列，算法开始处理下一层的活结点。7/29/202232第32页，共80页。队列式分支限界法while (true) / 检查左儿子结点 if (Ew + wi = c) / xi = 1 EnQueue(Q, Ew + wi, bestw, i, n); / 右儿子结点总是可行的 EnQueue(Q,

20、Ew, bestw, i, n); / xi = 0 Q.Delete(Ew); / 取下一扩展结点 if (Ew = -1) / 同层结点尾部 if (Q.IsEmpty() return bestw; Q.Add(-1); / 同层结点尾部标志 Q.Delete(Ew); / 取下一扩展结点 i+; / 进入下一层 7/29/202233第33页，共80页。3.3 算法的改进 节点的左子树表示将此集装箱装上船，右子树表示不将此集装箱装上船。设bestw是当前最优解；ew是当前扩展结点所相应的重量；r是剩余集装箱的重量。则当ew+rbestw时，可将其右子树剪去。 算法MaxLoading初

21、始时将bestw置为0，直到搜索到第一个叶结点时才更新bestw。因此在算法搜索到第一个叶结点之前，总有bestw0，r0，故Ew十rbestw总是成立。也就是说，此时右子树测试不起作用。 另外，为了确保右子树成功剪枝，应该在算法每一次进入左子树的时候更新bestw的值。7/29/202234第34页，共80页。算法的改进/ 检查左儿子结点 Type wt = Ew + wi; / 左儿子结点的重量 if (wt bestw) bestw = wt; / 加入活结点队列 if (i bestw & i n) Q.Add(Ew); / 可能含最优解 Q.Delete(Ew); / 取下一扩展结点

22、右儿子剪枝 7/29/202235第35页，共80页。算法的改进while (true) / 检查左儿子结点 Type wt = Ew + wi; / 左儿子结点的重量 if (wt bestw) bestw = wt; / 加入活结点队列 if (i bestw & i 0; j-) bestxj = bestE-LChild; bestE = bestE-parent; 找到最优值后，可以根据parent回溯到根结点，找到最优解。构造最优解7/29/202238第38页，共80页。3.5优先队列式分支限界法解装载问题的优先队列式分支限界法用最大优先队列存储活结点表。活结点x在优先队列中的优

23、先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和。优先队列中优先级最大的活结点成为下一个扩展结点。以结点x为根的子树中所有结点相应的路径的载重量不超过它的优先级。子集树中叶结点所相应的载重量与其优先级相同。在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。此时可终止算法。7/29/202239第39页，共80页。上述策略可以用两种不同的方式实现。第一种方式在结点优先队列的每一个活结点中保存从解空间树的根结点到该活结点的路径，在算法确定了达到最优值的叶结点时，就在该叶结点处同时得到相应的最优解。第二种策略在算法的搜索进程中

24、保存当前已构造出的部分解空间树，这样在算法确定了达到最优值的叶结点时，就可以在解空间树中从该叶结点开始向根结点回溯，构造出相应的最优解。在下面的算法中，我们采用第二种策略。7/29/202240第40页，共80页。第i十1层结点的剩余重量ri定义为ri 。变量E指向子集树中当前扩展结点, Ew是相应的重量。算法开始时，i1，Ew0，子集树的根结点是扩展结点。/定义剩余重量数组r int * r = (int*)malloc(sizeof(int)*(n+1) ; rn = 0; for(int j = n-1; j 0; j-) rj= rj+1 + wj+1;7/29/202241第41页，

25、共80页。int MaxLoading(int w , int c, int n)/优先队列式分支限界法，返回最优载重量，bestx返回最优解 /定义最大堆的容量为1000/ MaxHeap HeapNode H( 1000 );head = (HeapNode*)malloc(sizeof(HeapNode) ;if(head =NULL)printf(没有足够的空间分配n) ; return 1 ; head-level = 0 ; head-next = NULL ; head -ptr =NULL ; head-uweight = 0 ; /定义剩余重量数组r int * r = (i

26、nt*)malloc(sizeof(int)*(n+1) ; rn = 0; for(int j = n-1; j 0; j-) rj= rj+1 + wj+1; /初始化 int i = 1; / 当前扩展结点所处的层 bbnode * E =0; /当前扩展结点 int Ew = 0; /扩展结点所相应的载重量 7/29/202242第42页，共80页。优先队列式分支限界法While循环体产生当前扩展结点的左右儿子结点。如果当前扩展结点的左儿子结点是可行结点，即它所相应的重量末超过船载容量，则将它加入到子集树的第i十1层上，并插入最大堆。扩展结点的右儿子结点总是可行的，故直接插入子集树的最

27、大堆中。接着算法从最大堆中取出最大元素作为下一个扩展结点。如果此时不存在下一个扩展结点，则相应的问题无可行解。如果下一个扩展结点是一个叶结点，即子集树中第n十1层结点，则它相应的可行解为最优解。该最优解所相应的路径可由子集树中从该叶结点开始沿结点父指针逐步构造出来。具体算法可描述如下：7/29/202243第43页，共80页。while( i!=n+1 ) /非叶结点 /检查当前扩展结点的儿子结点 if(Ew+w i level;E = N-ptr;Ew = N-uweight-ri-1;/优先权uweight = Ew + r i - 1;7/29/202244第44页，共80页。for(j

28、 = n ; j 0;j-) /构造当前最优解 bestxj = E - LChild; E = E-parent;return Ew;构造当前最优解7/29/202245第45页，共80页。提纲一、分支限界法的基本思想二、单源最短路径问题三、装载问题四、0-1背包问题五、最大团问题六、旅行售货员问题7/29/202246第46页，共80页。4.1 问题定义给定n种物品和一个背包，物品i的重量是wi，价值pi,背包容量为C，问如何选择装入背包的物品，使装入背包中的物品的总价值最大？对于每种物品只能选择完全装入或不装入，一个物品至多装入一次。7/29/202247第47页，共80页。4.2 算法

29、思想首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。在优先队列分支限界法中，节点的优先级由已装入背包的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时即为问题的最优值。7/29/202248第48页，共80页。4.3 上界函数templateTypep Knap:Bound(int i)/ 计算结点所相应价值的上界 Typew c

30、left = c - cw; / 剩余容量 Typep b = cp; /价值上界 / 以物品单位重量价值递减序装满剩余背包容量 while (i = n & wi = cleft) cleft -= wi; b += pi; i+; / 装填剩余容量至装满背包 if (i = n) b += pi/wi * cleft; return b; 7/29/202249第49页，共80页。4.4 算法描述while (i != n+1) / 非叶结点 / 检查当前扩展结点的左儿子结点 Typew wt = cw + wi; if (wt bestp) bestp = cp+pi; AddLiveN

31、ode(up, cp+pi, cw+wi, true, i+1); up = Bound(i+1); / 检查当前扩展结点的右儿子结点 if (up = bestp) / 右子树可能含最优解 AddLiveNode(up, cp, cw, false, i+1); / 取下一个扩展节点（略）分支限界搜索过程7/29/202250第50页，共80页。提纲一、分支限界法的基本思想二、单源最短路径问题三、装载问题四、0-1背包问题五、最大团问题六、旅行售货员问题7/29/202251第51页，共80页。5.1 问题定义给定无向图G=(V，E)。如果UV，且对任意u，vU有(u，v)E，则称U是G的完

32、全子图。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的最大团。 7/29/202252第52页，共80页。5.2 算法思想 子集树的根结点是初始扩展结点，对于这个特殊的扩展结点，其cliqueSize的值为0。 算法在扩展内部结点时，首先考察其左儿子结点。在左儿子结点处，将顶点i加入到当前团中，并检查该顶点与当前团中其它顶点之间是否有边相连。当顶点i与当前团中所有顶点之间都有边相连

33、，则相应的左儿子结点是可行结点，将它加入到子集树中并插入活结点优先队列，否则就不是可行结点。 接着继续考察当前扩展结点的右儿子结点。当右儿子结点满足上界函数（upperSizebestn）时，右子树中可能含有最优解，此时将右儿子结点加入到子集树中并插入到活结点优先队列中。7/29/202253第53页，共80页。5.3 上界函数用变量cliqueSize表示与该结点相应的团的顶点数；level表示结点在子集空间树中所处的层次；用cliqueSize +n-level+1作为顶点数上界upperSize的值。在此优先队列式分支限界法中，upperSize实际上也是优先队列中元素的优先级。算法总是

34、从活结点优先队列中抽取具有最大upperSize值的元素作为下一个扩展元素。7/29/202254第54页，共80页。5.4 算法描述具体算法略（见课本）。 算法的while循环的终止条件是遇到子集树中的一个叶结点(即n+1层结点)成为当前扩展结点。 对于子集树中的叶结点，有upperSizecliqueSize。此时活结点优先队列中剩余结点的upperSize值均不超过当前扩展结点的upperSize值，从而进一步搜索不可能得到更大的团，此时算法已找到一个最优解。 7/29/202255第55页，共80页。提纲一、分支限界法的基本思想二、单源最短路径问题三、装载问题四、0-1背包问题五、最大

35、团问题六、旅行售货员问题7/29/202256第56页，共80页。6.1 问题定义某售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费)。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费)最小。路线是一个带权图。图中各边的费用（权）为正数。图的一条周游路线是包括V中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。旅行售货员问题的解空间可以组织成一棵树，从树的根结点到任一叶结点的路径定义了图的一条周游路线。旅行售货员问题要在图G中找出费用最小的周游路线。7/29/202257第57页，共80页。6.2 算法思想算法开始时创建一个最小

36、堆，用于表示活结点优先队列。堆中每个结点的子树费用的下界lcost值是优先队列的优先级。接着算法计算出图中每个顶点的最小费用出边并用minout记录。如果所给的有向图中某个顶点没有出边，则该图不可能有回路，算法即告结束。如果每个顶点都有出边，则根据计算出的minout作算法初始化。算法的while循环体完成对排列树内部结点的扩展。对于当前扩展结点，算法分2种情况进行处理：7/29/202258第58页，共80页。6.2 算法思想1、首先考虑s=n-2的情形，此时当前扩展结点是排列树中某个叶结点的父结点。如果该叶结点相应一条可行回路且费用小于当前最小费用，则将该叶结点插入到优先队列中，否则舍去该

37、叶结点。2、当sn-2时，算法依次产生当前扩展结点的所有儿子结点。由于当前扩展结点所相应的路径是x0:s，其可行儿子结点是从剩余顶点xs+1:n-1中选取的顶点xi，且(xs，xi)是所给有向图G中的一条边。对于当前扩展结点的每一个可行儿子结点，计算出其前缀(x0:s，xi)的费用cc和相应的下界lcost。当lcostbestc时，将这个可行儿子结点插入到活结点优先队列中。7/29/202259第59页，共80页。6.2 算法思想算法中while循环的终止条件是排列树的一个叶结点成为当前扩展结点。当s=n-1时，已找到的回路前缀是x0:n-1，它已包含图G的所有n个顶点。因此，当s=n-1时

38、，相应的扩展结点表示一个叶结点。此时该叶结点所相应的回路的费用等于cc和lcost的值。剩余的活结点的lcost值不小于已找到的回路的费用。它们都不可能导致费用更小的回路。因此已找到的叶结点所相应的回路是一个最小费用旅行售货员回路，算法可以结束。算法结束时返回找到的最小费用，相应的最优解由数组v给出。7/29/202260第60页，共80页。6.3 算法描述7/29/202261第61页，共80页。7/29/202262第62页，共80页。7/29/202263第63页，共80页。7/29/202264第64页，共80页。7/29/202265第65页，共80页。 算法中while循环的终止条

39、件是排列树的一个叶结点成为当前扩展结点。当sn1时，已找到的回路前缀是x0：n1，它已包含图G的所有n个顶点。因此，当sn1时，相应的扩展结点表示一个叶结点。此时该叶结点所相应的回路的费用等于cc和lcost的值。剩余的活结点的1cost值不小于己找到的回路的费用。它们都不可能导致费用更小的回路。因此已找到的叶结点所相应的回路是一个最小费用旅行售货员回路，算法可以结束.7/29/202266第66页，共80页。 算法的while循环体完成对排列树内部结点的扩展。对于当前扩展结点，算法分两种情况进行处理。首先；考虑sn2的情形。此时当前扩展结点是排列树中某个叶结点的父结点。如果该叶结点相应一条可

40、行回路且费用小于当前最小费用，则将该叶结点插入到优先队列中，否则舍去该叶结点。当sn-2时，算法依次产生当前扩展结点的所有儿子结点。由于当前扩展结点所相应的路径是x0:s，其可行儿子结。点是从剩余顶点xs+1:n-1中选取的顶点xIj，且(x s，xi)是所给有向图G中的一条边。对于当前扩展结点的每一个可行儿子结点，计算出其前缀(x0:s，xi)的费用cc和相应的下界Lcost。当lcostbestc时，将这个可行儿子结点插入到活结点优先队列中。7/29/202267第67页，共80页。试写出0/1 背包问题的优先队列式分枝限界算法程序，并找一个物品件数为16 的例子检验程序的运行情况。上机7

41、/29/202268第68页，共80页。回溯法与分支限界法的用法取向探讨1.基本思想分析回溯法的基本思想: 首先确定解空间的组织结构, 接着就从开始结点(根结点) 出发, 以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点, 同时也成为当前的扩展结点。在当前的扩展结点处, 搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点, 并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动, 则当前扩展结点就成为死结点。换句话说, 这个结点不再是一个活结点。此时, 应往回移动(回溯) 至最近的一个活结点处, 并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空

42、间中搜索, 直至找到所要求的解或解空间中已没有活结点时为止。7/29/202269第69页，共80页。分支限界法的基本思想: 确定解空间的组织结构, 以广度优先或以最小耗费(最大效益) 优先的方式搜索问题的解空间树。在搜索问题的解空间树时, 分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中, 每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点, 就一次性产生其所有儿子结点。在这些儿子结点中, 那些导致不可行解或导致非最优解的儿子结点被舍弃, 其余儿子结点被子加入活结点表中。此后, 从活结点表中取下一结点成为当前扩展结点, 并重复上述结点扩展过程。这个过程一直持续到

43、找到所求的解或活结点表为空时为止。7/29/202270第70页，共80页。用法比较分支限界法类似于回溯法, 也是一种在问题的解空间树T上搜索问题解的算法。但在一般情况下, 分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解, 而分支限界法的求解目标则是找出满足约束条件的一个解, 或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解, 即在某种意义下的最优解。7/29/202271第71页，共80页。由于求解目标不同, 导致分支限界法与回溯法在解空间树T上的搜索方式也不相同。回溯法以深度优先的方式搜索解空间树T, 而分支限界法则以广度优先或以最小耗费优先

44、的方式搜索解空间树T。分支限界法的搜索策略是: 在扩展结点处, 先生成其所有的儿子结点(分支) , 然后再从当前的活结点表中选择下一个扩展对点。为了有效地选择下一扩展结点, 以加速搜索的进程,在每一活结点处, 计算一个函数值(限界) , 并根据这些已计算出的函数值, 从当前活结点表中选择一个最有利的结点作为扩展结点, 使搜索朝着解空间树上有最优解的分支推进, 以便尽快地找出一个最优解。7/29/202272第72页，共80页。分支限界法常以广度优先或以最小耗费(最大效益) 优先的方式搜索问题的解空间树。问题的解空间树是表示问题解空间的一棵有序树, 常见的有子集树和排列树。在搜索问题的解空间树时, 分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中, 每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点, 就一次性产生其所有儿子结点。在这些儿子结点中, 那些