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

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

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

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

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

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

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

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

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

9、结点表。优先队列的分支限界法将活结点组成一个优先队列，并按优先队列中规定的结点优 先选取最高的下一个结点成为当前扩展结点。(2) 结点优先级确定：优先队列中的结点优先级长规定一个与该节点相关 的数值w,w 一般表示以该节点为根的子树的分支接近最优解的程度。(3) 优先队列组织：结点优先级确定后，按结点优先级进行排序，就生成 了优先队列。排序算法的时间复杂度较高，考虑到搜索算法每次只扩展一个结点， 数据结构中堆排序，适合这一特点且比较交换的次数最少。此例采用最大堆来实 现优先队列。3.2数据结构设计程序流程图创建-卒飙駅t prioriiyQueiM笄虫侧牝j-nr j = rj + l + w

10、j41bastx j - E . Lchild E = E - parent; j+否i=卫识)count = o 1=1iddLivIJode iW,E”wwk - v il ;k+ + ; bestk li - false;if+Eu+w*1T+r （1,truerF鼻丹i+lHaddLivNods（HFE 厂UJt木乐Sih2i木氐此JEw+r i false i+1）;*F咨崎2卒社程同上r图3-1优先队列限界法流程图数据结构描述(1) 要输出解的方案，在搜索过程中仍需要生成解结构树，其结点信息包括指向父结点的指针和标识物品取舍（或是父结点的左、右孩子）。（2） 堆结点包括结点优先级信

11、息：结点所在分支的装载上界uweight ;堆 中无法体现结点的层次信息（level ），只能存储在结点中；（3）由于扩展结点不是按层进行的，计算结点所在分支的装载上界时，要 用数组变量r记录当前层以下的最大重量，这样可随时方便使用各层结点的装载 上界。重要算法HeapNode H1000;struct bbnode bbnode *parent;/ 父结点指针int LChild; ;/当且仅当是父结点的左孩子时，取值为 1struct HeapNodebbnode *ptr;/活结点指针float uweight;/活结点的重量上限int level; ;MaxLoadi ng(float

12、 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); if (bestw<Ew+wi) bestw=Ew+wi;if(bestw<Ew+ri) AddLiveNode(E,Ew+ri,0,i+1); Delet

13、eMax(H,E);i=N.level;E=N.ptr; Ew=N.uweight-ri-1;for (int j=n ;j>O;j_)bestxj = E->LChild; E = E->pare nt;return Ew;AddLiveNode(float wt, in t lev,bb node *E, i nt ch)bbnode *b=new bbno de;b->pare nt=E;b->LChild=ch;HeapNode N;N.uweight=wt;N.level=lev;N.ptr=b;In sert(H,N);3.3测试结果与分析牡FJ為D貝

14、C耳OHE. . . QL.凶*恭DB.圜& -x g.鉴画图|当貝y <l&rmi nat*i> EranchLiriii tFIFOS&sr elk Java AppLicalion B： VprflgraiiVjivaVjreTVbLrkVj ivaw. eue (2013-1 分支限界FIFO算袪：输入货箱的亍數：5输入第一艘货船的載重量:SO输入第二艘货船的载重量：70输入各个赏箱的质量：124 6 o o h h1 1 2 2 br TO-23图3.2货物装载问题的解由图可以看出，当输入货箱的个数为 5时，第一艘船的载重量为50,第二 艘船的载重

15、量为70时，每个货箱的质量分别是12,14,16,20,20，得到如下图的 结果。第四章 基于队列式(FIFO)分支限界法解决货物装载问题4.1算法设计将此问题转化为一艘船的最优化问题，问题的解空间为一个子集树。也就是算法要考虑的所有物品的取、舍情况的组合，n个物品的取舍组合共2的N次 个分支，搜索子集树是NP-复杂问题。如下图所示，xi为1表示选取第i件物品， xi为0表示不选取第i件物品。搜索结点3,时 可以确定它不必被扩充为活结 点；因为扩展结点1后，就知道最大装载量不会小于 50；而扩展节点3时，发 现此分支的“装载上界”为 w2+w3=20<50无需搜索此分支，节点3不必入队。

16、图4-1 子集图4.2数据结构设计用FIFO分支搜索所有的分支，并记录已搜索分支的最优解，搜索完子集树 也就找到出了问题的解。要想求出最优解，必须搜素出最优解，必须搜索到叶节 点。所以要记录树的层次，当层次为n+1时，搜索完全部叶节点，算法结束。不 同于回溯算法，分支搜索过程中活节点的“层”是需要标志飞，否则在入队后就 无法识别节点所在的层。421程序流程图呈tj l.T 二二图4-2优先队列限界法流程图数据结构描述和算法float bestw,w100,bestx100; int n;Queue Q;struct QNode float weight;QNode *pare nt;QNode

17、 LChild;mai n() int c1,c2, n, s=0,i;in put(c1,c2, n);for(i=1;i<=n ;i+) in put(wi); s=s+wi;if (s<=c1 or s<=c2) print(“ need only one ship ” ); return;if (s>c1+c2)print( "no solution ” );return;MaxLoadi ng(c1);if (s-bestw <=c2); print( “The first ship loading ” , bestw, “ chose:” )

18、;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 ” )；MaxLoadi ng(i nt c) Qnode *E;/活结点队列int i = 1;E-结点的层E= new QNode; add (Q,0) ;0 代表分层标记E->weight=0; E-

19、>pare nt =n ull; 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)可行的左孩子 if (wt>bestw) bestw=wt;AddLiveNode(wt,i, E ,1);if (Ew+r>bestw)/ 检查右孩子AddLiveNode(Ew,i,E,0);Delete (Q,

20、E ) ; / 下一个 E-节点if (E=0)/层的尾部 if (Empty(Q ) add (Q, 0); Delete(Q,E); i+ ;r=r-wi; Ew=E->weight ;break;/层尾指针/下一个E-结点/ E-结点的层次/ E-结点中余下的重量/新的E-结点的重量/沿着从bestE到根的路径构造bestxfor (j=n-1;j>O;j-) bestxj=bestE->LChild; /从 bool 转换为 int bestE=bestE->pare nt;retur n bestw;4.3测试结果与分析请输入货箱的数呈：E诸輸入货箱的质呈：1214162025谙输入两亍货船的载重垦:5070|first: 50可装重为：14 16 2 0second:37可装重为:12 25图4.3货物装载问题的解由结果可以看出，当货箱的质量分别为 12 14 16 20 25时，两个货船的载 重量分别为50,70.由此算法可以得到第一艘船可以达到满装 14 16 20，第二 艘船可以装剩下的37。第五章结论通过本次的算法设计，了解并熟练掌握了 FIFO分支限界搜索算法和优先队 列分支限界算法的使