分支限界法求装载问题_物联1301班_刘悦_08080112.doc
《分支限界法求装载问题_物联1301班_刘悦_08080112.doc》由会员分享,可在线阅读,更多相关《分支限界法求装载问题_物联1301班_刘悦_08080112.doc(23页珍藏版)》请在三一办公上搜索。
1、算法分析与设计实验报告第 X 次实验姓名学号班级时间地点 实验名称分支限界法求装载问题实验目的通过上机实验,掌握分支限界算法的思想,利用分支限界算法求装载问题并实现。实验原理活结点x在最优队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的总量之和。优先队列中优先级最大的活结点成为下一个扩展结点。优先队列中活结点x的优先级为x.uweight。以结点x为根的子树中所有结点相应的路径的载重量不超过x.uweight。子集树中叶结点相应载重量与其优先级一样。因此,一旦一个叶结点成为当前扩展结点,如此可以断言该叶结点所相应的解为即为最优解,终止算法。这里选用在搜索进程中保存当前
2、已构造出的局部解空间树,在算法确定课达到最优解的叶结点时,就可以在解空间树中从该叶结点开始向根结点回溯,构造出相应的最优解。实验步骤 算法开始创建一个最大堆,表示活结点优先队列。 算法第一个扩展结点是子集树中根结点。 开始子集树的根结点是扩展结点。循环产生当前扩展结点的左右儿子结点。 如果当前扩展结点的左儿子结点是可行结点,即它所相应的重量为超过轮船的载重量,如此将它参加到子集树的第i+1层上,并插入最大堆。 扩展结点的右儿子结点总是可行的,故直接插入子集树的最大堆中。 接着从最大堆中取出最大元素作为下一个扩展结点。 如果此时不存在下一个扩展结点,如此问题无可行解。 如果下一个扩展结点是叶结点
3、,即子集树中第n+1层结点,如此它相对应的可行解为最优解,算法完毕。关键代码/定义集装箱的个数 const int N = 4; /*= 定义HeapNode类来存储最大堆中顶点的信息。 =*/template class HeapNode template friend void AddLiveNode(MaxHeapHeapNode & H,bbnode *E,T wt,bool ch,int lev); template friend Ty MaxLoading(Ty w,Ty c,int n,int bestx); public: operator Type() constreturn
4、 uweight; private: bbnode *ptr; /指向活节点在子集树中相应节点的指针 Type uweight; /活节点优先级(上界) int level; /活节点在子集树中所处的层序号 ; /*=定义bbnode类来定义子集空间树中的结点类型。=*/class bbnode template friend void AddLiveNode(MaxHeapHeapNode & H,bbnode *E,Type wt,bool ch,int lev); template friend Type MaxLoading(Type w,Type c,int n,int bestx)
5、; friend class AdjacencyGraph; private: bbnode *parent; /指向父节点的指针 bool LChild; /左儿子节点标识 ; /*= AddLiveNode函数将新产生的活节点参加到子集树中,并将这个新结点插入到表示活结点优先队列的最大堆中。=*/template void AddLiveNode(MaxHeapHeapNode & H,bbnode *E,Type wt,bool ch,int lev) /子集树结点赋值 bbnode *b = new bbnode; b-parent = E; b-LChild = ch; HeapNo
6、de N; /最大堆结点赋值 N.uweight = wt; N.level = lev; N.ptr = b;/将结点N插入到最大堆中 H.Insert(N); /*=MaxLoading函数为使用优先队列求装载问题,返回最优装载重量,bestx返回最优解。 活结点x在最优队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的总量之和。优先队列中优先级最大的活结点成为下一个扩展结点。优先队列中活结点x的优先级为x.uweight。以结点x为根的子树中所有结点相应的路径的载重量不超过x.uweight。子集树中叶结点相应载重量与其优先级一样。因此,一旦一个叶结点成为当前扩展
7、结点,如此可以断言该叶结点所相应的解为即为最优解,终止算法。 =*/template Type MaxLoading(Type w,Type c,int n,int bestx) /定义最大的容量为1000 MaxHeapHeapNode H(1000); /定义剩余容量数组 Type *r = new Typen+1; rn = 0; for(int j=n-1; j0; j-) rj = rj+1 + wj+1; /初始化 int i = 1;/当前扩展节点所处的层 bbnode *E = 0;/当前扩展节点 Type Ew = 0; /扩展节点所相应的载重量 /搜索子集空间树 while
8、(i!=n+1)/非叶子节点 /检查当前扩展节点的儿子节点 if(Ew+wi=c) /将结点参加最大堆中 AddLiveNode(H,E,Ew+wi+ri,true,i+1); /右儿子节点 AddLiveNode(H,E,Ew+ri,false,i+1); /取下一扩展节点 HeapNode N; /从最大堆中取出最大值 H.DeleteMax(N); /赋值 i = N.level; E = N.ptr; Ew = N.uweight - ri-1; /构造当前最优解 for(int j=n; j0; j-) bestxj = E-LChild; E = E-parent; return
9、Ew; 测试结果1. 当所有物品无法装入两艘轮船时结果如下所示:输出时间。输出是否可以将集装箱全部装上两艘轮船。输出所有装上第1艘轮船的集装箱的重量。1代表对应集装箱装上轮船,0代表对应集装箱不装上轮船输出待装上轮船的集装箱的重量。输出第2艘船的载重量输出第1艘船的载重量没有装入第1艘轮船的集装箱的重量为10,这里第2艘轮船的载重量为8,小于10,所以无法将剩余集装箱装上第2艘轮船,所以不可以将集装箱全部装入两艘轮船。2. 当所有物品可以装入两艘轮船时结果如下所示:没有装入第1艘轮船的集装箱的重量为10,这里第2艘轮船的载重量为80,大于10,所以可以将剩余集装箱装上第2艘轮船,所以可以将集装
10、箱全部装入两艘轮船。使用分支限界法求装在问题时间很短,可以看到算法的性质很好。实验心得 与旅行售货员问题比拟起来,这个装载问题要好理解很多,因为这个算法的解空间是子集树,而不是排列树,与0-1背包问题非常类似,所以很多问题的求解都是相似的,弄懂一个问题,会编写其中一个问题的代码,其他问题也就迎刃而解了。分支限界法的算法思想也不算非常难。但是我认为分支限界法有一个不好的地方,就是需要另外编写代码来实现最大最小堆,这个代码的编写我感觉是非常繁琐的,稍不小心马虎了,堆得实现就会出现问题。不过还好,编写了这么多的分支界限法的代码,可以通用堆的实现,只要将其定义为.h头文件格式就可以了。 到这里其实就做
11、完了所有的算法设计与分析课程的实验。刚开始分治法的实验的时候还感觉蛮轻松的。但是越到后面感觉越难。要想当年,我们数据结构课程,写Dijkstra算法,与最大最小堆有关的算法的时候,三个人一组都是勉勉强强才能搞定。到了现在,一个代码,自己也可以敲出来,虽然中间还是会遇到很多的问题,但是还好坚持一下就都能解决了。果然一个算法还是要反复学习的,每次学习都会有不同的感受,每多学习一次,就能理解得更加透彻。这也说明,算法分析与设计这门的学习还是很有用处的,使我对算法的掌握更进一步。但是这算法分析与设计课程学习的算法比数据结构课程学习的算法要深入很多,要对一些算法完全掌握,还需要我平时多下功夫。 编写这个
12、代码,主要是为了熟悉最优装载算法的不同实现,就我自己来说,我还是更加偏爱贪心算法,可是贪心算法,因为贪心算法的实现真的是非常非常的简单。回溯法和分支限界法比贪心算法要难理解一点,但是好好研究一下,也是可以看懂的。我觉得算法课程的一大难点就是,算法思想都懂,但是不会实现具体问题。这也告诫我,在平时的学习中,需要多进展实践,在实践中掌握知识。 通过这次实验,编写了分支限界法求解装载问题的代码,使我对分支限界法的思想更加熟悉,对装载问题的问题描述与解题思路更加熟悉。相信在以后的学习工作中一定可以熟练使用分支限界法,可以使用多种方法求解装载问题。实验得分助教签名附录:完整代码#include MaxH
13、eap.h #include #include#include#include#include using namespace std; /定义集装箱的个数 const int N = 4; class bbnode; /*= 定义HeapNode类来存储最大堆中顶点的信息。 =*/ template class HeapNode template friend void AddLiveNode(MaxHeapHeapNode & H,bbnode *E,T wt,bool ch,int lev); template friend Ty MaxLoading(Ty w,Ty c,int n,i
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 分支 限界 装载 问题 物联 1301 刘悦 _08080112
链接地址:https://www.31ppt.com/p-1131586.html