實驗五優(yōu)先隊列式分支限界法解裝載問題

1、實驗五優(yōu)先隊列式分支限界法解裝載問題09電信實驗班I09660118徐振飛一、實驗題目實現(xiàn)書本P201所描述的優(yōu)先隊列式分支限界法解裝載問題二、實驗?zāi)康?）掌握并運用分支限界法基本思想2）運用優(yōu)先隊列式分支限界法實現(xiàn)裝載問題3）比較隊列式分支限界法和優(yōu)先隊列式分支限界法的優(yōu)缺點三、實驗內(nèi)容和原理（1）實驗內(nèi)容有一批共n個集裝箱要裝上2艘載重量分別為c1和c2的輪船，nwic1c2其中集裝箱i的重量為Wi，且i1，要求確定可否有一個合理的裝載方案可將這n個集裝箱裝上這2艘輪船。若是有，請給出方案。（2）實驗原理解裝載問題的優(yōu)先隊列式分支限界法用最大優(yōu)先隊列儲藏活結(jié)點表?；罱Y(jié)點x在優(yōu)先隊列中的優(yōu)先

2、級定義為從根結(jié)點到結(jié)點x的路徑所相應(yīng)的載重量再加上節(jié)余集裝箱的重量之和。優(yōu)先隊列中優(yōu)先級最大的活結(jié)點成為下一個擴展結(jié)點。優(yōu)先隊列中活結(jié)點x的優(yōu)先級為x.uweight。以結(jié)點x為根的子樹中所有結(jié)點相應(yīng)的路徑的載重量不超過x.uweight。子集樹中葉結(jié)點所相應(yīng)的載重量與其優(yōu)先級相同。因此在優(yōu)先隊列式分支限界法中，一旦有一個葉結(jié)點成為當前擴展結(jié)1點，則可以斷言該葉結(jié)點所相應(yīng)的解即為最優(yōu)解，此時停止算法。上述策略可以用兩種不相同方式來實現(xiàn)。第一種方式在結(jié)點優(yōu)先隊列的每一個活結(jié)點中保存從解空間樹的根結(jié)點到該活結(jié)點的路徑，在算法確定了達到最優(yōu)值的葉結(jié)點時，就在該葉結(jié)點處同時獲取相應(yīng)的最優(yōu)解。第二種方式

3、在算法的搜尋進度中保存當前已構(gòu)造出的部分解空間樹，在算法確定了達到最優(yōu)值的葉結(jié)點時，就可以在解空間樹中從該葉結(jié)點開始向根結(jié)點回溯，構(gòu)造出相應(yīng)的最優(yōu)解。在下面的算法中，采用第二種方式。四、源程序importjava.util.Comparator;importjava.util.Iterator;importjava.util.PriorityQueue;importjava.util.Scanner;publicclasstest5publicvoidaddLiveNode(PriorityQueueH,bbnodeE,intwt,booleanch,intlev)bbnodeb=newbbn

4、ode(E,ch);HeapNodeN=newHeapNode(b,wt,lev);H.add(N);publicintmaxLoading(intw,intc,intn,booleanbestx)PriorityQueueH=newPriorityQueue(1000,newcomp();/*生成最大堆*/intr=newintn+1;rn=0;for(intj=n-1;j0;j-)rj=rj+1+wj+1;inti=1;bbnodeE=newbbnode(null,false);intEw=0;while(i!=n+1)if(Ew+wi0;j-)bestxj=E.Lchild;E=E.pa

5、rent;returnEw;publicstaticvoidmain(Stringargs)System.out.println(請輸入物品總數(shù)：);Scannersc1=newScanner(System.in);intn=sc1.nextInt();intw=newintn+1;System.out.println(請輸入物品重量：);Scannersc2=newScanner(System.in);for(inti=1;i=n;i+)wi=sc2.nextInt();System.out.println(請輸入箱子重量：);Scannersc3=newScanner(System.in)

6、;intc1=sc3.nextInt();intc2=sc3.nextInt();booleanbestx=newboolean100;test5t=newtest5();/辦理第一個箱子System.out.println(first:+t.maxLoading(w,c1,n,bestx);System.out.print(可裝重為：);intcount=0;for(inti=1;i=n;i+)if(bestxi)count+;System.out.print(wi+);/*輸出一個可行方案*/System.out.println();/*辦理第二個箱子*/intm=n-count;3int

7、ww=newintm+1;intk=1;for(inti=1;i=n;i+)if(!bestxi)wwk=wi;k+;bestxi=false;System.out.println();System.out.println(second:+t.maxLoading(ww,c2,m,bestx);System.out.print(可裝重為：);for(inti=1;i=m;i+)if(bestxi)System.out.print(wwi+);/*輸出一個可行方案*/*堆結(jié)點類*/classHeapNodebbnodeptr;intuweight;intlevel;publicHeapNode(

8、)publicHeapNode(bbnodeptr,intuweight,intlevel)this.ptr=ptr;this.uweight=uweight;this.level=level;publicStringtoString()return+this.uweight;classbbnodebbnodeparent;booleanLchild;publicbbnode(bbnodenode,booleanch)this.parent=node;this.Lchild=ch;/定義比較器類4classcompimplementsComparatorOverridepublicintcom

9、pare(HeapNodeo1,HeapNodeo2)intdif=o1.uweight-o2.uweight;if(dif0)return-1;elseif(dif=0)return0;elsereturn1;五、實驗結(jié)果和解析a.輸入格式說明：1）第一輸入物品總數(shù)量2）第二欄輸入所有物品重量3）第三欄輸入2個箱子的重量b.輸出格式說明：1）第一輸出first的字樣，后邊的數(shù)字表示第一個箱子所能裝載的最大重量，緊接著的一行輸出一種可以選擇裝載的方案2）Second字樣后邊的數(shù)字表示第二個箱子所能裝載的最大重量，緊接著的一行輸出一種可行方案5經(jīng)過解析，上述結(jié)果正確。六、實驗心得和領(lǐng)悟經(jīng)過實驗，

10、認識了分支限界法的基本思想。掌握了利用優(yōu)先隊列式分支限界法實現(xiàn)詳盡的裝載問題。由于本次實驗利用java.util包下的PriorityQueue代替算法中的最大堆，免去了編寫實現(xiàn)最大堆的程序代碼（但這其實不表示我不會編寫最大堆程序，在此次實驗中，最大堆的實現(xiàn)其實不是主要部分），因此本次實驗實現(xiàn)的相對順利。存在的問題及解析：在此例中最合理的裝載方法是第一個箱子裝載重量為：1050的6物品，第二個箱子裝載重量為2020的物品。解析：由于程序中先裝載第一個箱子，爾后再裝載第二個箱子；而分支限界法一旦擴展結(jié)點到達葉子結(jié)點時，程序便停止退出。因此在此例中當?shù)谝粋€箱子裝滿后（此時重量為102030的物品已被裝走），余下的