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

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

2、展结点被舍弃；活结点队列中的队首元素被取出作为当前扩展结点,由于队列中每一层结点之后都有一个尾部标记-1,故在取队首元素时,活结点队列肯定不空；当取出的元素为-1 时,再判定当前队列为否为空；假如队列非空,就将尾部标记-1 加入活结点队列,算法开头处理下一层的活结点；精品学习资料精选学习资料 - - - 欢迎下载节点的左子树表示将此集装箱装上船,右子树表示不将此集装箱装上船；设 bestw 为当前最优解； ew 为当前扩展结点所相应的重量；r 为剩余集装箱的重量；就当ew+r<bestw时,可将其右子树剪去,因 为此时如要船装最多集装箱,就应当把此箱装上船；另外,为了确保右子树胜利剪枝,

3、应当在算法每一次进入左子树的时候更新bestw 的值；为了在算法终止后能便利地构造出与最优值相应的最优解,算法必需储备相应子集树中从活结点到根结点的路径；为此目的,可在每个结点处设置指向其父结点的指针,并设置左.右儿子标志；找到最优值后,可以依据parent回溯到根节点,找到最优解；算法详细代码实现如下：1 .queue.hcppview plaincopy1. #include<iostream>2. usingnamespace std; 3.4. template< classt>5. classqueue 6.7. public:8. queueintmaxqu

4、euesize=50;9. queuedelete queue;10. boolisemptyconst returnfront=rear;11. boolisfullreturn rear+1 %maxsize=front .1:0;12. t topconst ;13. t lastconst ;14. queue<t>& addconstt& x;精品学习资料精选学习资料 - - - 欢迎下载15. queue<t>& addleftconstt& x;16. queue<t>& deletet &x;1

5、7. voidoutputostream& outconst ;18. intlengthreturnrear-front;19. private:20. intfront;21. intrear;22. intmaxsize;23. t *queue; 24.;25.26. template<classt>27. queue<t>:queueintmaxqueuesize28.29. maxsize=maxqueuesize+1;30. queue=new tmaxsize;31. front=rear=0;32. 33.34. template<cla

6、sst >35. t queue<t>:topconst36.37.if isempty38.39. cout<<"queue:no element、no."<<endl;40. return0;41.42.elsereturnqueuefront+1 % maxsize;43. 44.45. template<classt>46. t queue<t> :lastconst47.48.if isempty49.50. cout<<"queue:no element"<&

7、lt;endl;51. return0;52.53.elsereturnqueuerear;54. 55.56. template<classt>57. queue<t>& queue<t>:addconstt& x58.精品学习资料精选学习资料 - - - 欢迎下载59. if isfullcout<<"queue:no memory"<<endl;60. else61.62. rear=rear+1% maxsize;63. queuerear=x;64.65.return* this;66.

8、67.68. template<classt>69. queue<t>& queue<t>:addleftconstt& x70.71. if isfullcout<<"queue:no memory"<<endl;72. else73.74. front=front+maxsize-1% maxsize;75. queuefront+1% maxsize=x;76.77.return* this;78. 79.80. template<classt>81. queue<t>

9、& queue<t> :deletet & x82.83. if isemptycout<<"queue:no elementdelete"<<endl;84. else85.86. front=front+1 % maxsize;87. x=queuefront;88.89.return* this;90. 91. 92.93. template<classt>94. voidqueue <t>:outputostream& outconst95.96. for inti=rear%max

10、size;i>=front+1%maxsize;i-97. out<<queuei;98. 99.100. template<classt>101. ostream& operator << ostream& out、constqueue<t>& x102. x.outputout;returnout;精品学习资料精选学习资料 - - - 欢迎下载2 .6d3-1.cppcppview plaincopy1. / 装载问题队列式分支限界法求解2. #include "stdafx.h"3. #in

11、clude "queue.h"4. #include <iostream>5. usingnamespace std; 6.7.constintn = 4;8.9. template<classtype>10. classqnode11.12. template<classtype>13. friendvoidenqueuequeue<qnode<type>*>&q、type wt、inti、intn、type bestw、q node<type>*e、qnode<type> *&a

12、mp;beste、intbestx、boolch;14.15. template<classtype>16. friendtype maxloadingtype w、type c、intn、 intbestx; 17.18. private:19. qnode *parent;/ 指向父节点的指针20. boollchild;/ 左儿子标识21. type weight;/ 节点所相应的载重量22.;23.24. template<classtype>25. voidenqueuequeue<qnode<type>*>&q、type wt

13、、inti、intn、type bestw、qnode<type>* e、qnode<type> *&beste、intbestx、boolch;26.27. template<classtype>28. type maxloadingtype w、type c、intn、intbestx; 29.30.intmain31.32.floatc = 70;33.floatw = 0、20、10、26、15;/ 下标从 1 开头34. intxn+1;35. floatbestw; 36.37. cout<<" 轮船载重为： &qu

