0034算法筆記——【分支限界法】最優(yōu)裝載問(wèn)題

1、問(wèn)題描述有一批共個(gè)集裝箱要裝上2 艘載重量分別為c1 和 c2 的輪船，其中集裝箱 i 的重量為 wi，且裝載問(wèn)題要求確定是否有一個(gè)合理的裝載方案可將這個(gè)集裝箱裝上這2 艘輪船；假如有，找出一種裝載方案；簡(jiǎn)單證明：假如一個(gè)給定裝載問(wèn)題有解，就采納下面的策略可得到最優(yōu)裝載方案；(1) 第一將第一艘輪船盡可能裝滿；(2) 將剩余的集裝箱裝上其次艘輪船；1、隊(duì)列式分支限界法求解在算法的循環(huán)體中，第一檢測(cè)當(dāng)前擴(kuò)展結(jié)點(diǎn)的左兒子結(jié)點(diǎn)是否為可行結(jié)點(diǎn)；假如是就將其加入到活結(jié)點(diǎn)隊(duì)列中；然后將其右兒子結(jié)點(diǎn)加入到活結(jié)點(diǎn)隊(duì)列中 右兒子結(jié)點(diǎn)肯定是可行結(jié)點(diǎn)；2 個(gè)兒子結(jié)點(diǎn)都產(chǎn)生后，當(dāng)前擴(kuò)展結(jié)點(diǎn)被舍棄；活結(jié)點(diǎn)隊(duì)列中的隊(duì)首元

2、素被取出作為當(dāng)前擴(kuò)展結(jié)點(diǎn)，由于隊(duì)列中每一層結(jié)點(diǎn)之后都有一個(gè)尾部標(biāo)記-1，故在取隊(duì)首元素時(shí)，活結(jié)點(diǎn)隊(duì)列肯定不空；當(dāng)取出的元素是-1 時(shí)，再判定當(dāng)前隊(duì)列是否為空；假如隊(duì)列非空，就將尾部標(biāo)記-1 加入活結(jié)點(diǎn)隊(duì)列，算法開頭處理下一層的活結(jié)點(diǎn)；節(jié)點(diǎn)的左子樹表示將此集裝箱裝上船，右子樹表示不將此集裝箱裝上船；設(shè) bestw 是當(dāng)前最優(yōu)解； ew 是當(dāng)前擴(kuò)展結(jié)點(diǎn)所相應(yīng)的重量；r 是剩余集裝箱的重量；就當(dāng)ew+r<bestw時(shí)，可將其右子樹剪去，因 為此時(shí)如要船裝最多集裝箱，就應(yīng)當(dāng)把此箱裝上船；另外，為了確保右子樹勝利剪枝，應(yīng)當(dāng)在算法每一次進(jìn)入左子樹的時(shí)候更新bestw 的值；為了在算法終止后能便利地構(gòu)

3、造出與最優(yōu)值相應(yīng)的最優(yōu)解，算法必需儲(chǔ)備相應(yīng)子集樹中從活結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑；為此目的，可在每個(gè)結(jié)點(diǎn)處設(shè)置指向其父結(jié)點(diǎn)的指針，并設(shè)置左、右兒子標(biāo)志；找到最優(yōu)值后，可以依據(jù)parent回溯到根節(jié)點(diǎn)，找到最優(yōu)解；算法詳細(xì)代碼實(shí)現(xiàn)如下：1 、queue.hcppview plaincopy1. #include<iostream>2. usingnamespace std; 3.4. template< classt>5. classqueue 6.7. public:8. queueintmaxqueuesize=50;9. queuedelete queue;10. bool

4、isemptyconst 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;17. voidoutputostream& outconst ;18. intlengthreturnrear-fro

5、nt;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<classt >35. t queue<t>:topconst36.37.if isempty38.39. cou

6、t<<"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"<<endl;51. return0;52.53.elsereturnqueuerear;54. 55.56. templa

