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

分岔和极限：货物装载问题课程名称： * * * * * * * * * *院系： * * * * * * * * * * * *学生名称： *学号： *专业班： * * * * * * * * * * * * * * *指导教师： *2013年12月27日16页共16页分岔和极限：货物装载问题摘要：在现实生活中，我们经常遇到货物装载问题，解决货物装载问题，获得利润最大化，以最少的费用获得更多的东西，是人们一直需要思考的问题。 在广泛的解决问题中，人们通常使用分支边界算法来解决这种问题。 分歧边界法由分歧战略和边界战略两部分组成。 分支边界法是一种用途非常广泛的算法，使用该算法的技术性强，问题解法因类型而异。 更具体地，这种算法被运行时，所有可能的解空间被划分成逐渐变小的子集(称为分支)，并且针对子集中的每个解值计算下界或上界(称为分界)。 各分支后，对于所有边界超过已知可行解值的子集，不再进行进一步的分支。 因此，不再考虑解的多个部分集合(即搜索树的多个节点)，搜索范围变窄。 更具体地，这种算法被运行时，所有可能的解空间被划分成逐渐变小的子集(称为分支)，并且针对子集中的每个解值计算下界或上界(称为分界)。 各分支后，对于所有边界超过已知可行解值的子集，不再进行进一步的分支。 因此，不再考虑解的多个部分集合(即搜索树的多个节点)，搜索范围变窄。 分支战略表现在探索广泛优先问题空间的战略上，极限战略为加快探索速度采用启发信息剪枝的战略。 在分支边界法中，经常采用分支搜索法，分支搜索法是在问题空间中尝试搜索的算法。 分支是使用宽度优先策略来依次搜索E-节点的所有分支，即所有相邻节点。 与回溯法一样，在生成的节点中，丢弃不满足制约条件的节点，将其馀节点放入活节点表中。 分支检索的算法中，经常使用FIFO检索和优先队列检索。 例题中采用了轮船装载的问题，这是非常经典的分支极限算法的例题，通过这个例子的学习，理解并把握分支极限货物装载的问题。关键词：分支边界法货物装载FIFO分支边界优先队列分支边界目录第一章绪论41.1分支边界算法的基本思想41.2常见的两个分支边界算法4第二章货物装载问题52.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分支边界算法的基本思想分歧边界法通常在广泛的范围内优先，或者以最小消费(最大利益)优先的方法来探索问题的解空间树。 在分支边界法中，每个活性节点只有一次成为扩展节点的机会。 当活节点成为扩展节点时，其所有子节点一次出现。 这些子节点中，引起不可执行解或导致非最佳解的子节点被废弃，剩馀的子节点注册在活节点表中。 然后，从活性节点表中取出节点作为当前的扩展节点，重复上述节点扩展过程。 该过程一直持续到找到必要的解或活节点表。1.2常见的两种分支边界算法队列表达式(FIFO )分支边界方法依据队列先进先出(FIFO )原则选择下一个节点作为扩展节点。 FIFO检索算法依赖“团队”建立基本数据结构。 最初，根节点是唯一的活动节点，并且根节点被排队。 从一对活节点中取出新节点，作为当前的扩展节点。 对于当前的扩展节点，首先从左到右生下其所有的儿子，在制约条件下进行检查，将满足制约函数的所有儿子追加到活性节点列中。 进而，从生存节点表中取出团队的开头节点作为当前的扩展节点。 优先队列式分支边界法根据优先队列中规定的优先级，选择优先级最高的节点作为当前的扩展节点。 优先级队列搜索器计算每个生存节点的优先级，基于这些优先级从当前生存节点表中选择优先级最高的节点作为扩展节点，将搜索推进到解空间树的最优解的分支，以便尽快找到最优解。第二章货物装载问题2.1问题的说明有2艘船和需要装运的n个集装箱，第一艘船的装载量为c1，第二艘船的装载量为c2，wi为集装箱I的重量，w1w2， wn=c1c2。 我想确认一下是否有办法把所有的集装箱装船。 如果有的话，我会找到那个方法。2.2问题分析让我们看一个例子。 如果n=3，c1=c2=50，w= 10，40，40 ，则可以在第一艘船上安装容器1，2，在第二艘船上安装容器3。 但是，如果w= 20，40，40 ，集装箱不能全部装船。 也许问题有解，也许没有解，也许有很多解。 两艘船的问题，w1 w2 w3 .wn-bestw=c2的话，有可能确定一个解。 否则问题就解决不了。 这类问题将成为第一艘船的最大装载问题。第三章优先行列式分支极限法解决货物装载问题3.1算法设计卸载问题的优先队列式分支边界法，用最大优先队列存储活性节点表。 存在节点x的优先级由装载量和剩馀容器的重量之和定义，其对应于从根节点至节点x的路径。 优先队列中优先级最高的活动节点成为下一个扩展节点。 优先队列的活性节点x的优先级为x.uweight。 对应于以节点x为根的子树的所有节点的路径的装载量不超过x.uweight。 子集树的中叶节点所对应的装载量与其优先级相同。 因此，优先矩阵分支边界法中，当一个叶节点成为当前的扩展节点时，可以断定与该叶节点对应的解是最佳解，并结束算法。 通过实验，了解了分歧边界法的基本思想。 掌握了优先队列式分支边界法的具体装载问题。 不需要编写实现最大堆的程序代码，因为可以使用java.util包下的优先级队列来代替算法的最大堆。基于优先队列式分支边界法的算法设计要点如下(1)节点扩展方式：不管其分支边界法如何，都需要活动的节点表。 优先队列的分支边界法将活性节点作为优先队列，优先选择优先队列中指定的节点中最高的下一个节点作为当前扩展节点。(2)节点优先级的决定：优先队列的节点优先级长度规定有关该节点的数值w，w一般表示以该节点为根的子树的枝干接近最佳解的程度。(3)优先队列组织：确定节点优先级后，按节点优先级排序，生成优先队列。 考虑到排序算法的时间复杂性高，检索算法一次仅扩展一个节点，在数据结构中进行排序符合此特征并且比较交换的次数最少。 此示例使用最大堆实现首选队列。3.2数据结构设计3.2.1程序的流程图图3-1优先队列限制方法流程图3.2.2数据结构的说明(1)输出解的方案，在搜索过程中也需要生成解构造树，其节点信息中包含指向父节点的指针和标识物的取舍选择(或者父节点的左右的孩子)。(2)堆节点包含节点优先级信息：节点所在分支的加载上界uweight； 堆无法表示节点的级别信息，只能存储在节点中(3)因为扩展节点不是按层次分类的，所以在计算节点所在分支的装载上限时，通过用数组变量r记录当前层次以下的最大重量，可以随时简单地使用各层次的节点的装载上限。3.2.3关键算法HeapNode H1000；结构bb节点 bbnode *parent； /父节点指针int LChild； 仅对于父节点左侧的孩子，值为1结构头节点 bbnode *ptr； /活性节点指针浮点构件； /活性节点的重量上限int level； 最大加载(浮点c，int n，int bestx )浮点r 100 、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 (最佳w 0； j- )bestxj=E-LChild； E=E-parent； 以下称为return Ew；以下称为addlivenode (浮点wt，int lev，bb节点* e，int ch ) bbnode *b=new bbnode；b-parent=E；b-LChild=ch；HeapNode N；N.uweight=wt；N.level=lev；N.ptr=b；插入(h，n )以下称为3.3测试结果和分析图3.2货物装载问题的解由图可知，当集装箱的个数为5时，最初的船的装载量为50，第二个船的装载量为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=2050，不需要检索该分支图4-1子集图4.2数据结构设计用FIFO分支搜索全部分支，记录搜索到的分支的最佳解，即使搜索到部分集合树也找到了问题的解。 要求最优解，就要求最优解，搜索叶节点。 因此，为了记录树的层次，如果层次是n 1，则搜索完整的叶节点并结束该算法。 与回溯算法不同，分支搜索中活着的节点的“层”需要标记跳跃，否则入队后无法识别节点所在的层。4.2.1程序的流程图图4-2优先队列限制方法流程图4.2.2数据结构的描述和算法浮动bestw、w100、bestx100；int n；Queue Q；结构节点浮点构件；QNode *parent；QNode LChild； 以下称为main () int c1，c2，n，s=0，I；输入(C1，c2，n )for(i=1； i=n； I ) input(wi )； s=s wi； 以下称为if (s=c1ors=C2 ) print ( needonlyoneship ) return； 以下称为if (sc1 c2) print(“no solution”) return； 以下称为最大加载(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 lo