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

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代码 .264.3测试截图 .315贪心算法 .315.1算法分析 .315.2代码 .315.3测试

2、截图 .35II算法分析与设计一问题定义有一批共有 n个集装箱要装上两艘载重量分别为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;3/ 35算法分析与设计TMax()/ 查找if(CurrentSize=0)throwOutOfBounds();returnheap1;MaxHeap& Insert(constT&x);/ 增MaxHeap& DeleteMax

4、(T&x);/ 删voidInitialize(Ta,intsize,intArraySize);private:intCurrentSize,MaxSize;T*heap;/elementarray;templateMaxHeap:MaxHeap(intMaxHeapSize)/Maxheapconstructor.MaxSize=MaxHeapSize;heap=newTMaxSize+1;CurrentSize=0;templateMaxHeap& MaxHeap:Insert(constT&x)/Insertxintothemaxheap.4/ 35算法分析与设计if(CurrentS

5、ize=MaxSize)coutnospace!heapi/2)/ i 不是根节点，且其值大于父节点的值，需要继续调整heapi=heapi/2;/父节点下降i/=2;/继续向上，搜寻正确位置heapi=x;return*this;templateMaxHeap& MaxHeap:DeleteMax(T&x)/Setxtomaxelementanddeletemaxelementfromheap./checkifheapisemptyif(CurrentSize=0)coutEmptyheap!endl;return*this;5/ 35算法分析与设计x=heap1;/删除最大元素/ 重整堆T

6、y=heapCurrentSize-;/取最后一个节点，从根开始重整/findplaceforystartingatrootinti=1,/currentnodeofheapci=2;/childofiwhile(ci=CurrentSize)/ 使 ci 指向 i 的两个孩子中较大者if(ciCurrentSize&heapci=heapci)break;/是， i 就是 y 的正确位置，退出/ 否，需要继续向下，重整堆heapi=heapci;/大于父节点的孩子节点上升i=ci;/向下一层，继续搜索正确位置ci*=2;heapi=y;6/ 35算法分析与设计return*this;temp

7、latevoidMaxHeap: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)/heapcshouldbelar

8、gersiblingif(c CurrentSize& heapc=heapc)break;/yes7/ 35算法分析与设计/ noheapc/2=heapc;/movechildupc*=2;/movedownalevelheapc/2=y;1.2-2/6d3-2.cpp/ 装载问题优先队列式分支限界法求解#includestdafx.h#includeMaxHeap.h#includeusingnamespacestd;constintN=4;classbbnode;templateclassHeapNodetemplatefriendvoidAddLiveNode(MaxHeapHeap

9、Node&H,bbnode*E,Typewt,boolch,intlev);templatefriendTypeMaxLoading(Typew,Typec,intn,intbestx);public:8/ 35算法分析与设计operatorType()constreturnuweight;private:bbnode*ptr;/ 指向活节点在子集树中相应节点的指针Typeuweight;/ 活节点优先级 ( 上界 )intlevel;/活 节 点 在 子 集 树 中 所 处 的 层 序号;classbbnodetemplatefriendvoidAddLiveNode(MaxHeapHeap

10、Node&H,bbnode*E,Typewt,boolch,intlev);templatefriendTypeMaxLoading(Typew,Typec,intn,intbestx);friendclassAdjacencyGraph;private:bbnode*parent;/ 指向父节点的指针boolLChild;/ 左儿子节点标识;templatevoidAddLiveNode(MaxHeapHeapNode&H,bbnode*E,Typewt,boolch,intlev);templateTypeMaxLoading(Typew,Typec,intn,intbestx);9/ 3

11、5算法分析与设计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中template10/35算法分

12、析与设计voidAddLiveNode(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 返回最优解templateTypeMaxLoading(Typew,Typec,intn,intbestx)/ 定义最大的容量为 1000 MaxHeapHeapNode H(1000);/ 定义剩余容量数组Type

13、*r=newTypen+1;rn=0;for(intj=n-1;j0;j-)rj=rj+1+wj+1;11/35算法分析与设计/ 初始化inti=1;/当前扩展节点所处的层bbnode*E=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);/ 取下一扩展节点HeapNodeN;H.DeleteMax(N);/非空i=N.leve

14、l;E=N.ptr;Ew=N.uweight-ri-1;/ 构造当前最优解for(intj=n;j0;j-)bestxj=E-LChild;E=E-parent;12/35算法分析与设计returnEw;1.3 运行结果2 队列式分支限界法求解2.1 算法分析在算法的循环体中， 首先检测当前扩展结点的左儿子结点是否为可行结点。如果是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点队列中( 右儿子结点一定是可行结点) 。2 个儿子结点都产生后，当前扩展结点被舍弃。活结点队列中的队首元素被取出作为当前扩展结点，由于队列中每一层结点之后都有一个尾部标记-1 ，故在取队首元素时， 活结点队列一

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

