装载问题5种解决方案

《装载问题5种解决方案》由会员分享，可在线阅读，更多相关《装载问题5种解决方案（35页珍藏版）》请在装配图网上搜索。

1、算法分析与设计 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测试截图3535 / 35文档可自由编辑打印一问题定义有一批共有 n 个集装箱要装上两艘

2、载重量分别为 c1 和 c2 的轮船，其中集装箱 i 的重量为 wi, 且重量之和小于(c1 + c2)。装载问题要求确定是否存在一个合理的装载方案可将这 n 个集装箱装上这两艘轮船。如果有，找出一种装载方案。二解决方案1优先队列式分支限界法求解1.1算法分析活结点x在优先队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和。优先队列中优先级最大的活结点成为下一个扩展结点。以结点x为根的子树中所有结点相应的路径的载重量不超过它的优先级。子集树中叶结点所相应的载重量与其优先级相同。在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的

3、解即为最优解。此时可终止算法。1.2代码1.2-1/MaxHeap.htemplateclassMaxHeappublic:MaxHeap(intMaxHeapSize=10);MaxHeap()deleteheap;intSize()constreturnCurrentSize;TMax()/查找if(CurrentSize=0)throwOutOfBounds();returnheap1;MaxHeap&Insert(constT&x);/增MaxHeap&DeleteMax(T&x);/删voidInitialize(Ta,intsize,intArraySize);private:in

4、tCurrentSize,MaxSize;T*heap;/elementarray;templateMaxHeap:MaxHeap(intMaxHeapSize)/Maxheapconstructor.MaxSize=MaxHeapSize;heap=newTMaxSize+1;CurrentSize=0;templateMaxHeap&MaxHeap:Insert(constT&x)/Insertxintothemaxheap.if(CurrentSize=MaxSize)coutnospace!heapi/2)/i不是根节点，且其值大于父节点的值，需要继续调整heapi=heapi/2;/

5、父节点下降i/=2;/继续向上，搜寻正确位置heapi=x;return*this;templateMaxHeap&MaxHeap:DeleteMax(T&x)/Setxtomaxelementanddeletemaxelementfromheap./checkifheapisemptyif(CurrentSize=0)coutEmptyheap!endl;return*this;x=heap1;/删除最大元素/重整堆Ty=heapCurrentSize-;/取最后一个节点，从根开始重整/findplaceforystartingatrootinti=1,/currentnodeofheapc

6、i=2;/childofiwhile(ci=CurrentSize)/使ci指向i的两个孩子中较大者if(ciCurrentSize&heapci=heapci)break;/是，i就是y的正确位置，退出/否，需要继续向下，重整堆heapi=heapci;/大于父节点的孩子节点上升i=ci;/向下一层，继续搜索正确位置ci*=2;heapi=y;return*this;templatevoidMaxHeap:Initialize(Ta,intsize,intArraySize)/Initializemaxheaptoarraya.deleteheap;heap=a;CurrentSize=si

7、ze;MaxSize=ArraySize;/从最后一个内部节点开始，一直到根，对每个子树进行堆重整for(inti=CurrentSize/2;i=1;i-)Ty=heapi;/子树根节点元素/findplacetoputyintc=2*i;/parentofcistarget/locationforywhile(c=CurrentSize)/heapcshouldbelargersiblingif(cCurrentSize&heapc=heapc)break;/yes/noheapc/2=heapc;/movechildupc*=2;/movedownalevelheapc/2=y;1.2-

8、2/6d3-2.cpp/装载问题优先队列式分支限界法求解#includestdafx.h#includeMaxHeap.h#includeusingnamespacestd;constintN=4;classbbnode;templateclassHeapNodetemplatefriendvoidAddLiveNode(MaxHeapHeapNode&H,bbnode*E,Typewt,boolch,intlev);templatefriendTypeMaxLoading(Typew,Typec,intn,intbestx);public:operatorType()constreturnu

