1、第6章 分支限界法,分支限界法原理与算法框架 分支限界法 vs 回溯法应用范例（1）旅行商问题（2）单源最短路径问题（3）0-1背包问题应用范例（略）（4）多段图最短路径（5）装载问题（6）批处理作业调度问题,6.1分支限界法原理,与回溯法类似，一种基于解空间搜索的问题求解策略回溯法原理：1）利用某种数据结构解向量，形式化地表示问题解 e.g. n个城市旅行商问题(TSP) 解向量表示为长度为n的向量x1:n=2）问题的各种解组成了问题解空间最优解、次优解/可行 解、错误/不可行解、部分解,3）问题解应满足各种约束约束，包括: 显约束：对解空间中分量xi的取值限定 e.g. TSP xi 1,
2、2,3,n 隐约束：为满足问题的解而对不同分量之间施加的约束 e.g. TSP，各个城市只能遍历一次4）解空间中各个解根据相互间关系 和解的构造顺序，组成解空间树,e.g. 4个城市的旅行商问题,1） 非叶结点对应部分解2）叶节点对应最优解、可行解,5）对解空间中的解，引入定量指标，作为优化依据 e.g. 旅行商问题：旅游路径总长最短6）问题求解过程带有回溯的深度优先树搜索 以深度优先的方式，从树根结点开始，依次扩展树结点，直到达到叶结点搜索过程中动态产生解空间 深度优先目的：尽可能快地获得可行解,扩展过程中，碰到可行非叶结点（部分解），可进一步扩展 e.g. 结点C对应部分解 可进一步扩展为
3、: F= G= ,碰到不可行非叶/叶结点（不可行（部分）解），需要返回到上一层结点回溯 e.g. 对C结点，下一步的扩展有4种可能选择：3、4、1、2，每种选择都可以继续扩展子树；但只有其中2种选择是合理的，对后2种选择不再继续扩展，而是返回C结点,4,7）为了提高搜索效率，用剪枝函数（面向具体问题）避免无效搜索，即避免不可行解对应的子树或结点e.g. 剪枝条件/约束1： 如果当前正在考虑的顶点j与当前路径中的末端结点i没有边相连，即wi, j= , 则不必搜索j所在分支 E.g. 当前已有的部分路径为, ,路径末端结点为2, 下一步可考虑将顶点3、4加入到部分路径中。 但是，顶点2与4间无边
4、，w(2,4)= , 因此在解空间树中，可以不必考虑顶点4所在分支,剪枝条件2：假设：已经知道直到第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，根据界限函数，估计沿该结点向下搜索所可
5、能达到的完全解的目标函数的可能取值范围界限bound(vi)=downi, upi3）从中选择使目标函数取的极值（最大、最小）的结点优先进行宽度优先搜索，从而不断调整搜索方向，尽快找到问题解关键：各结点的界限函数bound(vi)=downi, upi, 依据具体问题而定e.g. 4个城市的TSP搜索树中的界限函数,bound(G),bound(D),bound(E),子树,子树,子树,一、与回溯法类似，解向量、解空间、解空间树二、解空间树中的结点分为4种类型 活结点，死结点，扩展结点，待处理结点,扩展结点,未处理结点, 活结点 当前满足约束条件、未来有可能产生最优解的结点； 对应部分解, e
6、.g. 结点G、D、E 所有活结点组成活结点表ANT (Alive Node Table), 扩展结点 从活结点表ANT中取出来，当前准备进行扩展的结点，即当前进行处理的结点 1）评估每个活结点价值，按照价值最大化/最小化原则，从 ANT中选取扩展结点 e_node 2）e_node扩展方式： 宽度优先，生成e_node的全部子节点； 评估这些子节点，满足界限约束、有可能产生更优解的 结点被作为活结点，加入ANT；不满足约束、或无法产生 最优解的子节点被舍弃剪枝 3） e_node结点被扩展后，该结点转换为死结点，以后将不会 被再搜索 活结点扩展结点死结点,e.g. 如下图 i) 从上图中的3
7、个活结点G、D、E中，选择价值最大的结点D，作为扩展结点,ii) 生成D的全部2个子结点H、I，经评估后，作为活结点加入 ADT表中iii) D变为死结点,B,C,F,E,L,2,3,4,4,A,1,4,G,3,第1步,第2步,第3步,第4步,H,I,D,2,4, 死结点： 1）已经处理过（搜索过）、不再处理的结点; e.g. A, B, C, F, L 2）不满足约束条件、无法产生最优解的结点. e.g. 结点G, 对应部分解, 而 w(4,3)=, 未处理结点 解空间树中位于活结点之下，还没有被搜索/处理到、不属于上述三类结点的其它结点 在后续的搜索过程中，通过结点扩展会逐步生成,三、解空
8、间树的扩展 选定扩展结点e_node，生成其全部子结点采取宽度优先进行扩展 e.g. 结点D对应于，考察它的2个子结点和,四、对扩展结点e_node，生成其全部儿子结点后，判断评估每个儿子结点： i) 是否满足约束条件。如不满足，则作为死结点 ii）估算沿着儿子结点向下搜索时，目标函数可能取得的“界”，即沿着儿子结点向下构造出的最终解可能取得的目标函数的范围； -极大化目标，估计子节点目标函数上界 -极小化目标，估计子节点目标函数下界 iii）将全部活结点组织在活结点表ANT中 利用活结点的“界”值，对活结点进行价值评估是否有可能得到最优解？ 关键：目标函数界限函数！,五、扩展结点e_node
9、选取 扩展树时，需要从活结点表ANT中选取合适的活结点，将其转化为扩展结点e_node 1) 对最小化问题（如TSP），选取具有最小“界”的活结点 e.g. 前图中，部分解D的最小界：经过D的最短路径长度至少（下界）是多少 2) 对最大化问题（如背包问题），选取具有最大“界”的活结点，物品装入方案的最大价值 e.g. 3) 当到达1个叶结点时，得到1个可行解，该可行解对应的最优值bound(x1,x2,xn)可作为当前最优解的1个“界”,六、结点界限函数及剪枝 进行结点/树扩展时，利用界限函数估计每个结点可能达到的最优解，进行剪枝 1) 估计e_node的每个儿子结点ci的“界”bound(c
10、i) -极大化目标，估计子结点目标函数上界 -极小化目标，估计子结点目标函数下界 2) 比较bound(ci)与活结点表ANT中现有活结点*的最优界限值bound(*) 对最小化问题，e.g. 最短路径，如果bound(ci) bound(*)，沿ci搜索得到可行解不可能小于目前已经得到的最优解，则结点ci不应加入活结点表剪枝，不考虑该结点,e.g. 已知 的路径总和=20；结点G对应如果路径1-2-4的总长=21，则结点G被舍弃 对最大化问题， e.g. 背包问题，如果bound(ci) = down），将x加入ANT表 /* 对最大化问题，要求沿x分支搜索到的完全解的目标值（上界）估计必须
11、大于现有已知的目标函数的下界down,循环，直到某个叶结点的目标函数值在表ANT中最大 /* 找到1个具有最大值的完全解 4.1 从表ANT中选择bound(vi)值最大的结点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对应的完全
12、解输出，算法结束 /* 结点c对应了1个新找到的、具有最大目标 函数值的完全解最优解,4.2.4 如果（c是叶结点 and bound(c)在表ANT中不是最 大），则： /*结点c对应了1个新找到的完全解，但该完全解的目标 函数值与已经找到的、或未来可能找到完全解相比，并非更优 i) 令down = value(c) /*利用新找到的完全解的实际目标函数，更新问题的下界 ii) 对表ANT中所有满足bound(vj) bound(c)的结点vj， 从表ANT中删除该结点！ /* 利用新找到的完全解的目标函数bound(c) ，进行剪枝，从ANT 表中去掉那些目标函数值不可能大于结点c的bou
13、nd(c)的结点vj， 即去掉那些目标函数值小于由于当前新找到的完全解c的目标值 bound(c)的结点,分支限界法是一种高效、通用的问题求解方法。此方法发明者曾获计算机界最高奖项图灵奖。分支限界法三个关键技术1. 如何确定合适的限界函数 面向具体问题而定2. 如何合理组织活结点表决定了结点扩展顺序 1）FIFO队列：按照先进先出（FIFO）原则，选取下一个节点为扩展节点 2）优先队列：按照优先队列中规定的优先级选取优先级最高的节点，成为当前扩展节点。 3）堆,3. 如何确定最优解中的各个分量 对解空间树中的结点处理是根据结点的bound值进行的，有可能是跳跃式的，回溯也不是单纯沿着双亲结点一
14、层层向上回溯。因此，当在某个叶结点上搜索到全局最优值时，有可能无法得到组成该最优解的各个分量。 为此，可采用下述处理方法： 1）对每个扩展结点，保存从根结点到该结点的路径 2）在搜索过程中，构建搜索经过的树结构。当求得最优解后，从叶结点回溯到根结点，得到最优解各个分量 问题：用于存储搜索树的存储空间可能会很大，增大了算法的空间复杂性,B,C,F,D,L,2,3,4,4,A,1,4,G,3,E,H,I,2,4,根据活结点表中各节点具体bound值，先处理D，后处理E，基本符合宽度优先序序,根据活结点表中各节点具体bound值，先处理E，后处理D，不符合宽度优先序序,分支限界法 vs 回溯法,求解
15、目标： 回溯法的求解目标是找出解空间树中满足约束条件的所有（？或多个）解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。,2. 搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。,3. 解空间树的扩展 对扩展结点e_node，生成其全部子结点采取宽度优先或以最小耗费（最大效益）优先进行扩展，需要维护活结点表，因此占用的空间比回溯法大，但计算速度一般比回溯法快以空间换时间！,此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结
16、点表为空时为止。,在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。,6.2最短路径问题,问题描述： 在下图所给的有向图G中，每一边都有一个非负边权。 要求：求出从源点s到目标点t之间的最短路径。,用优先队列式分支限界法，解空间树：1） 树中边上的字母代表每一步经过的结点间路径2）树节点上的数字表示从源点s到该结点所对应的当前路长3）以经历过的边表示路径e.g. 以图中顶点表示的路径s-1-2-5, 边表示的路径s a:u:f,算法思想,1. 解空
17、间树中的结点v 对应1条从源点s到图中某个顶点的路径；叶节点对应1条s到目标点t的路径； 每个结点v需要记录本路径从s开始、经过的全部边或顶点 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. 活结点表的组织 组织为极小堆，其优先级/目标函
18、数是结点所对应的当前路径长度dist,说明：教科书上的下界函数只考虑了当前部分路径的现有长度，没有考虑未来结点可能带来的路径长度，下界函数不准确e.g. 对部分路径s1 2 5, 书上给出的下界值/优先级/目标函数只是取为当前路径长度14； 但显然对该部分解，不管从结点5向后如何走，下界值肯定比14大,4. 搜索过程1）从源顶点s、空优先队列开始，首先选择s作为扩展结点2）结点s被扩展后，它的儿子结点被依次插入活结点表堆中3）从堆中取出优先级最高(即：dist(v)/目标函数/下界最小）的树结点v，作为当前扩展结点 v对应的路径为s-i1-i2-ik 与堆中其它结点相比，该路径的长度dist(
19、v)最小 e.g. 见下页，堆中有3个活结点，对应了三条路径s-1-2-5、s-1-5-6-9、s-2，路径长度dist分别为14、6、3 应选择dist最小的路径s-2，即原图中的城市顶点2应作为扩展结点,4) 生成扩展结点的子结点 在G (V,E)中，依次检查与当前扩展结点相邻的所有顶点。 e.g. 如果城市顶点2被选为扩展结点，则需要考察经过边f、g可到达的城市顶点5、65) 考察各子结点是否可作为活结点是否有必要进一步扩展? 如果 i) 从当前选择的扩展城市顶点i到它的邻接城市顶点j有边可达，并且 ii) 从源s出发，途经城市顶点i再到顶点j的所相应的路径的长度小于当前已经得到的最优路
20、径长度(或问题上界up), 即： dist(i) + distance(i, j) mindist=8, 被剪枝舍弃 右子结点表示路径s-3-6-9，dist=7 =8, 结点j就成为死结点； 只有dist(j)问题上界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,7Step5. 从ANT中，选择 lb最小的结点3扩展，生成结点9
21、、10、11,Step6. 按照上述方法，依次扩展搜索树，得到最优解 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+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个物品，左分支放入，右分支不放入,1,2,67,限界函数（
22、最大化问题） 下界down：贪心法， 第1个可装入的、具有最大价值/重量比的物品所具 有的价值，(1,0,0,0) , down=40 上界up：背包中全部装入第1个物品，且装满， up=10*10=100 问题限界40,100对第k层结点，代表了对物品1i作出的选择，假设已经装入的物品重量为w，获得的价值为v该结点的限界函数ub： 已装入背包中物品取得的价值v + 背包剩余容量（C-w）*剩余物品中的最大单位重量价值,68,问题完全解界限40, 100,1,1,1,2,3,4,5,无效死结点(wC),6,7,无效死结点(wC),9,8,剪枝条件: ub 上界18 3. 如果是，则该结点被剪枝
23、舍弃 e.g. 结点2， 对应路径01 结点10， 对应路径03 5 7,问题完全解界限14, 18,1. 树结点编号对应了结点搜索/生成顺序2. 表示被丢弃的死结点,2+7+5+3=17,3+4+5+3=15,2+8+5+7=22,2+7+6+3=18,2+8+5+3=18,4+8+5+3=20,3+4+6+3=16,3+7+5+3=18,3+4+8+7=22,3+4+6+3=16,1. 采用贪心法，计算上界up； 根据目标函数公式，计算下界down2. 将活结点表ANT初始化为空3. for ( i=1; i =1) 5.1 对顶点u的所有邻接点v 5.1.1 计算v的目标函数lb(v)
24、5.1.2 if (lb , lb(v)值 存入活结点表ANT 5.2 如果i=k-1, 即搜索到达叶节点，并且叶子结点的目标函 数值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个作
25、业的集合J=J1,J2,Jn,每个作业有3项任务需要在3台机器上完成，作业Ji需要机器j的处理时间为tij（1i n, 1j3 ）。每个作业需要依次在机器1、2、3上处理。要求：确定作业最优处理顺序，使得从第1个投入执行的作业在机器1上开始，到最后1个作业在机器3上结束为止，所需时间最短。最优调度：机器1上无空余时间，机器2、3上的空闲/等待时间最短可以证明：对最优调度，作业在机器1上的执行顺序与机器2、3上的执行顺序是一致的。,分支限界法的复杂性,与回溯法一样，分支限界法属于蛮力穷举法。最坏情况下，需要遍历指数阶个结点的解空间树，复杂性为指数阶。与回溯法不同：优先扩展上层结点，采用界限函数，利于大范围剪枝，缩小搜索空间；同时，利用限界函数，不断调整搜索方向，选择最优可能获得最优解的子树优先搜索性能密切依赖于限界函数对具体问题，很难预测分支限界法的搜索行为跳跃式搜索，构造完整解比较麻烦空间复杂性较高，最坏情况下，空间复杂性为指数阶,作业在机器上的处理时间矩阵T,
