算法设计与分析 课件 第七章 分支限界 7.3.1 装载问题

计算机算法设计与分析第7章分支限界法7.3.1装载问题一个农场需要将大量农产品运输到市场上去，假设农场现有n种不同的农产品和一辆载重量为c的车辆，农产品i的重量为wi，价值为vi，每种农产品只有装车和不装车两种选择。如何选择装入车辆的农产品，使得车辆不超重的情况下一次装下的农产品总重量最大。

7.3.1装载问题以n=4种农产品为例，车辆载重量c=10，每种农产品的重量W={6,7,2,4}，即w1=6，w2=7,w3=2,w4=4。4种农产品的装载可以表示为一个四元组X=(x1,x2,x3,x4)，xi代表第i种农产品装车的数量，由于每种农产品装载只有装与不装两种情况，所以xi(i=1,2,3,4，表示农产品种编号)只能等于0或1，其中0表示不装车，1表示转入车辆。

装载问题4类农产品装载问题的解向量空间树如图所示

装载问题c：表示车辆的载重量。xi：表示第i种农产品装入车辆的数量，取值0或1。wi：表示第i种农产品的重量。wt：表示当前已装入车的农产品总重量。bestw：表示当前车上装载的农产品重量的最优值。[wt，k]：表示解空间树上一个结点的状态，即从第1种农产品到第k种农产品完成装载选择时，该结点表示的车辆上农产品总重量为wt。Wt(X)：表示解向量X时，车辆装载的农产品总重量。

装载问题给定任意状态[wt，k]，怎么来判断其子结点是否可能得出可行解？约束函数剪枝过程约束函数剪枝过程扩展A结点的左子结点，xk+1=1，wt’=wt+wk+1，如果这时wt’>c，说明装入车辆的农产品重量超过了车辆的载重量，显然这时不可行的，需要被剪枝处理。而扩展A结点的右子结点，xk+1=0，wt≤c，装载的农产品重量与父结点A是一样的，因此扩展右子结点总是可行的。装载问题给定任意状态[wt，k]，怎么来判断其子结点是否可能得出最优解？限界函数剪枝过程：限界函数扩展A结点的右子结点，xk+1=0，其右子结点B的状态为[wt，k+1]。限界函数设装载问题的解向量为X=[X1,X2]，其中X1=[x1,x2,...,xk,0]，X2=[xk+2,...,xn]。X1表示第1种农产品到第k+1种农产品的装车情况，是目前已得到的农产品装车结果；X2表示从第k+2种农产品到第n种农产品的装车情况，是还未考虑过的未知装车结果。限界函数对于解向量X装载农产品的总重量：第1种农产品到第k+1种农产品装入车后的重量为Wt(X1)=wt；第k+2种农产品到第n种农产品装入车后的重量是未知的，用Wt(X2)表示。限界函数我们只能去估计Wt(X2)值的一个上界bound(X2)，上界函数bound(X2)≥Wt(X2)。bestw表示当前已得到的最优值，如果Wt(X1)+bound(X2)≤bestw，则表示当前已装车的农产品总重量加上未装车农产品重量的上界值比当前已知的最优解值还要小。因此，可以判定以A为根的结点扩展其右子结点是不可能得到问题的最优解的，可以剪去A结点的右分支。限界函数那么，如何来估算bound(X2)呢？我们可以将未装车的农产品全部装入，得到bound(X2)=这就是限界函数剪枝过程。限界函数限界函数分析过程，对于bestw值什么时候去获取？如果按照回溯算法分析过程，当得到问题第一个完整解向量时，将这个可行解的值记作第一个bestw的值。但是，得到完整向量的可行解需要搜索到解空间树的叶子结点才能完成。限界函数对于基于广度优先搜索的分支限界法，只能对后续的叶子结点进行限界函数剪枝，而剪枝对于叶子结点来说已经没有实际意义。因此，这样获取的bestw无实际效果。限界函数实际上，我们在扩展任意结点k的左分支时，若其左分支是一个可行解，我们将该左子结点之后的农产品装载全部选择不装车，也可以得到一个完整的解向量，即[x1,,...,xk,1,{0}]。我们可以以这样一个可行解的值作为bestw的值，因此，在扩展左分支时，只要可行（车辆不超重），就及时更新bestw的值。装载问题的约束限界函数（1）进入左分支的约束函数：wt+wk+1≤c（2）进入右分支的限界函数：wt+bound>bestw实例采用队列式分支限界法搜索n=4种农产品（c=10，W={6,7,2,4}，农产品种编号1~4）的装载问题，队列中的结点元素如下列步骤中的各个图所示。我们来定义一个结点元素(wt,bound,k):wt已装入车了农产品的重量bound剩余未装车农产品的总重量k当前被处理农产品种编号n=4种农产品：c=10，W={6,7,2,4}