7、te<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. 67.68. template<classt>69. queue<t>& queue<t>:addleftconstt&

8、 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>& queue<t> :deletet & x82.83. if isemptycout<<"queue:no eleme

9、ntdelete"<<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%maxsize;i>=front+1%maxsize;i-97. out<<queuei;98. 99.100. template<classt>1

10、01. ostream& operator << ostream& out,constqueue<t>& x102. x.outputout;returnout;2 、6d3-1.cppcppview plaincopy1. / 裝載問(wèn)題隊(duì)列式分支限界法求解2. #include "stdafx.h"3. #include "queue.h"4. #include <iostream>5. usingnamespace std; 6.7.constintn = 4;8.9. template&l

11、t;classtype>10. classqnode11.12. template<classtype>13. friendvoidenqueuequeue<qnode<type>*>&q,type wt,inti,intn,type bestw,q node<type>*e,qnode<type> *&beste,intbestx,boolch;14.15. template<classtype>16. friendtype maxloadingtype w,type c,intn, intbest

12、x; 17.18. private:19. qnode *parent;/ 指向父節(jié)點(diǎn)的指針20. boollchild;/ 左兒子標(biāo)識(shí)21. type weight;/ 節(jié)點(diǎn)所相應(yīng)的載重量22.;23.24. template<classtype>25. voidenqueuequeue<qnode<type>*>&q,type wt,inti,intn,type bestw,qnode<type>* e,qnode<type> *&beste,intbestx,boolch;26.27. template<c

13、lasstype>28. type maxloadingtype w,type c,intn,intbestx; 29.30.intmain31.32.floatc = 70;33.floatw = 0,20,10,26,15;/ 下標(biāo)從 1 開頭34. intxn+1;35. floatbestw; 36.37. cout<<" 輪船載重為： " <<c<<endl;38. cout<<" 待裝物品的重量分別為：" <<endl;39. for inti=1; i<=n; i+40

14、.41.cout<<wi<<" "42.43. cout<<endl;44. bestw = maxloadingw,c,n,x; 45.46.cout<<" 分支限界挑選結(jié)果為:" <<endl;47.for inti=1; i<=4; i+48.49.cout<<xi<<" "50.51. cout<<endl;52. cout<<" 最優(yōu)裝載重量為：" <<bestw<<e

15、ndl; 53.54.return0;55. 56.57. / 將活節(jié)點(diǎn)加入到活節(jié)點(diǎn)隊(duì)列q 中58. template<classtype>59. voidenqueuequeue<qnode<type>*>&q,type wt,inti,intn,type bestw,qnode<type>* e,qnode<type> *&beste,intbestx,boolch60.61.if i = n/ 可行葉節(jié)點(diǎn)62.63.if wt = bestw64.65. / 當(dāng)前最優(yōu)裝載重量66. beste = e;67. b

16、estxn = ch;68.69.return;70.71. / 非葉節(jié)點(diǎn)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. 79.80. template<classtype>81. type maxloadingtype w,type c,intn,intbestx82. / 隊(duì)列式分支限界法，返回最優(yōu)裝載重量，bestx返回最優(yōu)解83./ 初始化84.queue&l

17、t;qnode<type>*> q;/ 活節(jié)點(diǎn)隊(duì)列85.q.add0;/ 同層節(jié)點(diǎn)尾部標(biāo)識(shí)86.inti = 1;/ 當(dāng)前擴(kuò)展節(jié)點(diǎn)所處的層87.type ew = 0,/ 擴(kuò)展節(jié)點(diǎn)所相應(yīng)的載重量88.bestw = 0,/ 當(dāng)前最優(yōu)裝載重量89.r = 0;/ 剩余集裝箱重量90.91.for intj=2; j<=n; j+92.93.r += wj;94.95.96.qnode<type> *e = 0,/ 當(dāng)前擴(kuò)展節(jié)點(diǎn)97.*beste;/ 當(dāng)前最優(yōu)擴(kuò)展節(jié)點(diǎn)98.99./ 搜尋子集空間樹100.while true 101.102./ 檢查左兒子節(jié)點(diǎn)1

