分支及限界：货物装载问题

1、 分支与限界：货物装载问题课程名称： * 院 系： * 学生姓名： * 学 号： * 专业班级： *指导教师： * 2013年12月27日第 16 页 共 16 页分支与限界：货物装载问题摘要：在现实生活中，我们会经常遇见货物装载问题，如何解决货物装载问题，获取利润的最大化，花费最少的而得到更多的东西，是人们一直都要考虑的问题。在广泛的解决问题中，人们一般采用分支限界算法解决这样的问题。分支限界法是由分支策略和限界策略两部分组成的。分枝定界法是一个用途十分广泛的算法，运用这种算法的技巧性很强，不同类型的问题解法也各不相同。该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集（称为分支

2、），并为每个子集内的解的值计算一个下界或上界（称为定界）。在每次分支后，对凡是界限超出已知可行解值那些子集不再做进一步分支。这样，解的许多子集（即搜索树上的许多结点）就可以不予考虑了，从而缩小了搜索范围。该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集（称为分支），并为每个子集内的解的值计算一个下界或上界（称为定界）。在每次分支后，对凡是界限超出已知可行解值那些子集不再做进一步分支。这样，解的许多子集（即搜索树上的许多结点）就可以不予考虑了，从而缩小了搜索范围。分支策略体现在对问题空间是按广度优先的策略进行搜索，限界策略是为了加速搜索速度而采用启发信息剪枝的策略。在分支限界法，经

3、常采用的是分支搜索法，分支搜索法是一种在问题空间上进行搜索尝试的算法。所谓分支是采用广度优先的策略，依次搜索E-结点的所有的分支，也就是所有的相邻结点。和回溯法一样，在生成的节点中，抛弃那些不满足的约束条件的的结点，其余结点加入活结点表。在分支搜索的算法中，人们经常会采用FIFO搜索和优先队列式搜索。例题中采用的是轮船装载的问题，这是一个非常经典的分支限界算法的例题，通过这个例子的学习，将会理解并掌握分支限界货物装载的问题。关键词：分支限界法 货物装载 FIFO分支限界 优先队列分支限界 目录第一章 绪论41.1分支-界限算法的基本思想41.2常见的两种分支界限算法4第二章 货物装载问题52.

4、1 问题描述52.2 问题分析5第三章 优先队列式分支限界法解决货物装载问题63.1 算法设计63.2 数据结构设计73.2.1程序流程图73.2.2 数据结构描述73.2.3 重要算法83.3 测试结果与分析9第四章 基于队列式(FIFO)分支限界法解决货物装载问题104.1 算法设计104.2 数据结构设计104.2.1程序流程图114.2.2 数据结构描述和算法114.3 测试结果与分析13第五章 结论14参考文献15第一章 绪论1.1分支-界限算法的基本思想分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。

5、活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。1.2常见的两种分支界限算法 队列式(FIFO)分支限界法按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。FIFO搜索算法要依赖“队”做基本的数据结构。一开始根节点是唯一的活结点，根节点入队。从活结点的对中取出艮结点后，作为当前扩展结点。对当前扩展结点，先从左到右地产生它的所有儿子，用约束条件检查，把所有满足约束函数的儿子

6、加入到活结点队列中。再从活结点表中取出队首结点为当前扩展结点。优先队列式分支限界法按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。优先队列式搜索，对每一个活结点计算一个优先级，并根据这些优先级，从当前活结点表中优先选择一个一个优先级最高的节点作为扩展结点，使搜索朝着解空间树上最优解的分支推进，以便尽快找出一个最优解。第二章 货物装载问题2.1 问题描述有两艘船和需要装运的N个货箱，第一艘船的载重量是c1,第二艘船的载重量是c2，wi是货箱i的重量，且w1+w2+.+wn<=c1+c2。希望确定是否有一种可能将所有货箱全部装船的方法。若有的话，找出该方法。2.2 问题分析先

