第三章 优先队列式分支限界法解决货物装载问题
3.1 算法设计
解装载问题的优先队列式分支限界法用最大优先队列存储活结点表。活结点x在优先队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和。优先队列中优先级最大的活结点成为下一个扩展结点。优先队列中活结点x的优先级为x.uweight。以结点x为根的子树中所有结点相应的路径的载重量不超过x.uweight。子集树中叶结点所相应的载重量与其优先级相同。因此在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解，此时终止算法。通过实验，了解了分支限界法的基本思想。掌握了利用优先队列式分支限界法实现具体的装载问题。由于利用java.util包下的PriorityQueue代替算法中的最大堆，免去了编写实现最大堆的程序代码。
优先队列式分支限界法进行算法设计的要点如下：
（1）结点扩展方式：无论是那种分支限界法，需要有一张活的结点表。优先队列的分支限界法将活结点组成一个优先队列，并按优先队列中规定的结点优先选取最高的下一个结点成为当前扩展结点。
（2）结点优先级确定：优先队列中的结点优先级长规定一个与该节点相关的数值w,w一般表示以该节点为根的子树的分支接近最优解的程度。
（3）优先队列组织：结点优先级确定后，按结点优先级进行排序，就生成了优先队列。排序算法的时间复杂度较高，考虑到搜索算法每次只扩展一个结点，数据结构中堆排序，适合这一特点且比较交换的次数最少。此例采用最大堆来实现优先队列。
第 6 页 共 16 页
3.2 数据结构设计
3.2.1程序流程图
图3-1优先队列限界法流程图
3.2.2 数据结构描述
（1）要输出解的方案，在搜索过程中仍需要生成解结构树，其结点信息包
第 7 页 共 16 页
括指向父结点的指针和标识物品取舍（或是父结点的左、右孩子）。
（2）堆结点包括结点优先级信息：结点所在分支的装载上界uweight；堆中无法体现结点的层次信息（level），只能存储在结点中；
（3）由于扩展结点不是按层进行的，计算结点所在分支的装载上界时，要用数组变量r记录当前层以下的最大重量，这样可随时方便使用各层结点的装载上界。
3.2.3 重要算法
HeapNode H[1000]; struct bbnode
{ bbnode *parent; // 父结点指针
int LChild; }; //当且仅当是父结点的左孩子时，取值为1 struct HeapNode
{ bbnode *ptr; // 活结点指针
float uweight; // 活结点的重量上限
int level; } ;
MaxLoading(float c, int n, int bestx[]) { float r[100],Ew,bestw=0; r[n]=0;
for (int j=n-1; j > 0; j--) r[j]=r[j+1] + w[j+1];
int i = 1; bbnode *E = 0; Ew = 0; // 搜索子集空间树 while (i != n+1) // 不在叶子上 { if (Ew+w[i]<=c) // 可行的左孩子 { AddLiveNode(E,Ew+w[i]+r[i],1,i+1); } if (bestw if(bestw DeleteMax(H,E);i=N.level;E=N.ptr; Ew=N.uweight-r[i-1]; } for (int j=n;j>0;j--) {bestx[j] = E->LChild; E = E->parent;} return Ew; } AddLiveNode(float wt, int lev,bbnode *E, int ch) { bbnode *b=new bbnode; b->parent=E; b->LChild=ch; HeapNode N; N.uweight=wt; N.level=lev; N.ptr=b; Insert(H,N) ; 第 8 页 共 16 页 } 3.3 测试结果与分析 图3.2 货物装载问题的解 由图可以看出，当输入货箱的个数为5时，第一艘船的载重量为50，第二艘船的载重量为70时，每个货箱的质量分别是12,14,16,20,20，得到如下图的结果。 第 9 页 共 16 页 第四章 基于队列式(FIFO)分支限界法解决货物装载问题 4.1 算法设计 将此问题转化为一艘船的最优化问题，问题的解空间为一个子集树。也就是算法要考虑的所有物品的取、舍情况的组合，n个物品的取舍组合共2的N次个分支，搜索子集树是NP-复杂问题。如下图所示，xi为1表示选取第i件物品，xi 为0表示不选取第i件物品。搜索结点3,时 可以确定它不必被扩充为活结点；因为扩展结点1后，就知道最大装载量不会小于50；而扩展节点3时，发现此分支的“装载上界”为w2+w3=20<50,无需搜索此分支，节点3不必入队。 图 4-1 子集图 4.2 数据结构设计 用FIFO分支搜索所有的分支，并记录已搜索分支的最优解，搜索完子集树也就找到出了问题的解。要想求出最优解，必须搜素出最优解，必须搜索到叶节点。所以要记录树的层次，当层次为n+1时，搜索完全部叶节点，算法结束。不同于回溯算法，分支搜索过程中活节点的“层”是需要标志飞，否则在入队后就无法识别节点所在的层。 第 10 页 共 16 页