18、03.type wt = ew + wi;104.if wt <= c/ 可行節(jié)點(diǎn)105.106.if wt>bestw107.108.bestw = wt;109.110.enqueueq,wt,i,n,bestw,e,beste,bestx,true;111.112.113./ 檢查右兒子節(jié)點(diǎn)114.if ew+r>bestw115.116.enqueueq,ew,i,n,bestw,e,beste,bestx,false;117.118.q.deletee;/ 取下一擴(kuò)展節(jié)點(diǎn)119.120.if.e/ 同層節(jié)點(diǎn)尾部121.122.ifq.isempty123.124.b

19、reak ;125.126.q.add0;/ 同層節(jié)點(diǎn)尾部標(biāo)識(shí)127.q.deletee;/取下一擴(kuò)展節(jié)點(diǎn)128.i+;/進(jìn)入下一層129.r-=wi;/剩余集裝箱重量130.131.ew =e->weight;/ 新擴(kuò)展節(jié)點(diǎn)所對(duì)應(yīng)的載重量132.133.134./ 構(gòu)造當(dāng)前最優(yōu)解135.for intj=n-1; j>0; j-136.137.bestxj = beste->lchild;138.beste = beste->parent;139.140.returnbestw;141.程序運(yùn)行結(jié)果如圖：2、優(yōu)先隊(duì)列式分支限界法求解解裝載問(wèn)題的優(yōu)先隊(duì)列式分支限界法用

20、最大優(yōu)先隊(duì)列 儲(chǔ)備活結(jié)點(diǎn)表；活結(jié)點(diǎn) x 在優(yōu)先隊(duì)列中的優(yōu)先級(jí)定義為從根結(jié)點(diǎn)到結(jié)點(diǎn) x 的路徑所相應(yīng)的載重量再加上剩余集裝箱的重量之和；優(yōu)先隊(duì)列中優(yōu)先級(jí)最大的活結(jié)點(diǎn)成為下一個(gè)擴(kuò)展結(jié)點(diǎn)；以結(jié)點(diǎn)x 為根的子樹中全部結(jié)點(diǎn)相應(yīng)的路徑的載重量不超過(guò)它的優(yōu)先級(jí)；子集樹中葉結(jié)點(diǎn)所相應(yīng)的載重量與其優(yōu)先級(jí)相同；在優(yōu)先隊(duì)列式分支限界法中，一旦有一個(gè)葉結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，就可以斷言該葉結(jié)點(diǎn)所相應(yīng)的解即為最優(yōu)解；此時(shí)可終止算法；算法詳細(xì)代碼實(shí)現(xiàn)如下：1 、maxheap.hcppview plaincopy1. template<classt>2. classmaxheap 3.4. public:5.

21、maxheapintmaxheapsize = 10;6. maxheap delete heap;7. intsizeconst returncurrentsize; 8.9.t max10./ 查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,inta

22、rraysize; 22.23. private:24. intcurrentsize, maxsize;25. t *heap;/ element array 26.;27.28. template<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&l

23、t;t>& maxheap<t>:insertconstt& x38. / insert x into the max heap.39. ifcurrentsize = maxsize40.41.cout<<"no space."<<endl;42.return* this;43.44.45./查找新元素x 的位置46./ i初始為新葉節(jié)點(diǎn)的位置，逐層向上，查找最終位置47.inti = +currentsize;48.whilei .= 1 && x > heapi/249.50./ i不是根

24、節(jié)點(diǎn)，且其值大于父節(jié)點(diǎn)的值，需要連續(xù)調(diào)整51.heapi = heapi/2;/父節(jié)點(diǎn)下降52.i /= 2;/連續(xù)向上，搜尋正確位置53.54.55. 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. ifcurrentsi

