装载问题5种解决方案.doc

算法分析与设计算法分析与设计 2016/2017（2) 实验题目 装载问题5种解法 学生姓名 学生学号 学生班级 任课教师 提交日期2017 计算机科学与技术学目录一问题定义3二解决方案31优先队列式分支限界法求解31.1算法分析31。2代码31.3运行结果132队列式分支限界法求解132.1算法分析132.2代码142。3测试截图223回朔法迭代223.1算法分析223.2代码223。3测试截图264回朔法递归264.1算法分析264.2代码274.3测试截图315贪心算法315。1算法分析315.2代码315。3测试截图35II一问题定义有一批共有 n 个集装箱要装上两艘载重量分别为 c1 和 c2 的轮船,其中集装箱 i 的重量为 wi， 且重量之和小于（c1 + c2)。装载问题要求确定是否存在一个合理的装载方案可将这 n 个集装箱装上这两艘轮船。如果有，找出一种装载方案。二解决方案1优先队列式分支限界法求解1.1算法分析活结点x在优先队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和。优先队列中优先级最大的活结点成为下一个扩展结点。以结点x为根的子树中所有结点相应的路径的载重量不超过它的优先级。子集树中叶结点所相应的载重量与其优先级相同。在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解.此时可终止算法。1.2代码1。2-1/MaxHeap.htemplateclassTclassMaxHeappublic:MaxHeap(intMaxHeapSize=10）；MaxHeap（)deleteheap；intSize()constreturnCurrentSize；TMax()/查找if(CurrentSize=0)throwOutOfBounds(）；returnheap1;MaxHeapTInsert(constT&x);/增MaxHeapT&DeleteMax（Tx)；/删voidInitialize（Ta,intsize,intArraySize);private:intCurrentSize,MaxSize;T*heap;/elementarray；templateclassTMaxHeap：:MaxHeap（intMaxHeapSize）/Maxheapconstructor。MaxSize=MaxHeapSize；heap=newTMaxSize+1;CurrentSize=0；templateclassTMaxHeapMaxHeap:Insert（constT&x)/Insertxintothemaxheap.if(CurrentSize=MaxSize)cout”nospace!MaxHeapTMaxHeap：DeleteMax(Tx)/Setxtomaxelementanddeletemaxelementfromheap./checkifheapisemptyif（CurrentSize=0)cout”Emptyheap！”endl；returnthis;x=heap1;/删除最大元素/重整堆Ty=heapCurrentSize-;/取最后一个节点，从根开始重整/findplaceforystartingatrootinti=1,/currentnodeofheapci=2;/childofiwhile（ci=CurrentSize）/使ci指向i的两个孩子中较大者if(ciCurrentSize&heapciheapci+1)ci+；/y的值大于等于孩子节点吗？if(y=heapci)break；/是，i就是y的正确位置，退出/否,需要继续向下，重整堆heapi=heapci;/大于父节点的孩子节点上升i=ci;/向下一层,继续搜索正确位置ci=2；heapi=y;returnthis;templateclassTvoidMaxHeapT:：Initialize(Ta,intsize，intArraySize）/Initializemaxheaptoarraya.deleteheap；heap=a;CurrentSize=size;MaxSize=ArraySize;/从最后一个内部节点开始,一直到根，对每个子树进行堆重整for（inti=CurrentSize/2;i=1；i-）Ty=heapi；/子树根节点元素/findplacetoputyintc=2*i;/parentofcistarget/locationforywhile(c=CurrentSize）/heapcshouldbelargersiblingif（cCurrentSize&heapcheapc+1)c+；/canweputyinheapc/2？if(y=heapc）break;/yes/noheapc/2=heapc；/movechildupc=2;/movedownalevelheapc/2=y;1.22/6d32。cpp/装载问题优先队列式分支限界法求解#includestdafx。hincludeMaxHeap.h”includeusingnamespacestd；constintN=4；classbbnode;templateclassTypeclassHeapNodetemplatefriendvoidAddLiveNode(MaxHeapHeapNodeH，bbnode*E，Typewt,boolch，intlev);templatefriendTypeMaxLoading（Typew，Typec，intn,intbestx)；public：operatorType()constreturnuweight;private：bbnodeptr；/指向活节点在子集树中相应节点的指针Typeuweight;/活节点优先级（上界）intlevel；/活节点在子集树中所处的层序号;classbbnodetemplatefriendvoidAddLiveNode(MaxHeap&H,bbnode*E，Typewt,boolch，intlev）；templateclassTypefriendTypeMaxLoading(Typew,Typec,intn，intbestx)；friendclassAdjacencyGraph；private:bbnodeparent;/指向父节点的指针boolLChild；/左儿子节点标识;templateclassTypevoidAddLiveNode（MaxHeapH，bbnode*E，Typewt，boolch,intlev)；templateclassTypeTypeMaxLoading（Typew,Typec,intn，intbestx)；intmain（)floatc=70；floatw=0，20，10，26，15；/下标从1开始intxN+1；floatbestw；cout”轮船载重为：cendl;cout待装物品的重量分别为：”endl；for(inti=1；i=N；i+)coutwi；coutendl;bestw=MaxLoading(w，c，N，x)；cout”分支限界选择结果为:endl；for(inti=1;i=4;i+）coutxi”;coutendl;cout”最优装载重量为：bestwendl；return0;/将活节点加入到表示活节点优先队列的最大堆H中templateclassTypevoidAddLiveNode（MaxHeapHeapNode&H，bbnode*E，Typewt,boolch，intlev）bbnodeb=newbbnode;bparent=E;b-LChild=ch;HeapNodeN；N.uweight=wt；N。level=lev；N.ptr=b；H。Insert（N）；/优先队列式分支限界法，返回最优载重量，bestx返回最优解templateTypeMaxLoading(Typew,Typec,intn，intbestx）/定义最大的容量为1000MaxHeap0；j）rj=rj+1+wj+1；/初始化inti=1;/当前扩展节点所处的层bbnodeE=0；/当前扩展节点TypeEw=0；/扩展节点所相应的载重量/搜索子集空间树while（i!=n+1）/非叶子节点/检查当前扩展节点的儿子节点if（Ew+wi=c）AddLiveNode(H，E，Ew+wi+ri,true，i+1);/右儿子节点AddLiveNode（H，E，Ew+ri，false，i+1);/取下一扩展节点HeapNodeTypeN；H.DeleteMax(N）;/非空i=N.level；E=N。ptr；Ew=N.uweightri1；/构造当前最优解for（intj=n；j0;j）bestxj=ELChild；E=E-parent;returnEw;1.3运行结果2队列式分支限界法求解2.1算法分析在算法的循环体中，首先检测当前扩展结点的左儿子结点是否为可行结点.如果是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点队列中(右儿子结点一定是可行结点)。2个儿子结点都产生后，当前扩展结点被舍弃。活结点队列中的队首元素被取出作为当前扩展结点，由于队列中每一层结点之后都有一个尾部标记1,故在取队首元素时,活结点队列一定不空。当取出的元素是-1时，再判断当前队列是否为空。如果队列非空，则将尾部标记-1加入活结点队列，算法开始处理下一层的活结点。节点的左子树表示将此集装箱装上船，右子树表示不将此集装箱装上船。设bestw是当前最优解；ew是当前扩展结点所相应的重量；r是剩余集装箱的重量。则当ew+rbestw时，可将其右子树剪去,因为此时若要船装最多集装箱，就应该把此箱装上船。另外,为了确保右子树成功剪枝,应该在算法每一次进入左子树的时候更新bestw的值。为了在算法结束后能方便地构造出与最优值相应的最优解，算法必须存储相应子集树中从活结点到根结点的路径。为此目的，可在每个结点处设置指向其父结点的指针，并设置左、右儿子标志。找到最优值后,可以根据parent回溯到根节点，找到最优解.2.2代码22-1/Queue。hincludeiostreamusingnamespacestd;templateclassQueuepublic：Queue（intMaxQueueSize=50);Queue（）deletequeue；boolIsEmpty(）constreturnfront=rear;boolIsFull（）return(（rear+1）MaxSize=front）?1：0)；TTop(）const；TLast（）const;QueueAdd(constTx）；QueueT&AddLeft(constTx)；QueueQueueT：:Queue(intMaxQueueSize)MaxSize=MaxQueueSize+1;queue=newTMaxSize;front=rear=0;templateclassTTQueueT：Top（）constif(IsEmpty()）cout”queue：noelement,no!TQueueT:Last()constif(IsEmpty()）cout”queue:noelement”endl；return0;elsereturnqueuerear;templateclassTQueueT&QueueT：:Add（constTx）if(IsFull（)coutqueue:nomemory”QueueTQueueT：AddLeft(constT&x）if(IsFull(）)cout”queue:nomemory”endl;elsefront=(front+MaxSize1）MaxSize；queue(front+1）%MaxSize=x;return*this；templateQueueQueueT：Delete(Tx)if(IsEmpty（）coutqueue：noelement(delete)endl；elsefront=(front+1）MaxSize;x=queuefront;return*this；templatevoidQueueT:：Output(ostreamout）constfor（inti=rearMaxSize;i=(front+1）%MaxSize;i)outqueuei;template&x）x。Output(out）;returnout;2.22/6d31。cpp/装载问题队列式分支限界法求解#include”stdafx.h”includeQueue.h#includeusingnamespacestd;constintN=4;templatefriendvoidEnQueue（QueueQNodeType*&Q,Typewt,inti,intn，Typebestw，QNodeTypeE，QNodeTypebestE,intbestx，boolch)；templateclassTypefriendTypeMaxLoading（Typew,Typec,intn,intbestx);private：QNodeparent;/指向父节点的指针boolLChild;/左儿子标识Typeweight;/节点所相应的载重量;templateclassTypevoidEnQueue（QueueQ,Typewt，inti,intn，Typebestw,QNodeTypeE，QNodeTypeMaxLoading(Typew,Typec，intn，intbestx）；intmain()floatc=70;floatw=0,20，10，26，15;/下标从1开始intxN+1;floatbestw；cout”轮船载重为：cendl;cout待装物品的重量分别为：endl；for(inti=1；i=N；i+)coutwi”；coutendl；bestw=MaxLoading（w,c，N，x）；cout分支限界选择结果为：”endl；for（inti=1；i=4；i+)coutxi”；coutendl；cout”最优装载重量为：”bestwendl；return0；/将活节点加入到活节点队列Q中templateclassTypevoidEnQueue（QueueQNodeTypeQ,Typewt,inti,intn，Typebestw，QNode*E，QNode*bestE，intbestx，boolch）if(i=n）/可行叶节点if（wt=bestw）/当前最优装载重量bestE=E;bestxn=ch；return;/非叶节点QNode;bweight=wt；bparent=E;bLChild=ch;Q.Add（b)；templateclassTypeTypeMaxLoading（Typew，Typec，intn，intbestx）/队列式分支限界法,返回最优装载重量，bestx返回最优解/初始化QueueQNodeTypeQ；/活节点队列Q.Add(0)；/同层节点尾部标识inti=1;/当前扩展节点所处的层TypeEw=0,/扩展节点所相应的载重量bestw=0,/当前最优装载重量r=0;/剩余集装箱重量for（intj=2；j=n；j+)r+=wj；QNode*E=0，/当前扩展节点*bestE；/当前最优扩展节点/搜索子集空间树while(true)/检查左儿子节点Typewt=Ew+wi；if(wtLChild；bestE=bestE-parent；returnbestw；2。3测试截图3回朔法迭代3.1算法分析用回溯法解装载问题时，用子集树表示其解空间显然是最合适的。可行性约束条件重量之和小于(c1 + c2)可剪去不满足约束条件的子树用cw记当前的装载重量，即cw=(w1x1+w2x2+.+wjxj),当cwc1时,以节点Z为根的子树中所有节点都不满足约束条件,因而该子树中解均为不可行解，故可将该子树剪去。3。2代码includeiostreamusingnamespacestd;templateclassTypeTypeMaxLoading（Typew，Typec，intn，intbestx)；intmain()intn=3，m；intc=50,c2=50；intw4=0，10，40,40；intbestx4；m=MaxLoading（w,c,n,bestx);cout轮船的载重量分别为：”endl；cout”c（1）=”c”,c(2）=c2endl；cout待装集装箱重量分别为：”endl；cout”w（i）=”；for（inti=1;i=n;i+）coutwi”；coutendl；cout”回溯选择结果为：endl;cout”m（1）=”mendl;coutx(i）=;for(inti=1；i=n;i+)coutbestxi”；coutendl；intm2=0；for（intj=1;j=n；j+）m2=m2+wj*(1-bestxj）;cout”m(2）=”m2c2)cout”因为m(2)大于c(2),所以原问题无解！”endl；return0；templateclassTypeTypeMaxLoading(Typew