0034算法笔记——【分支限界法】最优装载问题.docx

问题描述 有一批共个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集装箱i的重量为Wi，且装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。 容易证明：如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。 (1)首先将第一艘轮船尽可能装满； (2)将剩余的集装箱装上第二艘轮船。 1、队列式分支限界法求解 在算法的循环体中，首先检测当前扩展结点的左儿子结点是否为可行结点。如果是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点队列中(右儿子结点一定是可行结点)。2个儿子结点都产生后，当前扩展结点被舍弃。 活结点队列中的队首元素被取出作为当前扩展结点，由于队列中每一层结点之后都有一个尾部标记-1，故在取队首元素时，活结点队列一定不空。当取出的元素是-1时，再判断当前队列是否为空。如果队列非空，则将尾部标记-1加入活结点队列，算法开始处理下一层的活结点。 节点的左子树表示将此集装箱装上船，右子树表示不将此集装箱装上船。设bestw是当前最优解；ew是当前扩展结点所相应的重量；r是剩余集装箱的重量。则当ew+rbestw时，可将其右子树剪去，因为此时若要船装最多集装箱，就应该把此箱装上船。另外，为了确保右子树成功剪枝，应该在算法每一次进入左子树的时候更新bestw的值。 为了在算法结束后能方便地构造出与最优值相应的最优解，算法必须存储相应子集树中从活结点到根结点的路径。为此目的，可在每个结点处设置指向其父结点的指针，并设置左、右儿子标志。 找到最优值后，可以根据parent回溯到根节点，找到最优解。 算法具体代码实现如下： 1、Queue.hcppview plaincopy1. #include2. usingnamespacestd;3. 4. template5. classQueue6. 7. public:8. Queue(intMaxQueueSize=50);9. Queue()deletequeue;10. boolIsEmpty()constreturnfront=rear;11. boolIsFull()return(rear+1)%MaxSize=front)?1:0);12. TTop()const;13. TLast()const;14. Queue&Add(constT&x);15. Queue&AddLeft(constT&x);16. Queue&Delete(T&x);17. voidOutput(ostream&out)const;18. intLength()return(rear-front);19. private:20. intfront;21. intrear;22. intMaxSize;23. T*queue;24. ;25. 26. template27. Queue:Queue(intMaxQueueSize)28. 29. MaxSize=MaxQueueSize+1;30. queue=newTMaxSize;31. front=rear=0;32. 33. 34. template35. TQueue:Top()const36. 37. if(IsEmpty()38. 39. coutqueue:noelement,no!endl;40. return0;41. 42. elsereturnqueue(front+1)%MaxSize;43. 44. 45. template46. TQueue:Last()const47. 48. if(IsEmpty()49. 50. coutqueue:noelementendl;51. return0;52. 53. elsereturnqueuerear;54. 55. 56. template57. Queue&Queue:Add(constT&x)58. 59. if(IsFull()coutqueue:nomemoryendl;60. else61. 62. rear=(rear+1)%MaxSize;63. queuerear=x;64. 65. return*this;66. 67. 68. template69. Queue&Queue:AddLeft(constT&x)70. 71. if(IsFull()coutqueue:nomemoryendl;72. else73. 74. front=(front+MaxSize-1)%MaxSize;75. queue(front+1)%MaxSize=x;76. 77. return*this;78. 79. 80. template81. Queue&Queue:Delete(T&x)82. 83. if(IsEmpty()coutqueue:noelement(delete)endl;84. else85. 86. front=(front+1)%MaxSize;87. x=queuefront;88. 89. return*this;90. 91. 92. 93. template94. voidQueue:Output(ostream&out)const95. 96. for(inti=rear%MaxSize;i=(front+1)%MaxSize;i-)97. outqueuei;98. 99. 100. template101. ostream&operator(ostream&out,constQueue&x)102. x.Output(out);returnout; 2、6d3-1.cppcppview plaincopy1. /装载问题队列式分支限界法求解2. #includestdafx.h3. #includeQueue.h4. #include5. usingnamespacestd;6. 7. constintN=4;8. 9. template10. classQNode11. 12. template13. friendvoidEnQueue(QueueQNode*&Q,Typewt,inti,intn,Typebestw,QNode*E,QNode*&bestE,intbestx,boolch);14. 15. template16. friendTypeMaxLoading(Typew,Typec,intn,intbestx);17. 18. private:19. QNode*parent;/指向父节点的指针20. boolLChild;/左儿子标识21. Typeweight;/节点所相应的载重量22. ;23. 24. template25. voidEnQueue(QueueQNode*&Q,Typewt,inti,intn,Typebestw,QNode*E,QNode*&bestE,intbestx,boolch);26. 27. template28. TypeMaxLoading(Typew,Typec,intn,intbestx);29. 30. intmain()31. 32. floatc=70;33. floatw=0,20,10,26,15;/下标从1开始34. intxN+1;35. floatbestw;36. 37. cout轮船载重为：cendl;38. cout待装物品的重量分别为：endl;39. for(inti=1;i=N;i+)40. 41. coutwi;42. 43. coutendl;44. bestw=MaxLoading(w,c,N,x);45. 46. cout分支限界选择结果为:endl;47. for(inti=1;i=4;i+)48. 49. coutxi;50. 51. coutendl;52. cout最优装载重量为：bestwendl;53. 54. return0;55. 56. 57. /将活节点加入到活节点队列Q中58. template59. voidEnQueue(QueueQNode*&Q,Typewt,inti,intn,Typebestw,QNode*E,QNode*&bestE,intbestx,boolch)60. 61. if(i=n)/可行叶节点62. 63. if(wt=bestw)64. 65. /当前最优装载重量66. bestE=E;67. bestxn=ch;68. 69. return;70. 71. /非叶节点72. QNode*b;73. b=newQNode;74. b-weight=wt;75. b-parent=E;76. b-LChild=ch;77. Q.Add(b);78. 79. 80. template81. TypeMaxLoading(Typew,Typec,intn,intbestx)82. /队列式分支限界法，返回最优装载重量，bestx返回最优解83. /初始化84. QueueQNode*Q;/活节点队列85. Q.Add(0);/同层节点尾部标识86. inti=1;/当前扩展节点所处的层87. TypeEw=0,/扩展节点所相应的载重量88. bestw=0,/当前最优装载重量89. r=0;/剩余集装箱重量90. 91. for(intj=2;j=n;j+)92. 93. r+=wj;94. 95. 96. QNode*E=0,/当前扩展节点97. *bestE;/当前最优扩展节点98. 99. /搜索子集空间树100. while(true)101. 102. /检查左儿子节点103. Typewt=Ew+wi;104. if(wtbestw)107. 108. bestw=wt;109. 110. EnQueue(Q,wt,i,n,bestw,E,bestE,bestx,true);111. 112. 113. /检查右儿子节点114. if(Ew+rbestw)115. 116. EnQueue(Q,Ew,i,n,bestw,E,bestE,bestx,false);117. 118. Q.Delete(E);/取下一扩展节点119. 120. if(!E)/同层节点尾部121. 122. if(Q.IsEmpty()123. 124. break;125. 126. Q.Add(0);/同层节点尾部标识127. Q.Delete(E);/取下一扩展节点128. i+;/进入下一层129. r-=wi;/剩余集装箱重量130. 131. Ew=E-weight;/新扩展节点所对应的载重量132. 133. 134. /构造当前最优解135. for(intj=n-1;j0;j-)136. 137. bestxj=bestE-LChild;138. bestE=bestE-parent;139. 140. returnbestw;141. 程序运行结果如图： 2、优先队列式分支限界法求解 解装载问题的优先队列式分支限界法用最大优先队列存储活结点表。活结点x在优先队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和。 优先队列中优先级最大的活结点成为下一个扩展结点。以结点x为根的子树中所有结点相应的路径的载重量不超过它的优先级。子集树中叶结点所相应的载重量与其优先级相同。 在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。此时可终止算法。 算法具体代码实现如下： 1、MaxHeap.hcppview plaincopy1. template2. classMaxHeap3. 4. public:5. MaxHeap(intMaxHeapSize=10);6. MaxHeap()deleteheap;7. intSize()constreturnCurrentSize;8. 9. TMax()10. /查11. if(CurrentSize=0)12. 13. throwOutOfBounds();14. 15. returnheap1;16. 17. 18. MaxHeap&Insert(constT&x);/增19. MaxHeap&DeleteMax(T&x);/删20. 21. voidInitialize(Ta,intsize,intArraySize);22. 23. private:24. intCurrentSize,MaxSize;25. T*heap;/elementarray26. ;27. 28. template29. MaxHeap:MaxHeap(intMaxHeapSize)30. /Maxheapconstructor.31. MaxSize=MaxHeapSize;32. heap=newTMaxSize+1;33. CurrentSize=0;34. 35. 36. template37. MaxHeap&MaxHeap:Insert(constT&x)38. /Insertxintothemaxheap.39. if(CurrentSize=MaxSize)40. 41. coutnospace!heapi/2)49. 50. /i不是根节点，且其值大于父节点的值，需要继续调整51. heapi=heapi/2;/父节点下降52. i/=2;/继续向上，搜寻正确位置53. 54. 55. heapi=x;56. return*this;57. 58. 59. template60. MaxHeap&MaxHeap:DeleteMax(T&x)61. /Setxtomaxelementanddeletemaxelementfromheap.62. /checkifheapisempty63. if(CurrentSize=0)64. 65. coutEmptyheap!endl;66. return*this;67. 68. 69. x=heap1;/删除最大元素70. /重整堆71. Ty=heapCurrentSize-;/取最后一个节点，从根开始重整72. 73. /findplaceforystartingatroot74. inti=1,/currentnodeofheap75. ci=2;/childofi76. 77. while(ci=CurrentSize)78. 79. /使ci指向i的两个孩子中较大者80. if(ciCurrentSize&heapci=heapci)86. 87. break;/是，i就是y的正确位置，退出88. 89. 90. /否，需要继续向下，重整堆91. heapi=heapci;/大于父节点的孩子节点上升92. i=ci;/向下一层，继续搜索正确位置93. ci*=2;94. 95. 96. heapi=y;97. return*this;98. 99. 100. template101. voidMaxHeap:Initialize(Ta,intsize,intArraySize)102. /Initializemaxheaptoarraya.103. deleteheap;104. heap=a;105. CurrentSize=size;106. MaxSize=ArraySize;107. 108. /从最后一个内部节点开始，一直到根，对每个子树进行堆重整109. for(inti=CurrentSize/2;i=1;i-)110. 111. Ty=heapi;/子树根节点元素112. /findplacetoputy113. intc=2*i;/parentofcistarget114. /locationfory115. while(c=CurrentSize)116. 117. /heapcshouldbelargersibling118. if(cCurrentSize&heapc=heapc)124. 125. break;/yes126. 127. 128. /no129. heapc/2=heapc;/movechildup130. c*=2;/movedownalevel131. 132. heapc/2=y;133. 134. 2、6d3-2.cppcppview plaincopy1. /装载问题优先队列式分支限界法求解2. #includestdafx.h3. #includeMaxHeap.h4. #include5. usingnamespacestd;6. 7. constintN=4;8. 9. classbbnode;10. 11. template12. classHeapNode13. 14. template15. friendvoidAddLiveNode(MaxHeapHeapNode&H,bbnode*E,Typewt,boolch,intlev);16. template17. friendTypeMaxLoading(Typew,Typec,intn,intbestx);18. public:19. operatorType()constreturnuweight;20. private:21. bbnode*ptr;/指向活节点在子集树中相应节点的指针22. Typeuweight;/活节点优先级(上界)23. intlevel;/活节点在子集树中所处的层序号24. ;25. 26. classbbnode27. 28. template29. friendvoidAddLiveNode(MaxHeapHeapNode&H,bbnode*E,Typewt,boolch,intlev);30. template31. friendTypeMaxLoading(Typew,Typec,intn,intbestx);32. friendclassAdjacencyGraph;33. 34. private:35. bbnode*parent;/指向父节点的指针36. boolLChild;/左儿子节点标识37. ;38. 39. template40. voidAddLiveNode(MaxHeapHeapNode&H,bbnode*E,Typewt,boolch,intlev);41. 42. template43. TypeMaxLoading(Typew,Typec,intn,intbestx);44. 45. 46. intmain()47. 48. floatc=70;49. floatw=0,20,10,26,15;/下标从1开始50. intxN+1;51. floatbestw;52. 53. cout轮船载重为：cendl;54. cout待装物品的重量分别为：endl;55. for(inti=1;i=N;i+)56. 57. coutwi;58. 59. coutendl;60. bestw=MaxLoading(w,c,N,x);61. 62. cout分支限界选择结果为:endl;63. for(inti=1;i=4;i+)64. 65. coutxi;66. 67. coutendl;68. cout最优装载重量为：bestwendl;69. 70. return0;71. 72. 73. /将活节点加入到表示活节点优先队列的最大堆H中74. template75. voidAddLiveNode(MaxHeapHeapNode&H,bbnode*E,T