1、第九章第九章 分支限界法分支限界法1234概述概述图问题中的分支限界法图问题中的分支限界法组合问题中的分支限界法组合问题中的分支限界法小结小结9.1 概述概述 9.1.1 分枝限界法的设计思想分枝限界法的设计思想 9.1.2 分枝限界法的时间性能分枝限界法的时间性能9.1.3 一个简单例子一个简单例子 -圆排列问题圆排列问题 分支限界法按分支限界法按广度优先策略广度优先策略搜索问题的解空间树，搜索问题的解空间树，在搜索过程中，对待处理的结点根据在搜索过程中，对待处理的结点根据限界函数限界函数估算目估算目标函数的可能取值，从中选取使目标函数取得极值标函数的可能取值，从中选取使目标函数取得极值（极
2、大或极小）的结点（极大或极小）的结点优先优先进行进行广度优先搜索广度优先搜索，从而，从而不断不断调整搜索方向调整搜索方向，尽快找到问题的解。，尽快找到问题的解。 分支限界法适用于求解分支限界法适用于求解最优化问题最优化问题。 确定一个确定一个合理的限界函数合理的限界函数，并根据限界函数确定目，并根据限界函数确定目标函数的标函数的界界down, up。 按照按照广度优先策略广度优先策略搜索问题的解空间树，在分支结搜索问题的解空间树，在分支结点上，依次扩展该结点的所有孩子结点，分别估算这点上，依次扩展该结点的所有孩子结点，分别估算这些孩子结点的目标函数的可能取值，某孩子结点的目些孩子结点的目标函数
3、的可能取值，某孩子结点的目标函数的可能取值标函数的可能取值超出目标函数的界超出目标函数的界，则将其，则将其丢弃丢弃；否则，将其否则，将其加入待处理结点表加入待处理结点表（以下简称（以下简称表表PT）中。）中。 依次从表依次从表PT中中选取选取使目标函数使目标函数取得极值的结点取得极值的结点成为成为当前扩展结点当前扩展结点，重复上述过程，直至找到最优解。，重复上述过程，直至找到最优解。9.1.1 分支限界法的设计思想分支限界法的设计思想分支限界法需要解决的分支限界法需要解决的关键问题关键问题 如何确定合适的限界函数。如何确定合适的限界函数。（提示：计算简单，减（提示：计算简单，减少搜索空间，不丢
4、解）少搜索空间，不丢解） 如何组织待处理结点表。如何组织待处理结点表。（提示：表（提示：表PT可以采用可以采用堆堆的形式，也可以采用的形式，也可以采用优先队列优先队列的形式存储。各有什的形式存储。各有什么特点？）么特点？） 如何确定最优解的各个分量。如何确定最优解的各个分量。（提示：（提示：跳跃式处理跳跃式处理解解空树结点，必须空树结点，必须保存保存搜索过程中经过的搜索过程中经过的路径信息路径信息。）。） 回溯法回溯法从根结点出发，按照从根结点出发，按照深度优先策略深度优先策略遍历问遍历问题的解空间树。题的解空间树。分支限界法分支限界法按按广度优先策略广度优先策略搜索问题的解空间树。搜索问题的
5、解空间树。二者与蛮力法区别？二者与蛮力法区别？回溯法与分支限界法区别？回溯法与分支限界法区别？ 一般情况下，在问题的解向量一般情况下，在问题的解向量X=(x1, x2, , xn)中，分量中，分量xi (1in)的取值范围为某个有限集合的取值范围为某个有限集合Si=ai1, ai2, , airi，因此，问题的解空间由，因此，问题的解空间由笛卡儿笛卡儿积积A=S1S2Sn构成构成，并且第，并且第1层的根结点有层的根结点有|S1|棵子树，则第棵子树，则第2层共有层共有|S1|个结点，第个结点，第2层的每个层的每个结点有结点有|S2|棵子树，则第棵子树，则第3层共有层共有|S1|S2|个结点，依个
6、结点，依此类推，第此类推，第n+1层共有层共有|S1|S2|Sn|个结点，个结点，他们都是他们都是叶子结点，代表问题的所有可能解叶子结点，代表问题的所有可能解。9.1.2 分支限界法的时间性能分支限界法的时间性能 类比类比回溯法回溯法分析分支限界法的时间性能分析分支限界法的时间性能11111100000001图8.2 0/1背包问题的解空间树对物品1的选择对物品3的选择对物品2的选择12345781112141531069例如：例如：对于对于n=3的的0/1背包问题解空间树背包问题解空间树 分支限界法分支限界法和和回溯法回溯法实际上都属于实际上都属于蛮力穷举法蛮力穷举法，当，当然不能指望它有很
7、好的最坏时间复杂性，遍历具有指然不能指望它有很好的最坏时间复杂性，遍历具有指数阶个结点的解空间树，在最坏情况下，时间复杂性数阶个结点的解空间树，在最坏情况下，时间复杂性肯定为肯定为指数阶指数阶。 与回溯法不同的是，分支限界法首先扩展解空间树与回溯法不同的是，分支限界法首先扩展解空间树中的上层结点，并采用限界函数，中的上层结点，并采用限界函数，有利于实行大范围有利于实行大范围剪枝剪枝，同时，同时，根据限界函数不断调整搜索方向根据限界函数不断调整搜索方向，选择，选择最有可能取得最优解的子树优先进行搜索。所以，如最有可能取得最优解的子树优先进行搜索。所以，如果选择了结点的合理扩展顺序以及设计了一个好
8、的限果选择了结点的合理扩展顺序以及设计了一个好的限界函数，分支界限法可以快速得到问题的解。界函数，分支界限法可以快速得到问题的解。 分支限界法的较高效率是以分支限界法的较高效率是以付出一定代价付出一定代价为基础的，其为基础的，其工作方式也造成了算法设计的复杂性。工作方式也造成了算法设计的复杂性。首先，首先，一个更好的限一个更好的限界函数通常需要花费更多的时间计算相应的目标函数值，而界函数通常需要花费更多的时间计算相应的目标函数值，而且对于具体的问题实例，通常需要进行且对于具体的问题实例，通常需要进行大量实验，才能确定大量实验，才能确定一个好的限界函数一个好的限界函数；其次，其次，由于分支限界法
9、对解空间树中结由于分支限界法对解空间树中结点的处理是跳跃式的，因此，在搜索到某个叶子结点得到最点的处理是跳跃式的，因此，在搜索到某个叶子结点得到最优值时，为了从该叶子结点求出对应的最优解中的各个分量，优值时，为了从该叶子结点求出对应的最优解中的各个分量，需要对每个扩展结点保存该结点到根结点的路径，或者在搜需要对每个扩展结点保存该结点到根结点的路径，或者在搜索过程中构建搜索经过的树结构，这使得算法的设计较为复索过程中构建搜索经过的树结构，这使得算法的设计较为复杂；杂；再次，再次，算法要维护一个待处理结点表算法要维护一个待处理结点表PTPT，并且需要在表，并且需要在表PTPT中快速查找取得极值的结
10、点，等等。这都需要较大的存储中快速查找取得极值的结点，等等。这都需要较大的存储空间，在空间，在最坏情况最坏情况下，下，分支限界法分支限界法需要的需要的空间复杂性空间复杂性是是指数指数阶阶。 9.1.3 一个简单的例子一个简单的例子圆排列问题圆排列问题问题描述：问题描述：给定给定n个圆的半径序列，将这些圆放个圆的半径序列，将这些圆放到一个矩形框中，各圆与矩形框的到一个矩形框中，各圆与矩形框的底边相切底边相切，则，则圆的不同排列会得到不同的排列长度，要求找出圆的不同排列会得到不同的排列长度，要求找出具有最小长度的圆排列。具有最小长度的圆排列。想法：想法：采用分支限界法求解圆排列问题，采用分支限界法
11、求解圆排列问题，首先首先设计限界函数，设计限界函数，然后然后在搜索过程中选择使目标在搜索过程中选择使目标函数取得极值的结点优先进行扩充。函数取得极值的结点优先进行扩充。 9.2 图问题中的分支限界法图问题中的分支限界法 9.2.1 TSP问题问题 9.2.2 多段图的最短路径问题多段图的最短路径问题问题描述：问题描述：TSP问题是指旅行家要旅行问题是指旅行家要旅行n个城市，要个城市，要求各个城市经历且仅经历一次然后回到出发城市，求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。并要求所走的路程最短。9.2.1 TSP问题问题 想法：想法： 确定目标函数的界确定目标函数的界dow
12、n, up 。（提示：如何确。（提示：如何确定上、下界？）定上、下界？） 确定目标函数值的计算方法（限界函数）。确定目标函数值的计算方法（限界函数）。 基于上、下界，按分支限界法设计思想，搜索解基于上、下界，按分支限界法设计思想，搜索解空间树，得到最优解。空间树，得到最优解。图图9.5(9.5(a) )所示是一个带权无向图，所示是一个带权无向图，( (b) )是该图的代价矩阵。是该图的代价矩阵。271563134253984C= 3 1 5 83 6 7 91 6 4 25 7 4 38 9 2 3 (a) 一个无向图一个无向图 (b) 无向图的代价矩阵无向图的代价矩阵图图 9.5 无向图及其
13、代价矩阵无向图及其代价矩阵1.1.确定问题的上界确定问题的上界1616，下界，下界1414。如何设计求上、下界策略？如何设计求上、下界策略？2.2.确定限界函数计算方法确定限界函数计算方法一般情况下，假设当前已确定的路径为一般情况下，假设当前已确定的路径为U=(r1, r2, , rk)，即路径上已确定了即路径上已确定了k个顶点个顶点，此时，该部分解的目标函数此时，该部分解的目标函数值的计算方法如下：值的计算方法如下：kiUrjikiiijrrrrclb, 11112/ )2(行最小的两个元素素行不在路径上的最小元3.3.基于分支限界法的思想，从根结点开始依次计算基于分支限界法的思想，从根结点
14、开始依次计算目标函数值加入待处理结点表中直至叶子结点。目标函数值加入待处理结点表中直至叶子结点。14,1614,16 3 1 5 83 6 7 91 6 4 25 7 4 38 9 2 3 kiUrjikiiijrrrrclb, 11112/ )2(行最小的两个元素素行不在路径上的最小元根据限界函数计算目标函数的下界根据限界函数计算目标函数的下界down； 采用贪心法得到上界采用贪心法得到上界up；2. 计算根结点的目标函数值并加入待处理结点表计算根结点的目标函数值并加入待处理结点表PT；3. 循环直到某个叶子结点的目标函数值在表循环直到某个叶子结点的目标函数值在表PT中取得极小值中取得极小值
15、 3.1 i = 表表PT中具有最小值的结点；中具有最小值的结点； 3.2 对结点对结点i的每个孩子结点的每个孩子结点x执行下列操作：执行下列操作： 3.2.1 估算结点估算结点x的目标函数值的目标函数值lb; 3.2.2 若若(lb=up)，则将结点，则将结点x加入表加入表PT中；中； 否则丢弃该结点；否则丢弃该结点；4. 将叶子结点对应的最优值输出，回溯求得最优解的各个分量；将叶子结点对应的最优值输出，回溯求得最优解的各个分量；算法描述：算法描述：9.2.2 多段图的最短路径问题多段图的最短路径问题 问题描述：问题描述：设图设图G=(V, E)是一个带权有向连通图，是一个带权有向连通图，如
16、果把顶点集合如果把顶点集合V划分成划分成k个互不相交的子集个互不相交的子集Vi（2kn, 1ik），使得），使得E中的任何一条边中的任何一条边(u, v)，必有必有uVi，vVi+m（1ik, 1i+mk），则称），则称图图G为多段图，称为多段图，称sV1为源点，为源点，tVk为终点。为终点。多多段图的最短路径问题段图的最短路径问题是求从源点到终点的最小代是求从源点到终点的最小代价路径。价路径。1203456789492386884756866537求解过程：求解过程：1. 应用应用贪心法贪心法求得近似解为求得近似解为02589，其路径代价为，其路径代价为2+7+6+3=18，这可以作为多段图
17、最短路径问题的，这可以作为多段图最短路径问题的上界上界。把每一。把每一段最小的代价相加，可以得到一个非常简单的下界，其路径长段最小的代价相加，可以得到一个非常简单的下界，其路径长度为度为2+4+5+3=14。于是，得到了目标函数的界。于是，得到了目标函数的界14, 18。2. 一般情况下，对于一个正在生成的路径，假设已经确定一般情况下，对于一个正在生成的路径，假设已经确定了前了前i段（段（1ik），其路径为），其路径为(r1, r2, , ri, ri+1)，此时，该部，此时，该部分解的目标函数值的计算方法即限界函数如下：分解的目标函数值的计算方法即限界函数如下： kijpiEvrijjjjv
18、rcrrclbpi21,11min1段的最短边第如果部分解包含路径如果部分解包含路径01，则第，则第1段的代价已经确定，并段的代价已经确定，并且在下一段只能从顶点且在下一段只能从顶点1出发，最好的情况是选择从顶点出发，最好的情况是选择从顶点1出发的最短边，则该部分解的下界是出发的最短边，则该部分解的下界是lb=4+8+5+3=20。搜搜索索空空间间分支限界法求解多段图的最短路径问题，搜索过程？分支限界法求解多段图的最短路径问题，搜索过程？9.3 9.3 组合问题中的分支限界法组合问题中的分支限界法 9.3.2 9.3.2 任务分配问题任务分配问题 9.3.3 9.3.3 批处理作业调度问题批处
19、理作业调度问题 9.3.1 9.3.1 0/1 背包问题背包问题 问题描述：问题描述：给定给定n种物品和一个容量为种物品和一个容量为W的的背包，物品背包，物品i的重量是的重量是wi,其价值为其价值为vi,对每种对每种物品物品i只有两种选择：装入背包或不装入背只有两种选择：装入背包或不装入背包，如何选择装入背包的物品，使得装入包，如何选择装入背包的物品，使得装入背包中物品的总价值最大背包中物品的总价值最大?9.3.1 9.3.1 0/1 背包问题背包问题 )()(11iiwvwWvlb1 确定目标函数上、下界；确定目标函数上、下界；2 确定目标函数计算方法；确定目标函数计算方法；一般情况下一般情
20、况下,假设当前已对前假设当前已对前i个物品进行了某种特定的选择个物品进行了某种特定的选择,且且背包中已装入物品的重量是背包中已装入物品的重量是w,获得的价值是获得的价值是v,计算该结点的目计算该结点的目标函数上界的一个简单方法是，将背包中剩余容量全部装入第标函数上界的一个简单方法是，将背包中剩余容量全部装入第i+1个物品个物品,并可以将背包装满并可以将背包装满,于是于是,得到限界函数：得到限界函数：想法：想法：3 依上计算从根结点到叶子结点的目标函数值直到表依上计算从根结点到叶子结点的目标函数值直到表PT中取中取得极大值。得极大值。搜索过程？搜索过程？重量为重量为4,7,5,3价值为价值为40
21、,42,25,12背包容量为背包容量为10单位价值：单位价值：10，6，5，4算法描述：算法描述：1. 根据限界函数计算目标函数的上界根据限界函数计算目标函数的上界up； 采用贪心法得到下界采用贪心法得到下界down；2. 计算根结点的目标函数值并加入待处理结点表计算根结点的目标函数值并加入待处理结点表PT；3. 循环直到某个叶子结点的目标函数值在表循环直到某个叶子结点的目标函数值在表PT中取极大值中取极大值 3.1 i = 表表PT中具有最大值的结点；中具有最大值的结点； 3.2 对结点对结点i的每个孩子结点的每个孩子结点x执行下列操作：执行下列操作： 3.2.1 如果结点如果结点x不满足约
22、束条件，则丢弃该结点；不满足约束条件，则丢弃该结点； 3.2.2 否则，估算结点否则，估算结点x的目标函数值的目标函数值lb， 将结点将结点x加入表加入表PT中；中；4. 将叶子结点对应的最优值输出，回溯求得最优解的各个分量；将叶子结点对应的最优值输出，回溯求得最优解的各个分量；问题描述：问题描述：任务分配问题要求把任务分配问题要求把n项任务分配项任务分配给给n个人，每个人完成每项任务的成本不同，个人，每个人完成每项任务的成本不同，要求分配总成本最小的最优分配方案。要求分配总成本最小的最优分配方案。9.3.2 任务分配问题任务分配问题实例实例C9 2 7 86 4 3 75 8 1 87 6
23、9 4任务任务1 任务任务2 任务任务3 任务任务4人员人员a人员人员b人员人员c人员人员d任务分配成本矩阵如下：任务分配成本矩阵如下： 1、 应用贪心法求得一个合理的上界应用贪心法求得一个合理的上界2+3+5+4=14，将每一行的最小元素加起来就得到解的下界将每一行的最小元素加起来就得到解的下界2+3+1+4=10。最优值一定是。最优值一定是10, 14之间的某个值。之间的某个值。2、设当前已对人员、设当前已对人员1i分配了任务，并且花费了成分配了任务，并且花费了成本本v，则限界函数可以定义为：，则限界函数可以定义为：nikkvlb1行的最小值第想法：想法：假设已经将任务假设已经将任务2分配
24、给人员分配给人员a，任务，任务3分配给人员分配给人员b，花费的，花费的成本是成本是5，则该部分解可能获得的最小成本是，则该部分解可能获得的最小成本是5+(1+4)=10。搜索过程？搜索过程？C9 2 7 86 4 3 75 8 1 87 6 9 4任务任务1 任务任务2 任务任务3 任务任务4abcd 9.3.3 批处理作业调度问题批处理作业调度问题问题描述：问题描述：给定给定n个作业的集合个作业的集合J=J1, J2, , Jn，每，每个作业都有个作业都有3项任务分别在项任务分别在3台机器上完成，作业台机器上完成，作业Ji需要机器需要机器j的处理时间为的处理时间为tij（1in, 1j3），
25、每个作），每个作业必须先由机器业必须先由机器1处理，再由机器处理，再由机器2处理，最后由机处理，最后由机器器3处理。批处理作业调度问题要求确定这处理。批处理作业调度问题要求确定这n个作业个作业的最优处理顺序，使得从第的最优处理顺序，使得从第1个作业在机器个作业在机器1上处理上处理开始，到最后一个作业在机器开始，到最后一个作业在机器3上处理结束所需的上处理结束所需的时间最少。时间最少。批处理作业的一个最优调度应使机器批处理作业的一个最优调度应使机器1没有空闲时没有空闲时间，且机器间，且机器2和机器和机器3的空闲时间最小。可以证明，的空闲时间最小。可以证明，存在一个最优作业调度使得在机器存在一个最
26、优作业调度使得在机器1、机器、机器2和机器和机器3上作业以相同次序完成。上作业以相同次序完成。 想法：想法： T 5 7 910 5 2 9 9 5 7 8 10J1J2J3J4机器1 机器2 机器3实例实例上界确定的方法：上界确定的方法：可以随机产生几个调度方案，从中选取具有最短完成可以随机产生几个调度方案，从中选取具有最短完成时间的调度方案作为近似最优解。时间的调度方案作为近似最优解。 J4:7 J1:5 J3:9 J2:10机器1机器2机器3空闲:7 J4:8 J1:7 J3:9 J2:5空闲:15 J4:10 J1:9 J3:5 J2:2 分支限界法求解批处理作业调度问题的关键在于限界
27、函分支限界法求解批处理作业调度问题的关键在于限界函数，即如何估算部分解的下界。考虑理想情况，机器数，即如何估算部分解的下界。考虑理想情况，机器1和机器和机器2无空闲，最后处理的恰好是在机器无空闲，最后处理的恰好是在机器3上处理时间上处理时间最短的作业。最短的作业。下界确定的方法：下界确定的方法：一般情况下，假设一般情况下，假设M是当前已安排了是当前已安排了k个作业的集合，设个作业的集合，设sum1表示机器表示机器1完成完成k个作业的处理时间，个作业的处理时间，sum2表示机器表示机器2完成完成k个作业的处理时间，现在要处理作业个作业的处理时间，现在要处理作业k+1，此时，此时，该部分解的目标函数值的下界计算方法如下：该部分解的目标函数值的下界计算方法如下：minsum2k,1sum1kmax, 132MjkjjMiittlb（1）sum1 = sum1+ tk+1,1（3）sum2 = maxsum1, sum2 + tk+1,2（2）搜索过程？搜索过程？ 谢谢 谢！谢！