25、ze = 064.65. cout<<"empty heap."<<endl;66. return* this;67.68.69. x = heap1;/刪除最大元素70. /重整堆71. t y = heapcurrentsize-;/取最終一個(gè)節(jié)點(diǎn)，從根開頭重整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指

26、向 i 的兩個(gè)孩子中較大者80. ifci < currentsize && heapci < heapci+181.82.ci+;83.84./ y的值大于等于孩子節(jié)點(diǎn)嗎？85.ify >= heapci86.87.break ;/是， i 就是 y 的正確位置，退出88.89.90./否，需要連續(xù)向下，重整堆91.heapi = heapci;/大于父節(jié)點(diǎn)的孩子節(jié)點(diǎn)上升92.i = ci;/向下一層，連續(xù)搜尋正確位置93.ci *= 2;94.95.96. heapi = y;97. return* this;98. 99.100. template<

27、;classt>101. voidmaxheap<t>:initializet a,intsize,intarraysize102. / initialize max heap to array a.103. delete heap;104. heap = a;105. currentsize = size;106. maxsize = arraysize; 107.108. /從最終一個(gè)內(nèi)部節(jié)點(diǎn)開頭，始終到根，對(duì)每個(gè)子樹進(jìn)行堆重整109. for inti = currentsize/2; i >= 1; i-110.111. t y = heapi;/子樹根節(jié)點(diǎn)元素

28、112. / find place to put y113. intc = 2*i;/ parent of 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

29、.127.128./ no129. heapc/2 = heapc;/ move child up130. c *= 2;/ move down a level131.132.heapc/2 = y;133.134.2 、6d3-2.cppcppview plaincopy1. / 裝載問(wèn)題優(yōu)先隊(duì)列式分支限界法求解2. #include "stdafx.h"3. #include "maxheap.h"4. #include <iostream>5. usingnamespace std; 6.7.constintn = 4; 8.9.cla

30、ssbbnode; 10.11. template<classtype>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

31、typeconst returnuweight;20. private:21. bbnode *ptr;/ 指向活節(jié)點(diǎn)在子集樹中相應(yīng)節(jié)點(diǎn)的指針22. type uweight;/ 活節(jié)點(diǎn)優(yōu)先級(jí) 上界 23. intlevel;/ 活節(jié)點(diǎn)在子集樹中所處的層序號(hào)24.;25.26.classbbnode27.28. template<classtype>29. friendvoidaddlivenodemaxheap<heapnode<type>>& h,bbnode *e,type wt,boolch,intlev;30.template<cla

32、sstype>31.friendtype maxloadingtype w,type c,intn, intbestx;32.friendclassadjacencygraph;33.34.private:35.bbnode *parent;/ 指向父節(jié)點(diǎn)的指針36.boollchild;/ 左兒子節(jié)點(diǎn)標(biāo)識(shí)37.;38.39.template<classtype>40.voidaddlivenodemaxheap<heapnode<type>>& h,bbnode *e,type wt,boolch,intle v;41.42. templat

33、e<classtype>43. type maxloadingtype w,type c,intn,intbestx; 44.45.46.intmain47.48.floatc = 70;49.floatw = 0,20,10,26,15;/ 下標(biāo)從 1 開頭50. intxn+1;51. floatbestw; 52.53. cout<<" 輪船載重為： " <<c<<endl;54. cout<<" 待裝物品的重量分別為：" <<endl;55. for inti=1; i<

34、;=n; i+56.57.cout<<wi<<" "58.59. cout<<endl;60. bestw = maxloadingw,c,n,x; 61.62.cout<<" 分支限界挑選結(jié)果為:" <<endl;63.for inti=1; i<=4; i+64.65.cout<<xi<<" "66.67. cout<<endl;68. cout<<" 最優(yōu)裝載重量為：" <<bestw<<endl; 69.70.return0;71. 72.73. / 將