4.2.1程序流程图
图4-2优先队列限界法流程图
4.2.2 数据结构描述和算法
float bestw,w[100],bestx[100]; int n； Queue Q; struct QNode
第 11 页 共 16 页
{ 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(w[i]); s=s+w[i];}
if (s<=c1 or s<=c2) {print(“need only one ship”); return;} if (s>c1+c2) {print(“no solution”); return;} MaxLoading(c1); if (s-bestw <=c2);
{ print(“The first ship loading”, bestw,“chose:”); for(i=1;i<=n;i++)
if (bestx[i]=1) print(i,“,”);
print(“换行符 The second ship loading”, s-bestw,“chose”); for(i=1;i<=n;i++)
if (bestx[i]=0) print(i,”,”); }
else print(“no solution”); }
MaxLoading(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+ w[j]; while (true) // 搜索子集空间树
{ wt=Ew+w[i]; // 检查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,E ) ; // 下一个E-节点 if (E=0) // 层的尾部 { if (Empty(Q )) break;
add (Q, 0) ; // 层尾指针 Delete(Q,E) ; // 下一个E-结点
i++ ; // E-结点的层次 r=r-w[i]; } // E-结点中余下的重量 Ew=E->weight ; // 新的E-结点的重量
第 12 页 共 16 页
}
// 沿着从bestE到根的路径构造bestx[] for (j=n-1;j>0;j--)
{ bestx[j]=bestE->LChild; //从bool转换为int bestE=bestE->parent;} return bestw; }
4.3 测试结果与分析
图4.3 货物装载问题的解
由结果可以看出，当货箱的质量分别为12 14 16 20 25 时，两个货船的载重量分别为50,70.由此算法可以得到第一艘船可以达到满装 14 16 20，第二艘船可以装剩下的37。
第 13 页 共 16 页
第五章 结论
通过本次的算法设计，了解并熟练掌握了FIFO分支限界搜索算法和优先队列分支限界算法的使用，基本上完成了货物装载问题。输入数据后，快速的得到了本题的答案，也基本理解了算法设计的基本思想：
首先，对于一个算法设计例题，我们应该分析题目应该采取什么样的算法，也就是所谓的算法分析。比如本体采用的分支限界法中的FIFO分支限界和优先队列式分支限界。
其次，确定完成需要选用的算法，我们就要针对题目进行数据结构的分析，画出程序流程图，写出简单的算法。
最后，根据前面所写的算法，采用比较擅长的算法就行具体的实现。然后根据结果分析情况，加以修改，得到问题的最优解。
本题实现的语言采用的JAVA语言。也从横向比较了优先队列算法和FIFO算法的不同之处。加深了对他们的理解。与C、Ｃ＋＋ 相比，JAVA语言具有很好的封装性，灵活性，行不其他语言实现较为简单、易懂、明了。通过此次算法设计也深刻了解了FIFO分支限界搜索算法和优先队列分支限界算法的内容，对于搜索算法的应用有了很深的理解。从本次课程设计当中，也明白了一般解决问题的方法，受益匪浅。
第 14 页 共 16 页
参考文献
[1] 算法设计与分析（第二版） 吕国英 主编 [2] Java语言程序设计（第八版） 李娜 译
第 15 页 共 16 页
指导教师评语： 1、文档： a、内容： 不完整□ 完整 □ 详细 □ b、方案设计： 较差 □ 合理 □ 非常合理□ c、实现： 未实现□ 部分实现□ 全部实现□ d、文档格式： 不规范□ 基本规范□ 规范 □ 2、答辩： a、未能完全理解题目，答辩情况较差 □ b、部分理解题目，部分问题回答正确 □ c、理解题目较清楚，问题回答基本正确 □ d、理解题目透彻，问题回答流利 □ 文档成绩： ，占总成绩比例： 40% 答辩成绩： ，占总成绩比例： 60% 总 成 绩： 指导教师签字： 年 月 日 第 16 页 共 16 页