分支限界法求装载问题_物联1301班_刘悦_201308080112

《分支限界法求装载问题_物联1301班_刘悦_201308080112》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、标准文案算法分析与设计实验报告第X次实验大全标准文案姓名刘悦学号201308080112班级物联1301班时间12.26上午地点工训楼C栋309实验名称分支限界法求装载问题实验目的通过上机实验，掌握分支限界算法的思想，利用分支限界算法求装载问题并实现。实验原理活结点x在最优队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的总量之和。优先队列中优先级最大的活结点成为下一个扩展结点。优先队列中活结点x的优先级为x.uweight。以结点x为根的子树中所有结点相应的路径的载重量不超过x.uweight。子集树中叶结点相应载重量与其优

2、先级相同。因此，一旦一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解为即为最优解，终止算法。这里选用在搜索进程中保存当前已构造出的部分解空间树，在算法确定课达到最优解的叶结点时，就可以在解空间树中从该叶结点开始向根结点回溯，构造出相应的最优解。实验步骤①算法开始创建一个最大堆，表示活结点优先队列。②算法第一个扩展结点是子集树中根结点。③开始子集树的根结点是扩展结点。循环产生当前扩展结点的左右儿子结点。④如果当前扩展结点的左儿子结点是可行结点，即它所相应的重量为超过轮船的载重量，则将它加入到子集树的第i+1层上，并插入最大堆。⑤扩展结点的右儿子

3、结点总是可行的，故直接插入子集树的最大堆中。⑥接着从最大堆中取出最大元素作为下一个扩展结点。⑦如果此时不存在下一个扩展结点，则问题无可行解。⑧如果下一个扩展结点是叶结点，即子集树中第n+1层结点，则它相对应的可行解为最优解，算法结束。大全标准文案关键代码//定义集装箱的个数constintN=4;/*=================================================================定义HeapNode类来存储最大堆中顶点的信息。======================================

4、===========================*/templateclassHeapNode{templatefriendvoidAddLiveNode(MaxHeap>&H,bbnode*E,Twt,boolch,intlev);templatefriendTyMaxLoading(Tyw[],Tyc,intn,intbestx[]);public:operatorType()const{returnuweight;}private:bbnode*ptr;//指

5、向活节点在子集树中相应节点的指针Typeuweight;//活节点优先级(上界)intlevel;//活节点在子集树中所处的层序号};/*=================================================================定义bbnode类来定义子集空间树中的结点类型。=================================================================*/大全标准文案classbbnode{templatefriendvoidAddLiv

6、eNode(MaxHeap>&H,bbnode*E,Typewt,boolch,intlev);templatefriendTypeMaxLoading(Typew[],Typec,intn,intbestx[]);friendclassAdjacencyGraph;private:bbnode*parent;//指向父节点的指针boolLChild;//左儿子节点标识};/*==============================================================

7、===AddLiveNode函数将新产生的活节点加入到子集树中,并将这个新结点插入到表示活结点优先队列的最大堆中。=================================================================*/templatevoidAddLiveNode(MaxHeap>&H,bbnode*E,Typewt,boolch,intlev){//子集树结点赋值bbnode*b=newbbnode;b->parent=E;b->LChild=ch;HeapNode<

8、Type>N;大全标准文案//最大堆结点赋值N.uweight=wt;N.level=lev;N.ptr=b