分支与限界货物装载问题资料

《分支与限界货物装载问题资料》由会员分享，可在线阅读，更多相关《分支与限界货物装载问题资料（17页珍藏版）》请在装配图网上搜索。

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

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

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

4、 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+.+w*=c1+c2。希望确定是否有一种 可能将所有货箱全部装船的方法。若有的话，找出该方法。

7、2.2问题分析先看一个实例，当n=3,c1=c2=50,w=10,40,40时，可将货箱1,2装到第一 艘船上，货箱3装到第二艘船上。但如果w=20,40,40,则无法将货箱全部装船。 有此可知问题可能有解，可能无解，也可能多解。虽然是关于两艘船的问题，若 w1+w2+w3+.wn-bestw 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 (bestwEw+wi

8、) bestw=Ew+wi;if(bestwO;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貝C耳OHE. . . QL.凶*恭DB.圜& -x g.鉴画图|当貝y EranchLiriii tFIFOS&sr e

9、lk 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,第二 艘船的载重量为70时，每个货箱的质量分别是12,14,16,20,20，得到如下图的 结果。第四章 基于队列式(FIFO)分支限界法解决货物装载问题4.1算法设计将此问题转化为一艘船的最优化问题

10、，问题的解空间为一个子集树。也就是算法要考虑的所有物品的取、舍情况的组合，n个物品的取舍组合共2的N次 个分支，搜索子集树是NP-复杂问题。如下图所示，xi为1表示选取第i件物品， xi为0表示不选取第i件物品。搜索结点3,时 可以确定它不必被扩充为活结 点；因为扩展结点1后，就知道最大装载量不会小于 50；而扩展节点3时，发 现此分支的“装载上界”为 w2+w3=2050无需搜索此分支，节点3不必入队。图4-1 子集图4.2数据结构设计用FIFO分支搜索所有的分支，并记录已搜索分支的最优解，搜索完子集树 也就找到出了问题的解。要想求出最优解，必须搜素出最优解，必须搜索到叶节 点。所以要记录树

11、的层次，当层次为n+1时，搜索完全部叶节点，算法结束。不 同于回溯算法，分支搜索过程中活节点的“层”是需要标志飞，否则在入队后就 无法识别节点所在的层。421程序流程图呈tj l.T 二二图4-2优先队列限界法流程图4.2.2数据结构描述和算法float bestw,w100,bestx100; int n;Queue Q;struct QNode float weight;QNode *pare nt;QNode 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

12、 (s=c1 or sc1+c2)print( no solution ” );return;MaxLoadi ng(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;iweight=0; E-pare nt =n ull; E-Lchild=0; add (Q,E); be

13、stw=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 (wtbestw) bestw=wt;AddLiveNode(wt,i, E ,1);if (Ew+rbestw)/ 检查右孩子AddLiveNode(Ew,i,E,0);Delete (Q,E ) ; / 下一个 E-节点if (E=0)/层的尾部 if (Empty(Q ) add (Q, 0); Delete(Q,E); i+ ;r=r-wi; Ew=E

14、-weight ;break;/层尾指针/下一个E-结点/ E-结点的层次/ E-结点中余下的重量/新的E-结点的重量/沿着从bestE到根的路径构造bestxfor (j=n-1;jO;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

15、14 16 20 25时，两个货船的载 重量分别为50,70.由此算法可以得到第一艘船可以达到满装 14 16 20，第二 艘船可以装剩下的37。第五章结论通过本次的算法设计，了解并熟练掌握了 FIFO分支限界搜索算法和优先队 列分支限界算法的使用，基本上完成了货物装载问题。输入数据后，快速的得到 了本题的答案，也基本理解了算法设计的基本思想：首先，对于一个算法设计例题，我们应该分析题目应该采取什么样的算法， 也就是所谓的算法分析。比如本体采用的分支限界法中的FIFO分支限界和优先队列式分支限界。其次，确定完成需要选用的算法，我们就要针对题目进行数据结构的分析，画出程序流程图，写出简单的算法。

16、最后，根据前面所写的算法，采用比较擅长的算法就行具体的实现。 然后根 据结果分析情况，加以修改，得到问题的最优解。本题实现的语言采用的JAVA语言。也从横向比较了优先队列算法和 FIFO 算法的不同之处。加深了对他们的理解。与 C、C + + 相比，JAVA语言具有很 好的封装性，灵活性，行不其他语言实现较为简单、易懂、明了。通过此次算法 设计也深刻了解了 FIFO分支限界搜索算法和优先队列分支限界算法的内容，对 于搜索算法的应用有了很深的理解。 从本次课程设计当中，也明白了一般解决问 题的方法，受益匪浅。参考文献1 算法设计与分析（第二版） 吕国英 主编2 Java 语言程序设计（第八版） 李娜 译指导教师评语:1、文档:a、内容:不完整口完整口详细口b、方案设计：较差 口合理口非常合理口c、实现：未实现口部分实现口全部实现口d、文档格式：不规范口基本规范口规范口2、答辩：a、未能完全理解题目，答辩情况较差口b、部分理解题目，部分问题回答正确口c、理解题目较清楚，问题回答基本正确口d 、理解题目透彻，问题回答流利口文档成绩：，占总成绩比例：40%答辩成绩： ，占总成绩比例：60%总成绩：指导教师签字：年 月 日