9、weight;private:bbnode*ptr;/指向活节点在子集树中相应节点的指针Typeuweight;/活节点优先级(上界)intlevel;/活节点在子集树中所处的层序号;classbbnodetemplatefriendvoidAddLiveNode(MaxHeapHeapNode&H,bbnode*E,Typewt,boolch,intlev);templatefriendTypeMaxLoading(Typew,Typec,intn,intbestx);friendclassAdjacencyGraph;private:bbnode*parent;/指向父节点的指针boolL

10、Child;/左儿子节点标识;templatevoidAddLiveNode(MaxHeapHeapNode&H,bbnode*E,Typewt,boolch,intlev);templateTypeMaxLoading(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);

11、cout分支限界选择结果为:endl;for(inti=1;i=4;i+)coutxi;coutendl;cout最优装载重量为：bestwendl;return0;/将活节点加入到表示活节点优先队列的最大堆H中templatevoidAddLiveNode(MaxHeapHeapNode&H,bbnode*E,Typewt,boolch,intlev)bbnode*b=newbbnode;b-parent=E;b-LChild=ch;HeapNodeN;N.uweight=wt;N.level=lev;N.ptr=b;H.Insert(N);/优先队列式分支限界法，返回最优载重量，bestx

12、返回最优解templateTypeMaxLoading(Typew,Typec,intn,intbestx)/定义最大的容量为1000MaxHeapHeapNodeH(1000);/定义剩余容量数组Type*r=newTypen+1;rn=0;for(intj=n-1;j0;j-)rj=rj+1+wj+1;/初始化inti=1;/当前扩展节点所处的层bbnode*E=0;/当前扩展节点TypeEw=0;/扩展节点所相应的载重量/搜索子集空间树while(i!=n+1)/非叶子节点/检查当前扩展节点的儿子节点if(Ew+wi=c)AddLiveNode(H,E,Ew+wi+ri,true,i+1

13、);/右儿子节点AddLiveNode(H,E,Ew+ri,false,i+1);/取下一扩展节点HeapNodeN;H.DeleteMax(N);/非空i=N.level;E=N.ptr;Ew=N.uweight-ri-1;/构造当前最优解for(intj=n;j0;j-)bestxj=E-LChild;E=E-parent;returnEw;1.3运行结果2队列式分支限界法求解2.1算法分析在算法的循环体中，首先检测当前扩展结点的左儿子结点是否为可行结点。如果是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点队列中(右儿子结点一定是可行结点)。2个儿子结点都产生后，当前扩展结点被舍

14、弃。活结点队列中的队首元素被取出作为当前扩展结点，由于队列中每一层结点之后都有一个尾部标记-1，故在取队首元素时，活结点队列一定不空。当取出的元素是-1时，再判断当前队列是否为空。如果队列非空，则将尾部标记-1加入活结点队列，算法开始处理下一层的活结点。节点的左子树表示将此集装箱装上船，右子树表示不将此集装箱装上船。设bestw是当前最优解；ew是当前扩展结点所相应的重量；r是剩余集装箱的重量。则当ew+rbestw时，可将其右子树剪去，因为此时若要船装最多集装箱，就应该把此箱装上船。另外，为了确保右子树成功剪枝，应该在算法每一次进入左子树的时候更新bestw的值。为了在算法结束后能方便地构造

15、出与最优值相应的最优解，算法必须存储相应子集树中从活结点到根结点的路径。为此目的，可在每个结点处设置指向其父结点的指针，并设置左、右儿子标志。找到最优值后，可以根据parent回溯到根节点，找到最优解。2.2代码22-1/Queue.h#includeusingnamespacestd;templateclassQueuepublic:Queue(intMaxQueueSize=50);Queue()deletequeue;boolIsEmpty()constreturnfront=rear;boolIsFull()return(rear+1)%MaxSize=front)?1:0);TTop

