算法设计与分析-6

1、分支限界法原理与算法框架 分支限界法 vs 回溯法应用范例（1）旅行商问题（2）单源最短路径问题（3）0-1背包问题应用范例（略）（4）多段图最短路径（5）装载问题（6）批处理作业调度问题6.1分支限界法原理 与回溯法类似，一种基于解空间搜索的问题求解策略回溯法原理：回溯法原理：1）利用某种数据结构解向量解向量，形式化地表示问题解 e.g. n个城市旅行商问题(TSP) 解向量表示为长度为n的向量x1:n=2）问题的各种解组成了问题解空间最优解、次优解/可行 解、错误/不可行解、部分解13243061020543）问题解应满足各种约束约束，包括: 显约束：对解空间中分量xi的取值限定 e.g.

2、 TSP xi 1,2,3,n 隐约束：为满足问题的解而对不同分量之间施加的约束 e.g. TSP，各个城市只能遍历一次4）解空间中各个解根据相互间关系 和解的构造顺序，组成解空间树1324306102054e.g. 4个城市的旅行商问题BCFEL2344A1GM34DHN24IO243HN23IO23第1步第2步第3步第4步1） 非叶结点对应部分解2）叶节点对应最优解、可行解5）对解空间中的解，引入定量指标，作为优化依据 e.g. 旅行商问题：旅游路径总长最短6）问题求解过程带有回溯的深度优先树搜索 以深度优先的方式以深度优先的方式，从树根结点开始，依次扩展树结点，直到达到叶结点搜索过程中动

3、态产生解空间 深度优先目的：尽可能快地获得可行解 BCFEL2344A1GM34DHN24IO243HN23IO23第1步第2步第3步第4步 扩展过程中，碰到可行非叶结点（部分解），可进一步扩展 e.g. 结点C对应部分解 可进一步扩展为: F= G= BCFEL2344A1GM34DHN24IO243HN23IO23 碰到不可行非叶/叶结点（不可行（部分）解），需要返回到上一层结点回溯 e.g. 对C结点，下一步的扩展有4种可能选择：3、4、1、2，每种选择都可以继续扩展子树；但只有其中2种选择是合理的，对后2种选择不再继续扩展，而是返回C结点4BCFEL234A1GM3412HN23IO2

4、37）为了提高搜索效率，用剪枝函数（面向具体问题）避免无效搜索，即避免不可行解对应的子树或结点e.g. 剪枝条件/约束1： 如果当前正在考虑的顶点j与当前路径中的末端结点i没有边相连，即wi, j= , 则不必搜索j所在分支 E.g. 当前已有的部分路径为, ,路径末端结点为2, 下一步可考虑将顶点3、4加入到部分路径中。 但是，顶点2与4间无边，w(2,4)= , 因此在解空间树中，可以不必考虑顶点4所在分CFEL2344A1GM34DHN24IO243HN23IO23第1层结点： x1第2层结点: x2第3层结点: x3第4层结点: x4此分支可剪枝剪枝条件2：假

5、设：已经知道直到第i-1层的部分解 ,从第i-1层结点选择顶点xi，并向该分支往下搜索的界限函数为： B(i) = cw(i-1) + w(xi-1, xi) 由此得到剪枝/约束条件2： 如果如果B(i) bestw, 则停止搜索则停止搜索xi分支及其下面的层分支及其下面的层 ，其中，bestw代表到目前为止,在前面的搜索中，从其它已经搜索过的路径中，找到的最佳回路的权和（总长度）分支限界法（branch and bound）原理：1）按宽度优先策略宽度优先策略遍历解空间树。2）在遍历过程中，对处理的每个结点vi，根据界限函数，估计沿该结点向下搜索所可能达到的完全解的目标函数的可能取值范围界限

6、bound(vi)=downi, upi3）从中选择使目标函数取的极值（最大、最小）的结点优先进行宽度优先搜索，从而不断调整搜索方向，尽快找到问题解关键：各结点的界限函数关键：各结点的界限函数bound(vi)=downi, upi, 依据具体问题而定依据具体问题而定e.g. 4个城市的TSP搜索树中的界限函数BCFEL2344A1G4D3第1步第2步第3步第4步bound(G)bound(D)bound(E)子树子树子树一、与回溯法类似，解向量、解空间、解空间树二、解空间树中的结点分为4种类型 活结点，死结点，扩展结点，待处理结点活结点死结点扩展结点未处理结点 活结点活结点 当前满足约束条件