14、ot; <<c<<endl;38. cout<<" 待装物品的重量分别为：" <<endl;39. for inti=1; i<=n; i+精品学习资料精选学习资料 - - - 欢迎下载40.41.cout<<wi<<" "42.43. cout<<endl;44. bestw = maxloadingw、c、n、x; 45.46.cout<<" 分支限界挑选结果为:" <<endl;47.for inti=1; i<

15、;=4; i+48.49.cout<<xi<<" "50.51. cout<<endl;52. cout<<" 最优装载重量为：" <<bestw<<endl; 53.54.return0;55. 56.57. / 将活节点加入到活节点队列q 中58. template<classtype>59. voidenqueuequeue<qnode<type>*>&q、type wt、inti、intn、type bestw、qnode<t

16、ype>* e、qnode<type> *&beste、intbestx、boolch60.61.if i = n/ 可行叶节点62.63.if wt = bestw64.65. / 当前最优装载重量66. beste = e;67. bestxn = ch;68.69.return;70.71. / 非叶节点72. qnode<type> *b;73. b =new qnode<type>74. b->weight = wt;75. b->parent = e;76. b->lchild = ch;77. q.addb;78

17、. 79.80. template<classtype>81. type maxloadingtype w、type c、intn、intbestx82. / 队列式分支限界法,返回最优装载重量,bestx返回最优解精品学习资料精选学习资料 - - - 欢迎下载83./ 初始化84.queue<qnode<type>*> q;/ 活节点队列85.q.add0;/ 同层节点尾部标识86.inti = 1;/ 当前扩展节点所处的层87.type ew = 0、/ 扩展节点所相应的载重量88.bestw = 0、/ 当前最优装载重量89.r = 0;/ 剩余集装箱

18、重量90.91.for intj=2; j<=n; j+92.93.r += wj;94.95.96.qnode<type> *e = 0、/ 当前扩展节点97.*beste;/ 当前最优扩展节点98.99./ 搜寻子集空间树100.while true 101.102./ 检查左儿子节点103.type wt = ew + wi;104.if wt <= c/ 可行节点105.106.if wt>bestw107.108.bestw = wt;109.110.enqueueq、wt、i、n、bestw、e、beste、bestx、true;111.112.113

19、./ 检查右儿子节点114.if ew+r>bestw115.116.enqueueq、ew、i、n、bestw、e、beste、bestx、false;117.118.q.deletee;/ 取下一扩展节点119.120.if.e/ 同层节点尾部121.122.ifq.isempty123.124.break ;125.126.q.add0;/ 同层节点尾部标识精品学习资料精选学习资料 - - - 欢迎下载127.q.deletee;/取下一扩展节点128.i+;/进入下一层129.r-=wi;/剩余集装箱重量130.131.ew =e->weight;/ 新扩展节点所对应的载重

20、量132.133.134./ 构造当前最优解135.for intj=n-1; j>0; j-136.137.bestxj = beste->lchild;138.beste = beste->parent;139.140.returnbestw;141.程序运行结果如图：2.优先队列式分支限界法求解解装载问题的优先队列式分支限界法用 最大优先队列 储备活结点表；活结点 x 在优先队列中的优先级定义为从根结点到结点 x 的路径所相应的载重量再加上剩余集装箱的重量之和；优先队列中优先级最大的活结点成为下一个扩展结点；以结点x 为根的子树中全部结点相应的路径的载重量不超过它的优先

21、级；子集树中叶结点所相应的载重量与其优先级相同；在优先队列式分支限界法中,一旦有一个叶结点成为当前扩展结点,就可以断言该叶结点所相应的解即为最优解；此时可终止算法；算法详细代码实现如下：精品学习资料精选学习资料 - - - 欢迎下载1 .maxheap.hcppview plaincopy1. template<classt>2. classmaxheap 3.4. public:5. maxheapintmaxheapsize = 10;6. maxheap delete heap;7. intsizeconst returncurrentsize; 8.9.t max10./

22、查11.ifcurrentsize = 012.13.throwoutofbounds;14.15.returnheap1;16.17.18. maxheap<t>& insertconstt& x;/ 增19. maxheap<t>& deletemaxt& x;/ 删20.21. voidinitializet a、intsize、intarraysize; 22.23. private:24. intcurrentsize、 maxsize;25. t *heap;/ element array 26.;27.28. templat

23、e<classt>29. maxheap<t>:maxheapintmaxheapsize30. / max heap constructor.31. maxsize = maxheapsize;32. heap =new tmaxsize+1;33. currentsize = 0;34. 35.36. template<classt>37. maxheap<t>& maxheap<t>:insertconstt& x38. / insert x into the max heap.39. ifcurrentsize