7、看一个实例，当n=3,c1=c2=50,w=10,40,40时，可将货箱1,2装到第一艘船上，货箱3装到第二艘船上。但如果w=20,40,40,则无法将货箱全部装船。有此可知问题可能有解，可能无解，也可能多解。虽然是关于两艘船的问题，若w1+w2+w3+.wn-bestw<=c2则可能确定一个解，否则问题就无解。这样的问题就转化为第一艘船的最大装载问题。第3章 优先队列式分支限界法解决货物装载问题3.1 算法设计 解装载问题的优先队列式分支限界法用最大优先队列存储活结点表。活结点x在优先队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和。优先队列中优先级最

8、大的活结点成为下一个扩展结点。优先队列中活结点x的优先级为x.uweight。以结点x为根的子树中所有结点相应的路径的载重量不超过x.uweight。子集树中叶结点所相应的载重量与其优先级相同。因此在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解，此时终止算法。通过实验，了解了分支限界法的基本思想。掌握了利用优先队列式分支限界法实现具体的装载问题。由于利用java.util包下的PriorityQueue代替算法中的最大堆，免去了编写实现最大堆的程序代码。优先队列式分支限界法进行算法设计的要点如下：（1） 结点扩展方式：无论是那种分支限界法，需

9、要有一张活的结点表。优先队列的分支限界法将活结点组成一个优先队列，并按优先队列中规定的结点优先选取最高的下一个结点成为当前扩展结点。（2） 结点优先级确定：优先队列中的结点优先级长规定一个与该节点相关的数值w,w一般表示以该节点为根的子树的分支接近最优解的程度。（3） 优先队列组织：结点优先级确定后，按结点优先级进行排序，就生成了优先队列。排序算法的时间复杂度较高，考虑到搜索算法每次只扩展一个结点，数据结构中堆排序，适合这一特点且比较交换的次数最少。此例采用最大堆来实现优先队列。3.2 数据结构设计3.2.1程序流程图 图3-1优先队列限界法流程图3.2.2 数据结构描述（1） 要输出解的方案

10、，在搜索过程中仍需要生成解结构树，其结点信息包括指向父结点的指针和标识物品取舍（或是父结点的左、右孩子）。（2） 堆结点包括结点优先级信息：结点所在分支的装载上界uweight；堆中无法体现结点的层次信息（level），只能存储在结点中；（3） 由于扩展结点不是按层进行的，计算结点所在分支的装载上界时，要用数组变量r记录当前层以下的最大重量，这样可随时方便使用各层结点的装载上界。3.2.3 重要算法HeapNode H1000;struct bbnode bbnode *parent; / 父结点指针 int LChild; ; /当且仅当是父结点的左孩子时，取值为1struct HeapNo

11、de bbnode *ptr; / 活结点指针 float uweight; / 活结点的重量上限int level; ; MaxLoading(float c, int n, int bestx) float r100,Ew,bestw=0; rn=0; for (int j=n-1; j > 0; j-) rj=rj+1 + wj+1; int i = 1; bbnode *E = 0; Ew = 0; / 搜索子集空间树 while (i != n+1) / 不在叶子上 if (Ew+wi<=c) / 可行的左孩子 AddLiveNode(E,Ew+wi+ri,1,i+1);

12、 if (bestw<Ew+wi) bestw=Ew+wi; if(bestw<Ew+ri) AddLiveNode(E,Ew+ri,0,i+1); DeleteMax(H,E);i=N.level;E=N.ptr; Ew=N.uweight-ri-1; for (int j=n;j>0;j-) bestxj = E->LChild; E = E->parent; return Ew; AddLiveNode(float wt, int lev,bbnode *E, int ch) bbnode *b=new bbnode; b->parent=E; b-&