7、、未来有可能产生最优解的结点； 对应部分解, e.g. 结点G、D、E 所有活结点组成活结点表ANT (Alive Node Table)BCFEL2344A1G4D3第1步第2步第3步第4步 扩展结点扩展结点 从活结点表ANT中取出来，当前准备进行扩展的结点，即当前进行处理的结点 1）评估每个活结点价值，按照价值最大化/最小化原则，从 ANT中选取扩展结点 e_node 2）e_node扩展方式： 宽度优先，生成e_node的全部子节点； 评估这些子节点，满足界限约束、有可能产生更优解的 结点被作为活结点，加入ANT；不满足约束、或无法产生 最优解的子节点被舍弃剪枝 3） e_node结点被

8、扩展后，该结点转换为死结点，以后将不会 被再搜索 活结点活结点扩展结点扩展结点死结点死结点e.g. 如下图 i) 从上图中的3个活结点G、D、E中，选择价值最大的结点D，作为扩展结点BCFEL2344A14G3第1步第2步第3步第4步Dii) 生成D的全部2个子结点H、I，经评估后，作为活结点加入 ADT表中iii) D变为死结点BCFEL2344A14G3第1步第2步第3步第4步HID24 死结点：死结点： 1）已经处理过（搜索过）、不再处理的结点; e.g. A, B, C, F, L 2）不满足约束条件、无法产生最优解的结点. e.g. 结点G, 对应部分解, 而 w(4,3)=BCFE

9、L2344A14G3第1步第2步第3步第4步HID2413243062054 未处理结点 解空间树中位于活结点之下，还没有被搜索/处理到、不属于上述三类结点的其它结点 在后续的搜索过程中，通过结点扩展会逐步生成BCFEL2344A14G3第1步第2步第3步第4步HID24三、解空间树的扩展 选定扩展结点e_node，生成其全部子结点采取宽度优先宽度优先进行扩展 e.g. 结点D对应于，考察它的2个子结点和BCFEL2344A14G3DHI24四、对扩展结点e_node，生成其全部儿子结点后，判断评估每个儿子结点： i) 是否满足约束条件。如不满足，则作为死结点 ii）估算估算沿着儿子结点向下搜

10、索时，目标函数可能取得的沿着儿子结点向下搜索时，目标函数可能取得的“界界”，即沿着儿子结点，即沿着儿子结点向下构造出的最终解可能取得的目标函数的范围；向下构造出的最终解可能取得的目标函数的范围； -极大化目标，估计子节点目标函数上界 -极小化目标，估计子节点目标函数下界 iii）将全部活结点组织在活结点表ANT中 利用活结点的“界”值，对活结点进行价值评估是否有可能得到最优解？ 关键：目标函数界限函数！五、扩展结点e_node选取 扩展树时，需要从活结点表ANT中选取合适的活结点，将其转化为扩展结点e_node 1) 对最小化问题（如TSP），选取具有最小“界”的活结点 e.g. 前图中，部分

11、解D的最小界：经过D的最短路径长度至少（下界）是多少 2) 对最大化问题（如背包问题），选取具有最大“界”的活结点，物品装入方案的最大价值 e.g. 3) 当到达1个叶结点时，得到1个可行解，该可行解对应的最优值bound(x1,x2,xn)可作为当前最优解的1个“界”六、结点界限函数及剪枝 进行结点/树扩展时，利用界限函数估计每个结点可能达到的最优解，进行剪枝 1) 估计e_node的每个儿子结点ci的“界”bound(ci) -极大化目标，估计子结点目标函数上界 -极小化目标，估计子结点目标函数下界 2) 比较bound(ci)与活结点表ANT中现有活结点*的最优界限值bound(*) 对