16、()const;TLast()const;Queue&Add(constT&x);Queue&AddLeft(constT&x);Queue&Delete(T&x);voidOutput(ostream&out)const;intLength()return(rear-front);private:intfront;intrear;intMaxSize;T*queue;templateQueue:Queue(intMaxQueueSize)MaxSize=MaxQueueSize+1;queue=newTMaxSize;front=rear=0;templateTQueue:Top()cons

17、tif(IsEmpty()coutqueue:noelement,no!endl;return0;elsereturnqueue(front+1)%MaxSize;templateTQueue:Last()constif(IsEmpty()coutqueue:noelementendl;return0;elsereturnqueuerear;templateQueue&Queue:Add(constT&x)if(IsFull()coutqueue:nomemoryendl;elserear=(rear+1)%MaxSize;queuerear=x;return*this;templateQue

18、ue&Queue:AddLeft(constT&x)if(IsFull()coutqueue:nomemoryendl;elsefront=(front+MaxSize-1)%MaxSize;queue(front+1)%MaxSize=x;return*this;templateQueue&Queue:Delete(T&x)if(IsEmpty()coutqueue:noelement(delete)endl;elsefront=(front+1)%MaxSize;x=queuefront;return*this;templatevoidQueue:Output(ostream&out)co

19、nstfor(inti=rear%MaxSize;i=(front+1)%MaxSize;i-)outqueuei;templateostream&operator(ostream&out,constQueue&x)x.Output(out);returnout;2.2-2/6d3-1.cpp/装载问题队列式分支限界法求解#includestdafx.h#includeQueue.h#includeusingnamespacestd;constintN=4;templateclassQNodetemplatefriendvoidEnQueue(QueueQNode*&Q,Typewt,inti

20、,intn,Typebestw,QNode*E,QNode*&bestE,intbestx,boolch);templatefriendTypeMaxLoading(Typew,Typec,intn,intbestx);private:QNode*parent;/指向父节点的指针boolLChild;/左儿子标识Typeweight;/节点所相应的载重量;templatevoidEnQueue(QueueQNode*&Q,Typewt,inti,intn,Typebestw,QNode*E,QNode*&bestE,intbestx,boolch);templateTypeMaxLoading

21、(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中templatevoid

22、EnQueue(QueueQNode*&Q,Typewt,inti,intn,Typebestw,QNode*E,QNode*&bestE,intbestx,boolch)if(i=n)/可行叶节点if(wt=bestw)/当前最优装载重量bestE=E;bestxn=ch;return;/非叶节点QNode*b;b=newQNode;b-weight=wt;b-parent=E;b-LChild=ch;Q.Add(b);templateTypeMaxLoading(Typew,Typec,intn,intbestx)/队列式分支限界法，返回最优装载重量，bestx返回最优解/初始化Queue

23、QNode*Q;/活节点队列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(wtbestw)bestw=wt;EnQueue(Q,wt,i,n,bestw,E,bestE,bestx,true);/检查右儿子节点if(Ew+rbestw)EnQueue(Q,Ew,i,n,be

24、stw,E,bestE,bestx,false);Q.Delete(E);/取下一扩展节点if(!E)/同层节点尾部if(Q.IsEmpty()break;Q.Add(0);/同层节点尾部标识Q.Delete(E);/取下一扩展节点i+;/进入下一层r-=wi;/剩余集装箱重量Ew=E-weight;/新扩展节点所对应的载重量/构造当前最优解for(intj=n-1;j0;j-)bestxj=bestE-LChild;bestE=bestE-parent;returnbestw;2.3测试截图3回朔法-迭代3.1算法分析用回溯法解装载问题时，用子集树表示其解空间显然是最合适的。可行性约束条件重

25、量之和小于(c1 + c2)可剪去不满足约束条件的子树用cw记当前的装载重量，即cw=(w1x1+w2x2+.+wjxj)，当cwc1时，以节点Z为根的子树中所有节点都不满足约束条件，因而该子树中解均为不可行解，故可将该子树剪去。3.2代码#includeusingnamespacestd;templateTypeMaxLoading(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;

26、coutc(1)=c,c(2)=c2endl;cout待装集装箱重量分别为：endl;coutw(i)=;for(inti=1;i=n;i+)coutwi;coutendl;cout回溯选择结果为：endl;coutm(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);coutm(2)=m2c2)cout因为m(2)大于c(2),所以原问题无解！endl;return0;templateTypeMaxLoading(Typew,Typec,

27、intn,intbestx)/迭代回溯法，返回最优载重量及其相应解，初始化根结点inti=1;/当前层，x1:i-1为当前路径int*x=newintn+1;Typebestw=0,/当前最优载重量cw=0,/当前载重量r=0;/剩余集装箱重量for(intj=1;j=n;j+)r+=wj;while(true)/搜索子树while(i=n&cw+win)/到达叶结点for(intj=1;j=n;j+)bestxj=xj;bestw=cw;else/进入右子树r-=wi;xi=0;i+;while(cw+r0&!xi)r+=wi;i-;/从右子树返回if(i=0)deletex;returnb

28、estw;xi=0;cw-=wi;i+;3.3测试截图4回朔法-递归4.1算法分析与回朔法-迭代的相同，以下代码只是更改了具体的实现过程4.2代码#includeusingnamespacestd;templateclassLoading/friendTypeMaxLoading(Type,Type,int,int);/private:public:voidBacktrack(inti);intn,/集装箱数*x,/当前解*bestx;/当前最优解Type*w,/集装箱重量数组c,/第一艘轮船的载重量cw,/当前载重量bestw,/当前最优载重量r;/剩余集装箱重量;templatevoidL

29、oading:Backtrack(inti);templateTypeMaxLoading(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;coutc(1)=c,c(2)=c2endl;cout待装集装箱重量分别为：endl;coutw(i)=;for(inti=1;i=n;i+)coutwi;coutendl;cout回溯选择结果为：endl;coutm(1)=mendl;cout

30、x(i)=;for(inti=1;i=n;i+)coutbestxi;coutendl;intm2=0;for(intj=1;j=n;j+)m2=m2+wj*(1-bestxj);coutm(2)=m2c2)cout因为m(2)大于c(2),所以原问题无解！endl;return0;templatevoidLoading:Backtrack(inti)/搜索第i层结点if(in)/到达叶结点if(cwbestw)for(intj=1;j=n;j+)bestxj=xj;/更新最优解bestw=cw;return;r-=wi;if(cw+wibestw)xi=0;/搜索右子树Backtrack(i

31、+1);r+=wi;templateTypeMaxLoading(Typew,Typec,intn,intbestx)/返回最优载重量LoadingX;/初始化XX.x=newintn+1;X.w=w;X.c=c;X.n=n;X.bestx=bestx;X.bestw=0;X.cw=0;/初始化rX.r=0;for(inti=1;i=n;i+)X.r+=wi;X.Backtrack(1);deleteX.x;returnX.bestw;4.3测试截图5贪心算法5.1算法分析最优子结构性质：设(x1,x2,xn)是最优装载问题的满足贪心选择性质的最优解，则易知，x1=1,(x2,x3,xn)是轮

32、船载重量为c-w1，待装船集装箱为2,3，n时相应最优装载问题的最优解。因此，最优装载问题具有最优子结构性质。求解过程：最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略，可产生最优装载问题的最优解。5.2代码#includeusingnamespacestd;constintN=4;templatevoidS&x,Type&y);templatevoidLoading(intx,Typew,Typec,intn);templatevoidSelectSort(Typew,int*t,intn);intmain()floatc=70;floatw=0,20,10,26,15;/下标从1开始intxN+1;cout轮船载重为：cendl;cout待装物品的重量分别为：endl;for(inti=1;i=N;i+)coutwi;coutendl;Loading(x,w,c,N);cout贪心选择结果为:endl;for(inti=1;i=N;i+)coutxi;coutendl;return0;templatevoidLoading(intx,Typew,Typec,intn)int*t=newintn+1;/存储排完序后w