24、 = maxsize40.精品学习资料精选学习资料 - - - 欢迎下载41.cout<<"no space."<<endl;42.return* this;43.44.45./查找新元素x 的位置46./ i初始为新叶节点的位置,逐层向上,查找最终位置47.inti = +currentsize;48.whilei .= 1 && x > heapi/249.50./ i不为根节点,且其值大于父节点的值,需要连续调整51.heapi = heapi/2;/父节点下降52.i /= 2;/连续向上,搜寻正确位置53.54.55.

25、 heapi = x;56. return* this;57. 58.59. template<classt>60. maxheap<t>& maxheap<t>:deletemaxt& x61. / set x to max element and delete max element from heap.62. / check if heap is empty63. ifcurrentsize = 064.65. cout<<"empty heap."<<endl;66. return* thi

26、s;67.68.69. x = heap1;/删除最大元素70. /重整堆71. t y = heapcurrentsize-;/取最终一个节点,从根开头重整72.73. / find place for y starting at root74. inti = 1、/ current node of heap75. ci = 2;/ child of i 76.77.whileci <= currentsize78.79. /使 ci指向 i 的两个孩子中较大者80. ifci < currentsize && heapci < heapci+181.82.

27、ci+;83.84./ y的值大于等于孩子节点吗？精品学习资料精选学习资料 - - - 欢迎下载85.ify >= heapci86.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. template<classt>101. voidmaxheap<t>:initializet a、in

28、tsize、intarraysize102. / initialize max heap to array a.103. delete heap;104. heap = a;105. currentsize = size;106. maxsize = arraysize; 107.108. /从最终一个内部节点开头,始终到根,对每个子树进行堆重整109. for inti = currentsize/2; i >= 1; i-110.111. t y = heapi;/子树根节点元素112. / find place to put y113. intc = 2*i;/ parent of

29、 c is target114. / location for y115. whilec <= currentsize116.117. / heapc should be larger sibling118. ifc < currentsize && heapc < heapc+1119.120.c+;121.122. / can we put y in heapc/2.123. ify >= heapc124.125.break ;/ yes126.127.128./ no精品学习资料精选学习资料 - - - 欢迎下载129. heapc/2 = he

30、apc;/ move child up130. c *= 2;/ move down a level131.132.heapc/2 = y;133.134.2 .6d3-2.cppcppview plaincopy1. / 装载问题优先队列式分支限界法求解2. #include "stdafx.h"3. #include "maxheap.h"4. #include <iostream>5. usingnamespace std; 6.7.constintn = 4; 8.9.classbbnode; 10.11. template<c

31、lasstype>12. classheapnode13.14. template<classtype>15. friendvoidaddlivenodemaxheap<heapnode<type>>& h、bbnode *e、type wt、boo l ch、intlev;16. template<classtype>17. friendtype maxloadingtype w、type c、intn、 intbestx;18. public:19. operator typeconst returnuweight;20. pr

32、ivate:21. bbnode *ptr;/ 指向活节点在子集树中相应节点的指针22. type uweight;/ 活节点优先级 上界 23. intlevel;/ 活节点在子集树中所处的层序号24.;25.26.classbbnode27.28. template<classtype>29. friendvoidaddlivenodemaxheap<heapnode<type>>& h、bbnode *e、type wt、boolch、intlev;30.template<classtype>31.friendtype maxloa

33、dingtype w、type c、intn、 intbestx;32.friendclassadjacencygraph;33.精品学习资料精选学习资料 - - - 欢迎下载34.private:35.bbnode *parent;/ 指向父节点的指针36.boollchild;/ 左儿子节点标识37.;38.39.template<classtype>40.voidaddlivenodemaxheap<heapnode<type>>& h、bbnode *e、type wt、boolch、intle v;41.42. template<cl

34、asstype>43. type maxloadingtype w、type c、intn、intbestx; 44.45.46.intmain47.48.floatc = 70;49.floatw = 0、20、10、26、15;/ 下标从 1 开头50. intxn+1;51. floatbestw; 52.53. cout<<" 轮船载重为： " <<c<<endl;54. cout<<" 待装物品的重量分别为：" <<endl;55. for inti=1; i<=n; i+

35、56.57.cout<<wi<<" "58.59. cout<<endl;60. bestw = maxloadingw、c、n、x; 61.62.cout<<" 分支限界挑选结果为:" <<endl;63.for inti=1; i<=4; i+64.65.cout<<xi<<" "66.67. cout<<endl;68. cout<<" 最优装载重量为：" <<bestw<<endl; 69.70.return0;71. 72.73. / 将活节点加入到表示活节点优先队列的最