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

《2022年算法笔记——【分支限界法】最优装载问题.docx》由会员分享，可在线阅读，更多相关《2022年算法笔记——【分支限界法】最优装载问题.docx（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -问题描述有一批共个集装箱要装上2 艘载重量分别为C1 和 C2 的轮船,其中集装箱 i 的重量为 Wi,且 一个合理的装载方案可将这个集装箱装上这一种装载方案；装载问题要求确定是否有 2 艘轮船；假如有,找出简单证明：假如一个给定装载问题有解,就采纳下面的策略可得到 最优装载方案； 1 第一将第一艘轮船尽可能装满； 2 将剩余的集装箱装上其次艘轮船；1、队列式分支限界法求解在算法的循环体中,第一检测当前扩展结点的左儿子结点是否为可 行结点；假如是就将其加入到活结点队列中；然后将其右儿子结点加入到活结点队列中

2、右儿子结点肯定是可行结点 后,当前扩展结点被舍弃；2 个儿子结点都产生活结点队列中的队首元素被取出作为当前扩展结点,由于队列中每一层结点之后都有一个尾部标记-1,故在取队首元素时,活结点队列肯定不空；当取出的元素是-1 时,再判定当前队列是否为空；假如队列非空,就将尾部标记 结点；-1 加入活结点队列,算法开头处理下一层的活细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 1 页,共 15 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -节点的左子树表示将此集装箱装上船,右子

3、树表示不将此集装箱装上船；设 bestw 是当前最优解； ew 是当前扩展结点所相应的重量；r是剩余集装箱的重量；就当ew+rbestw 时,可将其右子树剪去,因为此时如要船装最多集装箱,就应当把此箱装上船；另外,为了确保 右子树胜利剪枝,应当在算法每一次进入左子树的时候更新 bestw 的 值；为了在算法终止后能便利地构造出与最优值相应的最优解,算法必 须储备相应子集树中从活结点到根结点的路径；为此目的,可在每个 结点处设置指向其父结点的指针,并设置左、右儿子标志；cpp找到最优值后,可以依据 parent 回溯到根节点,找到最优解；算法详细代码实现如下： 1 、Queue.hview pl

4、ain copy1. #include2. using namespace std; 3.4. template 5. class Queue 6. 7. public : 8. Queue int MaxQueueSize=50; 9. Queue delete queue; 10. bool IsEmpty const return front=rear; 11. bool IsFull return rear+1 %MaxSize=front .1:0; 12. T Top const ; 13. T Last const ; 14. Queue& Add const T& x; 细心整

5、理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 2 页,共 15 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -15. Queue& AddLeftconst T& x; 16.; Queue& DeleteT &x; 17.void Outputostream& outconst ; 18.int Lengthreturn rear-front; 19.private: 20.int front; 21.int rear; 22.int MaxSize; 23. T *que

6、ue; 24.25.26. template 27. Queue:Queue int MaxQueueSize 28. 29. MaxSize=MaxQueueSize+1; 30. queue= new TMaxSize; 31. front=rear=0; 32. 33.34. template 35. T Queue:Top const36. 37. if IsEmpty 38. 39. cout queue:no element,no. endl; 40. return 0; 41. 42. else return queuefront+1 % MaxSize; 43. 44.45.t

7、emplate endl; 46.T Queue :Lastconst47. 48.if IsEmpty 49. 50. coutqueue:no element51.return 0; 52. 53.elsereturn queuerear; 54. 55.细心整理归纳 精选学习资料 56.template const T& x 第 3 页,共 15 页 57.Queue& Queue:Add58. - - - - - - - - - - - - - - - - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -59.if

8、IsFullcoutqueue:no memoryendl; 60. else61. 62. rear=rear+1% MaxSize; 63. queuerear=x; 64. 65.return * this; 66.67.68.template endl; 69.Queue& Queue:AddLeftconst T& x 70. 71.if IsFullcoutqueue:no memory72.else73. 74. front=front+MaxSize-1% MaxSize; 75. queuefront+1% MaxSize=x; 76. 77.return * this; 7

9、8. 79.80.template endl; 81.Queue& Queue :DeleteT & x 82. 83.if IsEmptycoutqueue:no elementdelete84.else85. 86. front=front+1 % MaxSize; 87. x=queuefront; 88. 89.return * this; 90. 91.92.93. template 94. void Queue :Outputostream& out const95. 96. for int i=rear%MaxSize;i=front+1%MaxSize;i- 97. outqu

10、euei; 98. 99.细心整理归纳 精选学习资料 100.template const Queue& x 第 4 页,共 15 页 101.ostream& operator ostream& out,102.x.Outputout;return out; - - - - - - - - - - - - - - - - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - - 2 、6d3-1.cppcpp view plain copy1. / 装载问题 队列式分支限界法求解2. #include stdafx.h3. #in