12、最小化问题，e.g. 最短路径，如果bound(ci) bound(*)，沿ci搜索得到可行解不可能小于目前已经得到的最优解，则结点ci不应加入活结点表剪枝，不考虑该结点e.g. 已知 的路径总和=20；结点G对应如果路径1-2-4的总长=21，则结点G被舍弃 对最大化问题， e.g. 背包问题，如果bound(ci) = down），将x加入ANT表 /* 对最大化问题，要求沿x分支搜索到的完全解的目标值（上界）估计必须大于现有已知的目标函数的下界down循环，直到某个叶结点的目标函数值在表ANT中最大 /* 找到1个具有最大值的完全解 4.1 从表ANT中选择bound(vi)值最大的结点

13、vi ，扩展其子结点 /* 从活结点表中，选择1个具有最大可能目标值的扩展结点vi 4.2 对结点vi的每个子结点c，执行下列操作 4.2.1 估算c的目标函数值bound(c)-上界 4.2.2 如果（bound(c)= down），将c加入ANT表 /*子结点c有可能产生更优的解，将其加入活结点 表，以后考虑对其进行扩展 4.2.3 如果（c是叶结点 and bound(c)在表ANT中最大）， 则将结点c对应的完全解输出，算法结束 /* 结点c对应了1个新找到的、具有最大目标 函数值的完全解最优解 4.2.4 如果（c是叶结点 and bound(c)在表ANT中不是最 大），则： /*

14、结点c对应了1个新找到的完全解，但该完全解的目标 函数值与已经找到的、或未来可能找到完全解相比，并非更优 i) 令down = value(c) /*利用新找到的完全解的实际目标函数，更新问题的下界 ii) 对表对表ANT中所有满足中所有满足bound(vj) bound(c)的结点的结点vj， 从表从表ANT中删除该结点！中删除该结点！ /* 利用新找到的完全解的目标函数bound(c) ，进行剪枝，从ANT 表中去掉那些目标函数值不可能大于结点c的bound(c)的结点vj， 即去掉那些目标函数值小于由于当前新找到的完全解c的目标值 bound(c)的结点分支限界法是一种高效、通用的问题求

15、解方法。此方法发明者曾获计算机界最高奖项图灵奖。分支限界法三个关键技术1. 如何确定合适的限界函数 面向具体问题而定2. 如何合理组织活结点表决定了结点扩展顺序 1）FIFO队列：按照先进先出（FIFO）原则，选取下一个节点为扩展节点 2）优先队列：按照优先队列中规定的优先级选取优先级最高的节点，成为当前扩展节点。 3）堆3. 如何确定最优解中的各个分量 对解空间树中的结点处理是根据结点的bound值进行的，有可能是跳跃式的，回溯也不是单纯沿着双亲结点一层层向上回溯。因此，当在某个叶结点上搜索到全局最优值时，有可能无法得到组成该最优解的各个分量。 为此，可采用下述处理方法： 1）对每个扩展结点

16、，保存从根结点到该结点的路径 2）在搜索过程中，构建搜索经过的树结构。当求得最优解后，从叶结点回溯到根结点，得到最优解各个分量 问题：用于存储搜索树的存储空间可能会很大，增大了算法的空间复杂性BCFDL2344A14G3EHI24根据活结点表中各节点具体bound值，先处理D，后处理E，基本符合宽度优先序序BCFEL2344A14G3DHI24根据活结点表中各节点具体bound值，先处理E，后处理D，不符合宽度优先序序分支限界法 vs 回溯法求解目标： 回溯法的求解目标是找出解空间树中满足约束条件的所有（？或多个）解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中

17、找出在某种意义下的最优解。 2. 搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。 3. 解空间树的扩展 对扩展结点e_node，生成其全部子结点采取宽度优先或以最小耗费（最大效益）优先进行扩展，需要维护活结点表，因此占用的空间比回溯法大，但计算速度一般比回溯法快以空间换时间！ 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可

18、行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。6.2最短路径问题问题描述： 在下图所给的有向图G中，每一边都有一个非负边权。 要求：求出从源点s到目标点t之间的最短路径。 123456789用优先队列式分支限界法，解空间树：1） 树中边上的字母代表每一步经过的结点间路径2）树节点上的数字表示从源点s到该结点所对应的当前路长3）以经历过的边表示路径e.g. 以图中顶点表示的路径s-1-2-5, 边表示的路径s a:u:f123456789算法思想1. 解空间树中的结点v 对应1条从源点s到图中某个顶点的路径；叶节点对应1条s到目标点t的路径； 每个结点v需要记录本路径从s开始

19、、经过的全部边或顶点 e.g. 树结点，当前路长14，对应的路径s a:u:f 各树结点v的限界函数 1）上界up：可利用贪心法，求出1个上界 方法：每步选择离当前结点最近的下一结点 书上没有给出每条边的长度？！ 2） dist(v)下界 树结点所对应路径的长度：从源点s至路径中最后一个顶点的总长 e.g. 对以顶点表示的路径s-1-2-5, 或以 边表示的路径s a:u:f，对应的树中结点？（红色），dist(?)=143. 活结点表的组织 组织为极小堆，其优先级/目标函数是结点所对应的当前路径长度dist说明：教科书上的下界函数只考虑了当前部分路径的现有长度，没有考虑未来结点可能带来的路径

20、长度，下界函数不准确e.g. 对部分路径s1 2 5, 书上给出的下界值/优先级/目标函数只是取为当前路径长度14； 但显然对该部分解，不管从结点5向后如何走，下界值肯定比14大1234567894. 搜索过程1）从源顶点s、空优先队列开始，首先选择s作为扩展结点2）结点s被扩展后，它的儿子结点被依次插入活结点表堆中3）从堆中取出优先级最高(即：dist(v)/目标函数/下界最小）的树结点v，作为当前扩展结点 v对应的路径为s-i1-i2-ik 与堆中其它结点相比，该路径的长度dist(v)最小 e.g. 见下页，堆中有3个活结点，对应了三条路径s-1-2-5、s-1-5-6-9、s-2，路径

21、长度dist分别为14、6、3 应选择dist最小的路径s-2，即原图中的城市顶点2应作为扩展结点1234567894) 生成扩展结点的子结点 在G (V,E)中，依次检查与当前扩展结点相邻的所有顶点。 e.g. 如果城市顶点2被选为扩展结点，则需要考察经过边f、g可到达的城市顶点5、65) 考察各子结点是否可作为活结点是否有必要进一步扩展? 如果 i) 从当前选择的扩展城市顶点i到它的邻接城市顶点j有边可达，并且 ii) 从源s出发，途经城市顶点i再到顶点j的所相应的路径的长度小于当前已经得到的最优路径长度(或问题上界up), 即： dist(i) + distance(i, j) mind

22、ist=8, 被剪枝舍弃 右子结点表示路径s-3-6-9，dist=7 =8, 结点j就成为死结点； 只有dist(j)8的结点才作为活结点保留下来。2）对树中的3条路径s-b:g:l、s-b:f、s-c:h:l，长度分别为10、12、11，均大于当前mindist=8, 因此3个结点下的子树被剪枝e.g. 假设当前得到的最优路径为s-1-5-6-9, mindist=6123456789策略2：利用结点间的控制关系进行剪枝。 从源顶点s出发，2条不同路径到达图G的同一顶点。由于两条路径的路长不同，因此可以将路长长的路径所对应的树中的结点为根的子树剪去e.g. 下图中， 2条路径s-b:g:l

23、、s-c:h:l，长度分别为10、11，均到达城市结点8，因此可以舍弃长度=11的路径s-c:h:l所对应的子树 e.g. 假设当前得到的最优路径为s-1-5-6-9, mindist=6123456789算法代码框架 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)

24、; try H.DeleteMin(E); / 取下一扩展结点 catch (OutOfBounds) break; / 优先队列空 顶点顶点I I和和j j间有边，且此路径长间有边，且此路径长小于原先从原点到小于原先从原点到j j的路径长的路径长 旅行商TSP问题本问题关键： 如何估计TSP最优解的上下界（a）5个顶点的无向图（b）代价矩阵C表示各城市间的距离315836791642 57438923c ij代价矩阵特点：每条满足要求的回路在代价矩阵中的每一行每一列有且只有1个元素与之对应（n后问题）。e.g. 回路13 5 4 2 1，对应于C中的 c13, c35, c54, c42,

25、c21132431745652389TSP问题的上下界1.利用贪心法计算上界 以起始城市1作为出发城市，每次从当前出发城市发出的多条边中，选择没有遍历过的最短边连接的城市，作为下一步达到城市。 即：选择离当前出发城市最近的城市作为下一步出发城市 e.g. 从城市1出发， 途径13 5 4 2 1路径长度=1+2+3+7+3=16作为上界，即最短路径长度161324317456523892. ! TSP 下界lb下界1：矩阵中每一行的最小元素相加，其路径长度为 1 + 3 + 1 +3 + 2 = 10, 说明：最小元素代表每一步可能走的最短距离下界2（信息量更大）： 1） 在一条路径上，每个城

26、市有2条邻接边：进入该城市、离开该城市； 2） 将矩阵中每一行最小的2个元素相加除以2，并向上取整，就得到一个合理下界 解释：对每一步经过的城市j，从最近的上一个城市i来，再到下一个最近城市k去，即ijke.g. 对上图所示TSP，其最短路径下界 lb=(1+3) + (3+6) + (1+2) + (3+4) + (2+3)/2 =14 因此，以最短路径长度dist作为TSP问题目标函数，则dist的界为 14, 16. 在问题求解过程中，如果1个部分解的目标函数dist下界（e.g.18）超出此界限（上界16），则该部分解对应了死结点，可剪枝。315836791642 57438923c

27、ij部分解目标函数下界计算 对于1条正在生成的路径/部分解，已经确定的顶点（已经经过/遍历的城市）集合为 U=(r1, r2, , rk) , 该部分解的目标函数的下界为：111(2 C+Cijkiiiir UrUlbc rrrrj矩阵 中第 行不在路径上的最小元素矩阵 中第 行最小的2个元素）/2/*已经经过的路径的总长的2倍/*从当前已经走过的城市出发，走向最近的1个未遍历城市的距离和/* 进入/离开未遍历城市时，各未遍历城市带来的最小路径成本132431745652389E.g. 假设 正在生成的路径/部分解为14, U=1,4，未遍历城市=2,3,5，该部分解下界为lb = 2*已经历

28、过的路径总长 + 从城市1到最近未遍历城市的距离 + 从城市4到最近未遍历城市的距离 + 进入/离开城市2带来的最小成本 + 进入/离开城市3带来的最小成本 + 进入/离开城市5带来的最小成本 /2 = 2*5 + 1 + 3 + (3+6) + (1+2) + (2+3) / 2= 16 (向上取整)315836791642 57438923c ij用分支限界求解，搜索空间树如下图所示：1. TSP问题完全解界限14, 162. 最优解为13 5 4 2 1，最短路径长度=1+2+3+7+3=163. 树结点编号对应了结点扩展顺序，即搜索顺序4. 表示被丢弃的死结点，其余为活结点搜索过程：S

29、tep1. 在根结点1处，U=空, 计算本问题的可能下界 lb = 2*已经历过的路径总长 + 进入/离开城市1带来的最小成本 + 进入/离开城市2带来的最小成本 + 进入/离开城市3带来的最小成本 + 进入/离开城市4带来的最小成本 + 进入/离开城市5带来的最小成本 /2 = 2*0 + 0 + (1+3) + (3+6) + (1+2) + (3+4) + (2+3) /2 = 14315836791642 57438923c ijstartlb=1412lb=1413lb=1414lb=1615lb=1923lb=1624lb=1632lb=1625lb=1934lb=1535lb=1

30、442lb=1845lb=1552lb=1954lb=1452lb=2042lb=1612345678 9101112131415 X1617TSP问题完全解界限14, 161. 树结点编号对应了结点搜索/生成顺序2. 表示被丢弃的死结点315836791642 57438923c ijStep2. 以结点1为扩展结点，依次生成树结点2,3,4,5；Step3. 计算这4个结点的lb： lb(2)= lb(3)=14, lb(4)=16，均小于 等于问题上界16，因此结点2、3、4 加入活结点表； 对结点5，已遍历城市U=1,5 lb(5) = 2*已经历过的路径1 5总长 + 从城市1到最近

31、未遍历城市3的距离 + 从城市5到最近未遍历城市3的距离 + 进入/离开城市2带来的最小成本 + 进入/离开城市3带来的最小成本 + 进入/离开城市4带来的最小成本 /2 = 2*8 + 1 + 2 + (3+6) + (1+2) + (3+4) /2 = 19 lb(5)问题上界16，树结点5被作为死结点舍弃Step4.从当前活结点表ANT=2,3,4中，以lb为依据，并兼顾结点生成顺序，选取lb最小的结点2作为扩展结点，生成结点6、7、8； 计算这3个结点的lb， lb(6)= lb(7)=16, lb(8)=19; 舍弃结点8，将结点6、7加入活结点表, 变为ANT=3,4, 6,7St

32、ep5. 从ANT中，选择 lb最小的结点3扩展，生成结点9、10、11startlb=1412lb=1413lb=1414lb=1615lb=1923lb=1624lb=1632lb=1625lb=1934lb=1535lb=142345678 91011Step6. 按照上述方法，依次扩展搜索树，得到最优解 13 5 4 2 1，最短路径长度=1+2+3+7+3=16 TSP问题分支限界法算法描述： 数组x1:n存储搜索路径上的树顶点 1. 采用贪心法，计算上界up； 根据目标函数公式，计算下界down2. 将活结点表ANT初始化为空3. for ( i=1; i =1) 5.1 i=k+

33、1; 5.2 xi=1; 5.3 while (xi = n) 5.3.1 如果路径上城市顶点不重复，则 5.3.1.1 计算xi的下界lb 5.3.1.2 if (lb 1层：考虑第i个物品，左分支放入，右分支不放入装载量w, 已获得价值v上界ub; 部分解S=I1, I2, .,Ik第k层结点1267 限界函数（最大化问题） 下界down：贪心法， 第1个可装入的、具有最大价值/重量比的物品所具 有的价值，(1,0,0,0) , down=40 上界up：背包中全部装入第1个物品，且装满， up=10*10=100 问题限界40,100对第k层结点，代表了对物品1i作出的选择，假设已经装入

34、的物品重量为w，获得的价值为v该结点的限界函数该结点的限界函数ub： 已装入背包中物品取得的价值已装入背包中物品取得的价值v + 背包剩余容量（背包剩余容量（C-w）*剩余物品中的最大单位重量剩余物品中的最大单位重量价值价值68问题完全解界限40, 100w=0, v=0ub=100, S=?,?,?,?w=4, v=40ub=40+(10-4)*6, S=1,?,?,?w=0, v=0ub=0+10*6, S=0,?,?,?11123w=4+7=11, , S=1,1,?,?w=4, v=40ub=40+0+(10-4)*5, S=1,0,?,?45无效死结点(wC)w=4+5=9, v=6

35、5 ub=65+(10-4-5)*4, S=1,0,1,?w=4, v=40ub=40+(10-4)*4, S=1,0,0,?67无效死结点(wC)w=9, v=65 ub=65, S=1,0,1,09w=12, , S=1,0,1,18剪枝条件: ub 上界18 3. 如果是，则该结点被剪枝舍弃 e.g. 结点2， 对应路径01 结点10， 对应路径03 5 7 问题完全解界限14, 181. 树结点编号对应了结点搜索/生成顺序2. 表示被丢弃的死结点startlb=1401lb=2002lb=1703lb=1524lb=2225lb=1826lb=1857lb=2212 347 89103

36、6lb=18635lb=16558lb=16112+7+5+3=173+4+5+3=152+8+5+7=222+7+6+3=182+8+5+3=184+8+5+3=203+4+6+3=163+7+5+3=183+4+8+7=223+4+6+3=161. 采用贪心法，计算上界up； 根据目标函数公式，计算下界down2. 将活结点表ANT初始化为空3. for ( i=1; i =1) 5.1 对顶点u的所有邻接点v 5.1.1 计算v的目标函数lb(v) 5.1.2 if (lb = up), v为活结点，将路径上的 顶点i, , lb(v)值 存入活结点表ANT 5.2 如果i=k-1, 即

37、搜索到达叶节点，并且叶子结点的目标函 数值lb在表ANT中最小 ，则输出该叶结点对应的最优解 5.3 否则，若i=k-1，并且叶子结点的目标函数值lb在 表ANT中不是最小，则 5.3.1 令up=表ANT中叶子结点所具有的最小的lb值 5.3.2 删除ANT表中目标函数值lb超出up的结点 5.4 u =表ANT中lb最小的结点的v值（顶点编号） /* 选取lb最小的活结点v，作为扩展结点 5.5 i =表ANT中lb最小的结点的i值； /*扩展结点对应的段号 5.6 i+批处理作业调度 给定n个作业的集合J=J1,J2,Jn,每个作业有3项任务需要在3台机器上完成，作业Ji需要机器j的处理

38、时间为tij（1i n, 1j3 ）。每个作业需要依次在机器1、2、3上处理。 要求：确定作业最优处理顺序，使得从第1个投入执行的作业在机器1上开始，到最后1个作业在机器3上结束为止，所需时间最短。 最优调度：机器1上无空余时间，机器2、3上的空闲/等待时间最短 可以证明：对最优调度，作业在机器1上的执行顺序与机器2、3上的执行顺序是一致的。分支限界法的复杂性 与回溯法一样，分支限界法属于蛮力穷举法。 最坏情况下，需要遍历指数阶个结点的解空间树，复杂性为指数阶。 与回溯法不同：优先扩展上层结点，采用界限函数，利于大范围剪枝，缩小搜索空间；同时，利用限界函数，不断调整搜索方向，选择最优可能获得最

39、优解的子树优先搜索 性能密切依赖于限界函数 对具体问题，很难预测分支限界法的搜索行为 跳跃式搜索，构造完整解比较麻烦 空间复杂性较高，最坏情况下，空间复杂性为指数阶机器1机器2机器3J1579J21052J3995J47810作业在机器上的处理时间矩阵T83M1M2M3J2:10J3:9J1:5J4:7空闲:10J2:5J3:9J1:7J4:8空闲:15J2:2J3:5J1:9J4:10 需要估计： 问题上界，部分解下界 剪枝条件： 部分解下界 问题上界 理想情况下，机器机器1、2无空闲，最后处理的恰好是机无空闲，最后处理的恰好是机器器3上处理时间最短的作业上处理时间最短的作业 例如，以作业J

40、i开始的处理顺序，估算处理所需的最短时间部分解下界为： ti1 + tj2 + mintk3, where j=1,.,n, ki 一般情况下，对1个已经安排的作业集合M，|M|=k，M为1,2,.,n的子集，设sum1k表示机器1完成k个作业的处理时间， sum2k表示机器2完成k个作业的处理时间，现在需要处理作业k+1，此时该部分解的目标函数的下界为：当第k+1步恰好调度第k+1个作业时，(1) sum1k+1=sum1k + tk+1,1(2) lb=maxsum1k+1,sum2k + ti2 /* i不在M中 + mintj3 , /*jk+1, j不在M中(3) sum2k+1 =

41、maxsum1k+1, sum2k +tk+1,2startsum1=0,sum2=0J1, sum1=5lb=36,sum2=1212345J2, sum1=10lb=44,sum2=15J3, sum1=9lb=40,sum2=18J4, sum1=7lb=38,sum2=15J1J2, sum1=15lb=42,sum2=20J1J3, sum1=14lb=38,sum2=23J1J4, sum1=12lb=36,sum2=20678J1J4J2, sum1=22lb=41,sum2=27J1J4J3, sum1=21lb=37,sum2=30910J1J4J3J2, sum1=31lb

42、=36,sum2=3611取lb最小的结点优先扩展6.3 装载问题1. 问题描述有一批共个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集装箱i的重量为Wi，且211ccwnii装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。 容易证明：如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。 (1)首先将第一艘轮船尽可能装满；(2)将剩余的集装箱装上第二艘轮船。 2. 队列式分支限界法（FIFO）（略） 在算法的while循环中，首先检测当前扩展结点的左儿子结点是否为可行结点。如果是则将其加入到活结点队列中将第k个物品装入。然后将其右

43、儿子结点加入到活结点队列中(右儿子结点一定是可行结点)第k个物品不装入。2个儿子结点都产生后，当前扩展结点被舍弃。 活结点队列中的队首元素被取出作为当前扩展结点，由于队列中每一层结点之后都有一个尾部标记-1，故在取队首元素时，活结点队列一定不空。当取出的元素是-1时，再判断当前队列是否为空。如果队列非空，则将尾部标记-1加入活结点队列，算法开始处理下一层的活结点。while (true) / 检查左儿子结点 if (Ew + wi bestw then bestw C(i)8. if i bestw and i n then Enqueue (Q, cw)10. cw Dequeue(Q)93

44、11. if cw=-1 then12. if Q then return bestw13. Enqueue(Q,1)14. cw Dequeue(Q)15. i i+1 r r-wi17. return bestw94问题： n=3， W=8, 6, 2, C1=12 最优解：1 0 195AC(i), B(i)BC(i)=8, B(i)=16CC(i)=0, B(i)=8D, C(i)=14, B(i)=16EC(i)=8, B(i)=1010无效死结点J C(i)=10, B(i)=10KC(i)=8, B(i)=81100963. 算法的改进 节点的左子树表示将此集装箱装上船，右子树表

45、示不将此集装箱装上船。设bestw是当前最优解；ew是当前扩展结点所相应的重量；r是剩余集装箱的重量。则当ew+rbestw时，可将其右子树剪去，因为此时若要船装最多集装箱，就应该把此箱装上船。 另外，为了确保右子树成功剪枝，应该在算法每一次进入左子树的时候更新bestw的值。6.3 装载问题3. 算法的改进/ 检查左儿子结点 Type wt = Ew + wi; / 左儿子结点的重量 if (wt bestw) bestw = wt; / 加入活结点队列 if (i bestw & i 0; j-) bestxj = bestE-LChild; bestE = bestE-parent; 6

46、.3 装载问题5. 优先队列式分支限界法 解装载问题的优先队列式分支限界法用最大优先队列存储活结点表。活结点x在优先队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和。 优先队列中优先级最大的活结点成为下一个扩展结点。以结点x为根的子树中所有结点相应的路径的载重量不超过它的优先级。子集树中叶结点所相应的载重量与其优先级相同。 在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。此时可终止算法。 6.4 布线问题1. 算法思想 解此问题的队列式分支限界法从起始位置a开始将它作为第一个扩展结点。与该扩展结点相邻并且可达

47、的方格成为可行结点被加入到活结点队列中，并且将这些方格标记为1，即从起始方格a到这些方格的距离为1。 接着，算法从活结点队列中取出队首结点作为下一个扩展结点，并将与当前扩展结点相邻且未标记过的方格标记为2，并存入活结点队列。这个过程一直继续到算法搜索到目标方格b或活结点队列为空时为止。即加入剪枝的广度优先搜索。6.4 布线问题Position offset4; offset0.row = 0; offset0.col = 1; / 右 offset1.row = 1; offset1.col = 0; / 下 offset2.row = 0; offset2.col = -1; / 左 off

48、set3.row = -1; offset3.col = 0; / 上定义移动方向的相对位移定义移动方向的相对位移 for (int i = 0; i = m+1; i+) grid0i = gridn+1i = 1; / 顶部和底部 for (int i = 0; i = n+1; i+) gridi0 = gridim+1 = 1; / 左翼和右翼设置边界的围墙设置边界的围墙6.4 布线问题for (int i = 0; i NumOfNbrs; i+) nbr.row = here.row + offseti.row; nbr.col = here.col + offseti.col;

49、if (gridnbr.rownbr.col = 0) / 该方格未标记 gridnbr.rownbr.col = gridhere.rowhere.col + 1; if (nbr.row = finish.row) & (nbr.col = finish.col) break; / 完成布线 Q.Add(nbr); 找到目标位置后，可以通过回溯方法找到这条最短路径。6.5 0-1背包问题算法的思想 首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。 在下面描述的优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。

50、算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时为问题的最优值。6.5 0-1背包问题上界函数while (i = n & wi = cleft) / n表示物品总数，cleft为剩余空间 cleft -= wi; /wi表示i所占空间 b += pi; /pi表示i的价值 i+; if (i = n) b += pi / wi * cleft; / 装填剩余容量装满背包return b; /b为上界函数6.5 0

51、-1背包问题 while (i != n+1) / 非叶结点 / 检查当前扩展结点的左儿子结点 Typew wt = cw + wi; if (wt bestp) bestp = cp+pi; AddLiveNode(up, cp+pi, cw+wi, true, i+1); up = Bound(i+1); / 检查当前扩展结点的右儿子结点 if (up = bestp) / 右子树可能含最优解 AddLiveNode(up, cp, cw, false, i+1); / 取下一个扩展节点（略）分支限界搜索过程分支限界搜索过程6.6 最大团问题 给定无向图G=(V，E)。如果UV，且对任意u

52、，vU有(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的最大团。 1. 问题描述6.6 最大团问题2. 上界函数用变量cliqueSize表示与该结点相应的团的顶点数；level表示结点在子集空间树中所处的层次；用cliqueSize +n-level+1作为顶点数上界upperSize的值。 在此优先队列式分支限界法中，upperSize实际上

53、也是优先队列中元素的优先级。算法总是从活结点优先队列中抽取具有最大upperSize值的元素作为下一个扩展元素。 6.6 最大团问题3. 算法思想 子集树的根结点是初始扩展结点，对于这个特殊的扩展结点，其cliqueSize的值为0。 算法在扩展内部结点时，首先考察其左儿子结点。在左儿子结点处，将顶点i加入到当前团中，并检查该顶点与当前团中其它顶点之间是否有边相连。当顶点i与当前团中所有顶点之间都有边相连，则相应的左儿子结点是可行结点，将它加入到子集树中并插入活结点优先队列，否则就不是可行结点。 接着继续考察当前扩展结点的右儿子结点。当upperSizebestn时，右子树中可能含有最优解，此

54、时将右儿子结点加入到子集树中并插入到活结点优先队列中。6.6 最大团问题3. 算法思想 算法的while循环的终止条件是遇到子集树中的一个叶结点(即n+1层结点)成为当前扩展结点。 对于子集树中的叶结点，有upperSizecliqueSize。此时活结点优先队列中剩余结点的upperSize值均不超过当前扩展结点的upperSize值，从而进一步搜索不可能得到更大的团，此时算法已找到一个最优解。 6.7 旅行售货员问题1. 问题描述 某售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费)。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费)最小。 路线

55、是一个带权图。图中各边的费用（权）为正数。图的一条周游路线是包括V中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。 旅行售货员问题的解空间可以组织成一棵树，从树的根结点到任一叶结点的路径定义了图的一条周游路线。旅行售货员问题要在图G中找出费用最小的周游路线。 6.7 旅行售货员问题2. 算法描述 算法开始时创建一个最小堆，用于表示活结点优先队列。堆中每个结点的子树费用的下界lcost值是优先队列的优先级。接着算法计算出图中每个顶点的最小费用出边并用minout记录。如果所给的有向图中某个顶点没有出边，则该图不可能有回路，算法即告结束。如果每个顶点都有出边，则根据计算出的

56、minout作算法初始化。 算法的while循环体完成对排列树内部结点的扩展。对于当前扩展结点，算法分2种情况进行处理：6.7 旅行售货员问题2. 算法描述 1、首先考虑s=n-2的情形，此时当前扩展结点是排列树中某个叶结点的父结点。如果该叶结点相应一条可行回路且费用小于当前最小费用，则将该叶结点插入到优先队列中，否则舍去该叶结点。 2、当sn-2时，算法依次产生当前扩展结点的所有儿子结点。由于当前扩展结点所相应的路径是x0:s，其可行儿子结点是从剩余顶点xs+1:n-1中选取的顶点xi，且(xs，xi)是所给有向图G中的一条边。对于当前扩展结点的每一个可行儿子结点，计算出其前缀(x0:s，xi)的费用cc和相应的下界lcost。当lcostbestc时，将这个可行儿子结点插入到活结点优先队列中。 6.7 旅行售货员问题2. 算法描述 算法中while循环的终止条件是排列树的一个叶结点成为当前扩展结点。当s=n-1时，已找到的回路前缀是x0:n-1，它已包含图G的所有n个顶点。因此，当s=n-1时，相应的扩展结点表示一个叶结点。此时该叶结点所相应的回路的费用等于cc和lcost的值。剩余的