13、gt;LChild=ch; HeapNode N; N.uweight=wt; N.level=lev; N.ptr=b; Insert(H,N) ; 3.3 测试结果与分析图3.2 货物装载问题的解由图可以看出，当输入货箱的个数为5时，第一艘船的载重量为50，第二艘船的载重量为70时，每个货箱的质量分别是12,14,16,20,20，得到如下图的结果。第4章 基于队列式(FIFO)分支限界法解决货物装载问题4.1 算法设计将此问题转化为一艘船的最优化问题，问题的解空间为一个子集树。也就是算法要考虑的所有物品的取、舍情况的组合，n个物品的取舍组合共2的N次个分支，搜索子集树是NP-复杂问题。如

14、下图所示，xi为1表示选取第i件物品，xi 为0表示不选取第i件物品。搜索结点3,时 可以确定它不必被扩充为活结点；因为扩展结点1后，就知道最大装载量不会小于50；而扩展节点3时，发现此分支的“装载上界”为w2+w3=20<50,无需搜索此分支，节点3不必入队。图 4-1 子集图4.2 数据结构设计用FIFO分支搜索所有的分支，并记录已搜索分支的最优解，搜索完子集树也就找到出了问题的解。要想求出最优解，必须搜素出最优解，必须搜索到叶节点。所以要记录树的层次，当层次为n+1时，搜索完全部叶节点，算法结束。不同于回溯算法，分支搜索过程中活节点的“层”是需要标志飞，否则在入队后就无法识别节点所

15、在的层。4.2.1程序流程图 图4-2优先队列限界法流程图4.2.2 数据结构描述和算法float bestw,w100,bestx100;int n；Queue Q;struct QNode float weight; QNode *parent; QNode LChild; main( ) int c1,c2,n, s=0,i; input(c1,c2,n); for(i=1;i<=n;i+) input(wi); s=s+wi; if (s<=c1 or s<=c2) print(“need only one ship”); return; if (s>c1+c2

16、) print(“no solution”); return; MaxLoading(c1); if (s-bestw <=c2); print(“The first ship loading”, bestw,“chose:”); for(i=1;i<=n;i+) if (bestxi=1) print(i,“,”); print(“换行符 The second ship loading”, s-bestw,“chose”); for(i=1;i<=n;i+) if (bestxi=0) print(i,”,”); else print(“no solution”); Max

17、Loading(int c) Qnode *E; /活结点队列 int i = 1; /E-结点的层 E= new QNode; add (Q,0) ; /0代表分层标记 E->weight=0; E->parent =null; E->Lchild=0; add (Q,E) ; bestw=0; r=0; / E-结点中余下的重量 Ew=E->weight; /E-结点的重量 for (int j=2;j<=n;j+) r=r+ wj; while (true) / 搜索子集空间树 wt=Ew+wi; / 检查E-结点的左孩子 if (wt<=c) /可行

18、的左孩子 if (wt>bestw) bestw=wt; AddLiveNode(wt,i, E ,1); if (Ew+r>bestw) / 检查右孩子 AddLiveNode(Ew,i,E,0); Delete (Q,E ) ; / 下一个E-节点if (E=0) / 层的尾部 if (Empty(Q ) break; add (Q, 0) ; / 层尾指针 Delete(Q,E) ; / 下一个E-结点 i+ ; / E-结点的层次 r=r-wi; / E-结点中余下的重量 Ew=E->weight ; / 新的E-结点的重量 / 沿着从bestE到根的路径构造best

19、x for (j=n-1;j>0;j-) bestxj=bestE->LChild; /从bool转换为int bestE=bestE->parent; return bestw; 4.3 测试结果与分析图4.3 货物装载问题的解由结果可以看出，当货箱的质量分别为12 14 16 20 25 时，两个货船的载重量分别为50,70.由此算法可以得到第一艘船可以达到满装 14 16 20，第二艘船可以装剩下的37。第5章 结论通过本次的算法设计，了解并熟练掌握了FIFO分支限界搜索算法和优先队列分支限界算法的使用，基本上完成了货物装载问题。输入数据后，快速的得到了本题的答案，也基本理解了算法设计的基本思