16、处设置指向其父结点的指针，并设置左、右儿子标志。找到最优值后，可以根据 parent 回溯到根节点，找到最优解。13/35算法分析与设计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()const;TLast()const;Queue& Add(

17、constT&x);Queue& AddLeft(constT&x);Queue& Delete(T&x);voidOutput(ostream&out)const;intLength()return(rear-front);private:intfront;intrear;intMaxSize;T*queue;template14/35算法分析与设计Queue:Queue(intMaxQueueSize)MaxSize=MaxQueueSize+1;queue=newTMaxSize;front=rear=0;templateT Queue:Top()constif(IsEmpty()cou

18、tqueue:noelement,no!endl;return0;elsereturnqueue(front+1)% MaxSize;templateTQueue:Last()constif(IsEmpty()coutqueue:noelementendl;return0;elsereturnqueuerear;template15/35算法分析与设计Queue&Queue:Add(constT&x)if(IsFull()coutqueue:nomemoryendl;elserear=(rear+1)%MaxSize;queuerear=x;return*this;templateQueue&

19、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;16/35算法分析与设计x=queuefront;return*this;templatevoidQueue:Output(ostre

20、am&out)constfor(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;templateclassQNode17/35算法分析与设计templatefriendvoidEnQueue(Qu

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

22、olch);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+)18/35算法分析与设计coutwi;coutendl;bestw=MaxLoading(w,c,N,x);cout 分支限界选择结果为:endl;for(inti=1;i=4;i+)coutxi;coutendl;cout 最优装载重量

23、为：bestwendl;return0;/ 将活节点加入到活节点队列Q中templatevoidEnQueue(QueueQNode*&Q,Type wt,inti,intn,Typebestw,QNode*E,QNode*&bestE,intbestx,boolch)if(i=n)/可行叶节点if(wt=bestw)/ 当前最优装载重量bestE=E;bestxn=ch;19/35算法分析与设计return;/非叶节点QNode*b;b= newQNode;b-weight=wt;b-parent=E;b-LChild=ch;Q.Add(b);templateTypeMaxLoading(T

24、ypew,Typec,intn,intbestx)/队列式分支限界法，返回最优装载重量，bestx 返回最优解/ 初始化QueueQNode* Q;/ 活节点队列Q.Add(0);/ 同层节点尾部标识inti=1;/ 当前扩展节点所处的层TypeEw=0,/ 扩展节点所相应的载重量bestw=0,/ 当前最优装载重量r=0;/ 剩余集装箱重量for(intj=2;j=n;j+)r+=wj;QNode *E=0,/ 当前扩展节点*bestE;/ 当前最优扩展节点/ 搜索子集空间树20/35算法分析与设计while(true)/ 检查左儿子节点Typewt=Ew+wi;if(wtbestw)bes

25、tw=wt;EnQueue(Q,wt,i,n,bestw,E,bestE,bestx,true);/ 检查右儿子节点if(Ew+rbestw)EnQueue(Q,Ew,i,n,bestw,E,bestE,bestx,false);Q.Delete(E);/取下一扩展节点if(!E)/同层节点尾部if(Q.IsEmpty()break;Q.Add(0);/ 同层节点尾部标识Q.Delete(E);/ 取下一扩展节点i+;/ 进入下一层r-=wi;/ 剩余集装箱重量21/35算法分析与设计Ew=E-weight;/ 新扩展节点所对应的载重量/ 构造当前最优解for(intj=n-1;j0;j-)b

26、estxj=bestE-LChild;bestE=bestE-parent;returnbestw;2.3 测试截图3 回朔法 -迭代3.1 算法分析用回溯法解装载问题时，用子集树表示其解空间显然是最合适的。可行性约束条件重量之和小于 (c1 + c2) 可剪去不满足约束条件的子树用cw 记当前的装载重量，即 cw=(w1x1+w2x2+.+wjxj)，当 cwc1时，以节点 Z 为根的子树中所有节点都不满足约束条件，因而该子树中解均为不可行解，故可将该子树剪去。3.2 代码#includeusingnamespacestd;22/35算法分析与设计templateTypeMaxLoading

27、(Type w ,Type c, 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;coutx(i)=;for(inti=1;i=n;i+)coutbestxi;23

28、/35算法分析与设计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,intn,intbestx)/迭代回溯法，返回最优载重量及其相应解，初始化根结点inti=1;/当前层， x1:i-1为当前路径int*x=newintn+1;Typebestw=0,/ 当前最优载重量cw=0,/ 当前载重量r=0;/ 剩余集装箱重量for(intj=1;j=n;j+)24/35算法分析与设计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-;25/35算法分析