11、clude Queue.h4. #include 5. using namespace std; 6.7.constint N = 4; 8.9.template int i,int n,Type bestw,Q10.class QNode 11. 12.template 13.friendvoid EnQueueQueueQNode*&Q,Type wt,Node*E,QNode *&bestE,int bestx,bool ch; 14.15.template int n, int bestx; 16.friend Type MaxLoadingType w,Type c,17.18.;

12、private: / 指向父节点的指针19. QNode *parent; 20.bool LChild; / 左儿子标识21. Type weight; / 节点所相应的载重量22.23.24.template int i,int n,Type bestw,QNode*25.void EnQueueQueueQNode*&Q,Type wt,E,QNode *&bestE,int bestx,bool ch; 26.27.template int n,int bestx; 28.Type MaxLoadingType w,Type c,29.30.int main / 下标从 1 开头31.

13、 32.float c = 70; 33.float w = 0,20,10,26,15;34.int xN+1; 35.float bestw; 36.细心整理归纳 精选学习资料 37. cout 轮船载重为： cendl; 第 5 页,共 15 页 38. cout 待装物品的重量分别为： endl; 39.for int i=1; i=N; i+ - - - - - - - - - - - - - - - - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -40. 41. coutwi ; 42. 43. couten

14、dl; 44. bestw = MaxLoadingw,c,N,x; 45.46. cout 分支限界挑选结果为 : endl; 47. for int i=1; i=4; i+ 48. 49. coutxi ; 50. 51. coutendl; 52. cout 最优装载重量为： bestwendl; 53.54. return 0; 55.56.57./ 将活节点加入到活节点队列Q中int i,int n,Type bestw,QNode*58.template 59.void EnQueueQueueQNode*&Q,Type wt,60.E,QNode *&bestE,int bes

15、tx,bool ch 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 = new QNode; 74. b-weight = wt; 75. b-parent = E; 76. b-LChild = ch; 77. Q.Addb; 78. 79.细心整理归纳 精选学习资料 80.template 第 6 页,共 15 页 81.Type MaxLoadingType w,T

16、ype c,int n,int bestx 82. / 队列式分支限界法,返回最优装载重量,bestx返回最优解 - - - - - - - - - - - - - - - - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -83. / 初始化84. QueueQNode* Q; / 活节点队列85. Q.Add0; / 同层节点尾部标识86.int i = 1; / 当前扩展节点所处的层87. Type Ew = 0, / 扩展节点所相应的载重量88. bestw = 0, / 当前最优装载重量89. r = 0; / 剩

17、余集装箱重量90.91. for int j=2; j=n; j+ 92. 93. r += wj; 94. 95.96. QNode *E = 0, / 当前扩展节点97. *bestE; / 当前最优扩展节点98.99./ 搜寻子集空间树true ; 100.while true 101. 102./ 检查左儿子节点103. Type wt = Ew + wi; 104.if wt bestw 107. 108. bestw = wt; 109. 110. EnQueueQ,wt,i,n,bestw,E,bestE,bestx,111. 112.113./ 检查右儿子节点false; 11

18、4.if Ew+rbestw 115. 116. EnQueueQ,Ew,i,n,bestw,E,bestE,bestx,117. 118. Q.DeleteE;/ 取下一扩展节点119.细心整理归纳 精选学习资料 120.if .E / 同层节点尾部/ 同层节点尾部标识 第 7 页,共 15 页 121. 122.if Q.IsEmpty 123. 124.break ; 125. 126. Q.Add0; - - - - - - - - - - - - - - - - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -12

19、7. Q.DeleteE; / 取下一扩展节点128. i+; / 进入下一层129. r-=wi; / 剩余集装箱重量130. / 新扩展节点所对应的载重量131. Ew =E-weight; 132. 133.134. / 构造当前最优解135.for int j=n-1; j0; j- 136. 137. bestxj = bestE-LChild; 138. bestE = bestE-parent; 139. 140.return bestw; 141.程序运行结果如图：2、优先队列式分支限界法求解解装载问题的优先队列式分支限界法用最大优先队列 储备活结点表；活结点 x 在优先队列中

20、的优先级定义为从根结点到结点 x 的路径所相 应的载重量再加上剩余集装箱的重量之和；优先队列中优先级最大的活结点成为下一个扩展结点；以结点 x 为 根的子树中全部结点相应的路径的载重量不超过它的优先级；子集树 中叶结点所相应的载重量与其优先级相同；在优先队列式分支限界法中,一旦有一个叶结点成为当前扩展结点,就可以断言该叶结点所相应的解即为最优解；此时可终止算法；算法详细代码实现如下：细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 8 页,共 15 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - -

21、- - - - - - 1 、MaxHeap.hcpp view plain copy1. template 2. class MaxHeap 3. 4. public : 5. MaxHeap int MaxHeapSize = 10; 6. MaxHeap delete heap; 7. int Size const return CurrentSize; 8.9. T Max / 查10. 11. if CurrentSize = 0 12.13. throw OutOfBounds; 14.15. return heap1; 16.17.18. MaxHeap& Insertconst

