分支限界法

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