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

n=4种农产品：c=10，W={6,7,2,4}（4）取队首结点3，扩展它的左子结点6，wt=0+710，满足约束条件是可行的，x2=1，结点6的三个数据项值为（7,6,2），结点6入队，同时修改bestw=7。然后再来扩展它的右子结点7，wt+bound=0+6bestw=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+2bestw=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+410，不满足约束条件，是不可行的，结点12被剪枝处理。然后再来扩展它的右子结点13，wt+bound=7+2bestw=10，不满足限界条件，是不可能产生最优解的，结点13被剪枝处理。左右子结点扩展完毕，队首结点6出队。之后队列情况：10（10,2,3）n=4种农产品：c=10，W={6,7,2,4}（7）取队首结点10，扩展它的左子结点20，wt=10+210，不满足约束条件，是不可行的，结点20被剪枝处理。然后再来扩展它的右子结点21，wt+bound=10+0=bestw=10，是一个最优解的，结点21（10,0,4）为叶子结点，结点21入队。左右子结点扩展完毕，队首结点10出队。之后队列情况：21（10,0,4）（8）取队首结点21，发现已为叶子结点，不用进行结点扩展，结点21直接出队。（9）队列为空，循环结束。*计算机算法设计与分析第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)，上界