22、 T& x; / 增19. MaxHeap& DeleteMaxT& x; / 删20.21.void InitializeT a, int size, int ArraySize; 22.23.; private: 24.int CurrentSize, MaxSize; 25. T *heap; / element array26.27.28. template 29. MaxHeap:MaxHeap int MaxHeapSize 30. / Max heap constructor.31. MaxSize = MaxHeapSize; 32. heap = new TMaxSize+1

23、; 33. CurrentSize = 0; 34. 35.细心整理归纳 精选学习资料 36.template const T& x 第 9 页,共 15 页 37.MaxHeap& MaxHeap:Insert38. / Insert x into the max heap.39.if CurrentSize = MaxSize 40. - - - - - - - - - - - - - - - - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -41. coutno space. heapi/2 49. 50. / i

24、不是根节点,且其值大于父节点的值,需要连续调整51. heapi = heapi/2; / 父节点下降52. i /= 2; / 连续向上,搜寻正确位置53. 54.55. heapi = x; ; 56.return * this57. 58.59. template 60. MaxHeap& MaxHeap:DeleteMaxT& x 61. / Set x to max element and delete max element from heap.62. / check if heap is empty63. if CurrentSize = 0 64. 65. cout Empty

25、 heap. endl; 66. return * this ; 67. 68.69. x = heap1; / 删除最大元素/ 取最终一个节点,从根开头重整70./ 重整堆71. T y = heapCurrentSize-; 72.73. / find place for y starting at root74. int i = 1, / current node of heap75. ci = 2; / child of i76.细心整理归纳 精选学习资料 77.while ci = CurrentSize 第 10 页,共 15 页 78. 79./ 使 ci指向 i 的两个孩子中较

26、大者80.if ci CurrentSize & heapci = heapci 86. break ; / 是, i 就是 y 的正确位置,退出87. 88.89.90./ 否,需要连续向下,重整堆大于父节点的孩子节点上升91. heapi = heapci; / 92. i = ci; / 向下一层,连续搜寻正确位置93. ci *= 2; 94. 95.96. heapi = y; ; 97.return * this98.99.100.template int size,int ArraySize 101.void MaxHeap:InitializeT a, 102. / Initi

27、alize max heap to array a.103.delete heap; 104. heap = a; 105. CurrentSize = size; 106. MaxSize = ArraySize; 107.108. / 从最终一个内部节点开头,始终到根,对每个子树进行堆重整109.for int i = CurrentSize/2; i = 1; i- 110. T y = heapi; / 子树根节点元素111.112./ find place to put y113.int c = 2*i; / parent of c is target114./ location f

28、or y115.while c = CurrentSize 116. 117./ heapc should be larger sibling118.if c CurrentSize & heapc = heapc 124. 125.break ; / yes126. 127.细心整理归纳 精选学习资料 128./ no 第 11 页,共 15 页 - - - - - - - - - - - - - - - - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -129. heapc/2 = heapc; / move chil

29、d up130. c *= 2; / move down a level131. 132. heapc/2 = y; 133. 134. 2 、6d3-2.cppcpp view plain copy1. / 装载问题 优先队列式分支限界法求解2. #include stdafx.h3. #include MaxHeap.h4. #include 5. using namespace std; 6.7.constint N = 4; 8.9. class bbnode; 10.11.template boo12.class HeapNode 13. 14.template 15.friendv

30、oid AddLiveNodeMaxHeapHeapNode& H,bbnode *E,Type wt,16.l ch,int lev; template 17.friend Type MaxLoadingType w,Type c,int n, int bestx; 18.public: 19. operator Type const return uweight; 20.private: 21. bbnode *ptr; / 指向活节点在子集树中相应节点的指针22. Type uweight; / 活节点优先级 上界 23.int level; / 活节点在子集树中所处的层序号24.; 2

31、5.26.class bbnode boo27. 28.template 29.friendvoid AddLiveNodeMaxHeapHeapNode& H,bbnode *E,Type wt,30.l ch,int lev; template 31.friend Type MaxLoadingType w,Type c,int n, int bestx; 32.friendclass AdjacencyGraph; 33.细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 12 页,共 15 页 - - - - - - - - - 名师归纳总结 精

32、品学习资料 - - - - - - - - - - - - - - -34.private: 35.; bbnode *parent; / 指向父节点的指针36.bool LChild; / 左儿子节点标识37.38.39.template bool ch,int le40.void AddLiveNodeMaxHeapHeapNode& H,bbnode *E,Type wt,v; 41.42.template int n,int bestx; 43.Type MaxLoadingType w,Type c,44.45.46.int main / 下标从 1 开头47. 48.float c = 70; 49.float w = 0,20,10,26,15;50.int xN+1; 51.float bestw; 52.53. cout 轮船载重为： cendl; 54. cout 待装物品的重量分别为： endl; 55. for int i=1; i=N; i+ 56. 57. coutwi ; 58. 59. coutendl; 60. bestw = MaxLoadingw,c,N,x; 61.62. cout 分支限界挑选结果为 : endl; 63. for int i=1; i=4; i+ 64. 65. coutxi ; 66. 67. coutendl;