左子结点采用约束函数wt≤c=10作为剪枝策略右子结点采用限界函数wt+bound>bestw作为剪枝策略（1）初始结点1的三个数据项值为（0，19，0），即wt=0，bound=19，k=0。bestw初值为0。初始结点1入队。1（0,19,0）n=4种农产品：c=10，W={6,7,2,4}（2）取队首结点1，扩展它的左子结点2，wt=6<10，满足约束条件是可行的，x1=1，结点2的三个数据项值为（6,13,1），结点2入队，同时修改bestw=6。然后再来扩展1的右子结点3，wt+bound=0+19>bestw=6，满足限界条件是可行的，x1=0，结点3的三个数据项为（0,13,1），结点3入队。左右子结点扩展完毕，队首结点1出队。之后队列情况：2（6,13,1），3（0,13,1）n=4种农产品：c=10，W={6,7,2,4}（3）取队首元素结点2，扩展它的左子结点4，wt=6+7=13>10，不满足约束条件，是不可行的，结点4被剪枝处理。然后再来扩展它的右子结点5，wt+bound=6+6>bestw，满足限界条件是可行的，x2=0，结点5的三个数据项为（6,6,2），结点5入队。左右子结点扩展完毕，队首结点2出队。之后队列情况：3（0,13,1），5（6,6,2）n=4种农产品：c=10，W={6,7,2,4}（4）取队首结点3，扩展它的左子结点6，wt=0+7<10，满足约束条件是可行的，x2=1，结点6的三个数据项值为（7,6,2），结点6入队，同时修改bestw=7。然后再来扩展它的右子结点7，wt+bound=0+6<bestw=7，不满足限界条件，是不可能产生最优解的，结点7被剪枝处理。左右子结点扩展完毕，队首结点3出队。之后队列情况：5（6,6,2），6（7,6,2）n=4种农产品：c=10，W={6,7,2,4}（5）取队首结点5，扩展它的左子结点10，wt=6+4=10，满足约束条件是可行的，x3=1，结点10的三个数据项值为（10,2,3），结点10入队，同时修改bestw=10。然后再来扩展它的右子结点11，wt+bound=6+2<bestw=10，不满足限界条件，是不可能产生最优解的，结点11被剪枝处理。左右子结点扩展完毕，队首结点5出队。之后队列情况：6（7,6,2），10（10,2,3）n=4种农产品：c=10，W={6,7,2,4}（6）取队首结点6，扩展它的左子结点12，wt=7+4>10，不满足约束条件，是不可行的，结点12被剪枝处理。然后再来扩展它的右子结点13，wt+bound=7+2<bestw=10，不满足限界条件，是不可能产生最优解的，结点13被剪枝处理。左右子结点扩展完毕，队首结点6出队。之后队列情况：10（10,2,3）n=4种农产品：c=10，W={6,7,2,4}（7）取队首结点10，扩展它的左子结点20，wt=10+2>10，不满足约束条件，是不可行的，结点2