第9章分支限界法

第9章分支限界法1.分支限界法的基本思想2.分支限界法在各种问题中的应用分支限界法首先确定一个合理的限界函数，并根据限界函数确定目标函数的界[down,up]。然后，按照广度优先策略遍历问题的解空间树，在分支结点上，依次搜索该结点的所有孩子结点，分别估算这些孩子结点的目标函数的可能取值，如果某孩子结点的目标函数可能取得的值超出目标函数的界，则将其丢弃；否则，将其加入待处理结点表（表PT）中。依次从表PT中选取使目标函数的值取得极值的结点成为当前扩展结点，重复上述过程，直到找到最优解。9.1概述9.1.1解空间树的动态搜索（2）随着遍历过程的深入，表PT中所估算的目标函数的界越来越接近问题的最优解。当搜索到一个叶子结点时，如果该结点的目标函数值是表PT中的极值，则该叶子结点对应的解就是问题的最优解；否则，根据这个叶子结点调整目标函数的界（对于最小化问题，调整上界；对于最大化问题，调整下界），依次考察表PT中的结点，将超出目标函数界的结点丢弃，然后从表PT中选取使目标函数取得极值的结点继续进行扩展。例：0/1背包问题。假设有4个物品，其重量分别为(4,7,5,3)，价值分别为(40,42,25,12)，背包容量W=10。首先，将给定物品按单位重量价值从大到小排序：物品重量(w)价值(v)价值/重量(v/w)144010274263525543124（1）应用贪心法求得近似解为(1,0,0,0)，获得的价值为40-----作为0/1背包问题的下界。（2）0/1背包问题的上界：最好情况下，背包中装入的全部是第1个物品且可以将背包装满，则ub=W×(v1/w1)=10×10=100。（3）目标函数的界[40,100]。限界函数为：)()(11iiwvwWvub×w=0,v=0ub=100w=4,v=40ub=76w=0,v=0ub=60w=11无效解w=4,v=40ub=70w=9,v=65ub=69w=4,v=40ub=64w=12无效解w=9,v=65ub=6523456789×1分支限界法求解0/1背包问题分支限界法求解0/1背包问题，其搜索空间如图9.1所示，具体的搜索过程如下：（1）在根结点1，没有将任何物品装入背包，因此，背包的重量和获得的价值均为0，根据限界函数计算结点1的目标函数值为10×10=100；（2）在结点2，将物品1装入背包，因此，背包的重量为4，获得的价值为40，目标函数值为40+(10-4)×6=76，将结点2加入待处理结点表PT中；在结点3，没有将物品1装入背包，因此，背包的重量和获得的价值仍为0，目标函数值为10×6＝60，将结点3加入表PT中；（3）在表PT中选取目标函数值取得极大的结点2优先进行搜索；（4）在结点4，将物品2装入背包，因此，背包的重量为11，不满足约束条件，将结点4丢弃；在结点5，没有将物品2装入背包，因此，背包的重量和获得的价值与结点2相同，目标函数值为40+(10-4)×5=70，将结点5加入表PT中；（5）在表PT中选取目标函数值取得极大的结点5优先进行搜索；（6）在结点6，将物品3装入背包，因此，背包的重量为9，获得的价值为65，目标函数值为65+(10-9)×4=69，将结点6加入表PT中；在结点7，没有将物品3装入背包，因此，背包的重量和获得的价值与结点5相同，目标函数值为40+(10-4)×4＝64，将结点7加入表PT中；（7）在表PT中选取目标函数值取得极大的结点6优先进行搜索；（8）在结点8，将物品4装入背包，因此，背包的重量为12，不满足约束条件，将结点8丢弃；在结点9，没有将物品4装入背包，因此，背包的重量和获得的价值与结点6相同，目标函数值为65；（9）由于结点9是叶子结点，同时结点9的目标函数值是表PT中的极大值，所以，结点9对应的解即是问题的最优解，搜索结束。9.1.2分支限界法的设计思想假设求解最大化问题，解向量为X=(x1,x2,…,xn)，其中，xi的取值范围为某个有穷集合Si，|Si|=ri（1≤i≤n）。在使用分支限界法搜索问题的解空间树时，首先根据限界函数估算目标函数的界[down,up]，然后从根结点出发，扩展根结点的r1个孩子结点，从而构成分量x1的r1种可能的取值方式。对这r1个孩子结点分别估算可能取得的目标函数值bound(x1)，其含义是以该孩子结点为根的子树所可能取得的目标函数值不大于bound(x1)，也就是部分解应满足：bound(x1)≥bound(x1,x2)≥…≥bound(x1,x2,…,xk)≥…≥bound(x1,x2,…,xn)若某孩子结点的目标函数值超出目标函数的界，则将该孩子结点丢弃；否则，将该孩子结点保存在待处理结点表PT中。从表PT中选取使目标函数取得极大值的结点作为下一次扩展的根结点，重复上述过程，当到达一个叶子结点时，就得到了一个可行解X=(x1,x2,…,xn)及其目标函数值bound(x1,x2,…,xn)。如果bound(x1,x2,…,xn)是表PT中目标函数值最大的结点，则bound(x1,x2,…,xn)就是所求问题的最大值，(x1,x2,…,xn)就是问题的最优解；如果bound(x1,x2,…,xn)不是表PT中目标函数值最大的结点，说明还存在某个部分解对应的结点，其上界大于bound(x1,x2,…,xn)。于是，用bound(x1,x2,…,xn)调整目标函数的下界，即令down=bound(x1,x2,…,xn)，并将表PT中超出目标函数下界down的结点删除，然后选取目标函数值取得极大值的结点作为下一次扩展的根结点，继续搜索，直到某个叶子结点的目标函数值在表PT中最大。分支限界法求解最大化问题的一般过程分支限界法的一般过程1．根据限界函数确定目标函数的界[down,up]；2．将待处理结点表PT初始化为空；3．对根结点的每个孩子结点x执行下列操作3.1估算结点x的目标函数值value;3.2若(value=down)，则将结点x加入表PT中；4．循环直到某个叶子结点的目标函数值在表PT中最大4.1i=表PT中值最大的结点；4.2对结点i的每个孩子结点x执行下列操作4.2.1估算结点x的目标函数值value;4.2.2若(value=down)，则将结点x加入表PT中；4.2.3若(结点x是叶子结点且结点x的value值在表PT中最大)，则将结点x对应的解输出，算法结束；4.2.4若(结点x是叶子结点但结点x的value值在表PT中不是最大)，则令down=value，并且将表PT中所有小于value的结点删除；应用分支限界法的关键问题（1）确定合适的限界函数（2）组织待处理结点表PT（3）确定最优解中的各个分量分支限界法对问题的解空间树中结点的处理是跳跃式的，回溯也不是单纯地沿着双亲结点一层一层向上回溯。当搜索到某个叶子结点且该叶子结点的目标函数值在表PT中最大时（假设求解最大化问题），求得了问题的最优值。但是，却无法求得该叶子结点对应的最优解中的各个分量。这个问题可以用如下2种方法解决：①对每个扩展结点保存该结点到根结点的路径；②在搜索过程中构建搜索经过的树结构，在求得最优解时，从叶子结点不断回溯到根结点，以确定最优解中的各个分量。(0)60(1,0,0)64(1,0,1,0)65(a)扩展根结点后表PT状态(b)扩展结点2后表PT状态(c)扩展结点5后表PT状态(d)扩展结点6后表PT状态，最优解为(1,0,1,0)65图9.2方法①确定0/1背包问题最优解的各分量(0)60(1,0,1)69(1,0,0)64(1)76(0)60(0)60(1,0)70例如图9.1所示0/1背包问题，为了对每个扩展结点保存该结点到根结点的路径，将部分解(x1,…,xi)和该部分解的目标函数值都存储在待处理结点表PT中，在搜索过程中表PT的状态如图9.2所示。(a)扩展根结点后(b)扩展结点2后(c)扩展结点5后(d)扩展结点6后，最优解为(1,0,1,0)65图9.3方法②确定0/1背包问题最优解的各分量(0,1,176)(0,1,060)PTST(0,1,060)(1,2,070)PTST(0,1,176)(0,1,060)(0,3,169)(0,3,064)PTST(0,1,176)(1,2,070)(0,1,060)(0,3,064)(1,4,065)PTST(0,1,176)(1,2,070)(0,3,169)图9.1所示0/1背包问题，为了在搜索过程中构建搜索经过的树结构，设一个表ST，在表PT中取出最大值结点进行扩充时，将最大值结点存储到表ST中，表PT和表ST的数据结构为(物品i-1的选择结果，物品i,物品i的选择结果ub)，在搜索过程中表PT和表ST的状态如图9.3所示。9.1.3分支限界法的时间性能分支限界法和回溯法实际上都属于蛮力穷举法。与回溯法不同的是，分支限界法首先扩展解空间树中的上层结点（广度优先），并采用限界函数，有利于实行大范围剪枝，同时，根据限界函数不断调整搜索方向，选择最有可能取得最优解的子树优先进行搜索。关键点：结点的合理扩展顺序、好的限界函数分支限界法的较高效率是以付出一定代价为基础的，其工作方式也造成了算法设计的复杂性。首先，通常需要进行大量实验确定限界函数其次，由于分支限界法对解空间树中结点的处理是跳跃式的，因此，在搜索到某个叶子结点得到最优值时，为了从该叶子结点求出对应的最优解中的各个分量，需要对每个扩展结点保存该结点到根结点的路径，或者在搜索过程中构建搜索经过的树结构，这使得算法的设计较为复杂；再次，算法要维护一个待处理结点表PT，并且需要在表PT中快速查找取得极值的结点，等等。这都需要较大的存储空间，在最坏情况下，分支限界法需要的空间复杂性是指数阶。9.2图问题中的分支限界法9.2.1TSP问题9.2.2多段图的最短路径问题9.2.1TSP问题TSP问题是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。271563134253984C=∞31583∞67916∞42574∞38923∞(a)一个无向图(b)无向图的代价矩阵图9.4无向图及其代价矩阵采用贪心法求得近似解为1→3→5→4→2→1，其路径长度为1+2+3+7+3=16，这可以作为TSP问题的上界。把矩阵中每一行最小的元素相加，可以得到一个简单的下界，其路径长度为1+3+1+3+2=10，但是还有一个信息量更大的下界：考虑一个TSP问题的完整解，在每条路径上，每个城市都有两条邻接边，一条是进入这个城市的，另一条是离开这个城市的，那么，如果把矩阵中每一行最小的两个元素相加再除以2，如果图中所有的代价都是整数，再对这个结果向上取整，就得到了一个合理的下界。lb=((1+3)+(3+6)+(1+2)+(3+4)+(2+3))/2=14于是，得到了目标函数的界[14,16]。需要强调的是，这个解并不是一个合法的选择（可能没有构成哈密顿回路），它仅仅给出了一个参考下界。部分解的目标函数值的计算方法图9.4所示无向图，如果部分解包含边(1,4)，则该部分解的下界是lb=((1+5)+(3+6)+(1+2)+(3+5)+(2+3))/2=16。UrUrjikiiiijrrrrclb2/)]][[2(111行最小的两个元素素行不在路径上的最小元41→2lb=142356781×startlb=141→3lb=141→4lb=161→5lb=192→3lb=162→4lb=162→5lb=193→2lb=163→4lb=153→5lb=14×910115→2lb=195→4lb=141213×4→2lb=16144→2lb=184→5lb=151516×5→2lb=2017×分支限界法求解TSP问题示例应用分支限界法求解图9.4所示无向图的TSP问题，其搜索空间如图9.5所示，具体的搜索过程如下（加黑表示该路径上已经确定的边）：（1）在根