《實(shí)驗(yàn)五、優(yōu)先隊(duì)列式分支限界法解裝載問題【參照內(nèi)容】》由會員分享，可在線閱讀，更多相關(guān)《實(shí)驗(yàn)五、優(yōu)先隊(duì)列式分支限界法解裝載問題【參照內(nèi)容】（7頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

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

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

3、結(jié)點(diǎn)時，就在該葉結(jié)點(diǎn)處同時得到相應(yīng)的最優(yōu)解。第二種方式在算法的搜索進(jìn)程中保存當(dāng)前已構(gòu)造出的部分解空間樹，在算法確定了達(dá)到最優(yōu)值的葉結(jié)點(diǎn)時，就可以在解空間樹中從該葉結(jié)點(diǎn)開始向根結(jié)點(diǎn)回溯，構(gòu)造出相應(yīng)的最優(yōu)解。在下面的算法中，采用第二種方式。 四、 源程序 import java.util.Comparator; import java.util.Iterator; import java.util.PriorityQueue; import java.util.Scanner; public class test5 { public void addLiveNode(Prior

4、ityQueue H,bbnode E,int wt,boolean ch,int lev){ bbnode b = new bbnode(E,ch); HeapNode N = new HeapNode(b, wt, lev); H.add(N); } public int maxLoading(int w[],int c,int n,boolean bestx[]){ PriorityQueue H = new PriorityQueue(1000,new comp()); /*生成最大堆*/ int[]

5、 r = new int[n+1]; r[n] = 0; for(int j=n-1;j>0;j--){ r[j] = r[j+1] + w[j+1]; } int i = 1; bbnode E = new bbnode(null,false); int Ew = 0; while(i!=n+1){ if(Ew+w[i]<=c){ addLiveNode(H, E, Ew+w[i]+r[i], true, i+1); } addLiveNode(H, E, Ew+r[i], false, i+1);

6、HeapNode N; N=H.poll(); i = N.level; E = N.ptr; Ew = N.uweight - r[i-1]; } //構(gòu)造最優(yōu)解 for(int j=n;j>0;j--){ bestx[j] = E.Lchild; E = E.parent; } return Ew; } public static void main(String[] args){ System.out.println("請輸入物品總數(shù)："); Scanner sc1 = new Scann

7、er(System.in); int n = sc1.nextInt(); int[] w = new int[n+1]; System.out.println("請輸入物品重量："); Scanner sc2 = new Scanner(System.in); for(int i=1;i<=n;i++){ w[i] = sc2.nextInt(); } System.out.println("請輸入箱子重量："); Scanner sc3 = new Scanner(System.in); int c1 = sc3.nextInt

8、(); int c2 = sc3.nextInt(); boolean[] bestx = new boolean[100]; test5 t = new test5(); //處理第一個箱子 System.out.println("first:"+t.maxLoading(w, c1, n, bestx)); System.out.print("可裝重為："); int count = 0; for(int i=1;i<=n;i++){ if(bestx[i]){ count++; System.out.print(

9、w[i]+" "); /*輸出一個可行方案*/ } } System.out.println(); /*處理第二個箱子*/ int m = n - count; int[] ww = new int[m+1]; int k = 1; for(int i=1;i<=n;i++){ if(!bestx[i]){ ww[k] = w[i]; k++; bestx[i] = false; } } System.out.println(); System.out.println("

10、second:"+t.maxLoading(ww, c2, m, bestx)); System.out.print("可裝重為："); for(int i=1;i<=m;i++){ if(bestx[i]){ System.out.print(ww[i]+" "); /*輸出一個可行方案*/ } } } } /*堆結(jié)點(diǎn)類*/ class HeapNode{ bbnode ptr; int uweight; int level; public HeapNode(){} public HeapNode(bbno

11、de ptr,int uweight,int level){ this.ptr = ptr; this.uweight = uweight; this.level = level; } public String toString(){ return ""+this.uweight; } } class bbnode{ bbnode parent; boolean Lchild; public bbnode(bbnode node,boolean ch){ this.parent = node; this.Lchild = ch;

12、 } } //定義比較器類 class comp implements Comparator{ @Override public int compare(HeapNode o1, HeapNode o2) { int dif = o1.uweight-o2.uweight; if(dif>0) { return -1; } else if(dif==0) { return 0; }

13、 else { return 1; } } } 五、 實(shí)驗(yàn)結(jié)果和分析 a.輸入格式說明： （1）首先輸入物品總數(shù)量 （2）第二欄輸入所有物品重量 （3）第三欄輸入2個箱子的重量 b.輸出格式說明： （1） 首先輸出first的字樣，后面的數(shù)字表示第一個箱子所能裝載的最大重量，緊接著的一行輸出一種可以選擇裝載的方案 （2） Second字樣后面的數(shù)字表示第二個箱子所能裝載的最大重量，緊接著的一行輸出一種可行方案 經(jīng)過分析，上述結(jié)果正確。 六、 實(shí)驗(yàn)心得和體會 通過實(shí)驗(yàn)，了解了分支限界

14、法的基本思想。掌握了利用優(yōu)先隊(duì)列式分支限界法實(shí)現(xiàn)具體的裝載問題。由于本次實(shí)驗(yàn)利用java.util包下的PriorityQueue代替算法中的最大堆，免去了編寫實(shí)現(xiàn)最大堆的程序代碼（但這并不表示我不會編寫最大堆程序，在這次實(shí)驗(yàn)中，最大堆的實(shí)現(xiàn)并不是主要部分），所以本次實(shí)驗(yàn)實(shí)現(xiàn)的相對順利。 存在的問題及分析： 在此例中最合理的裝載方法是第一個箱子裝載重量為：10 50的物品，第二個箱子裝載重量為20 20的物品。 分析：由于程序中先裝載第一個箱子，然后再裝載第二個箱子；而分支限界法一旦擴(kuò)展結(jié)點(diǎn)到達(dá)葉子結(jié)點(diǎn)時，程序便終止退出。所以在此例中當(dāng)?shù)谝粋€箱子裝滿后（此時重量為10 20 30的物品已被裝走），余下的物品重量只有 50 20 兩個，因此第二個箱子無法裝滿。 解決方法：可以對程序稍作改變，尋找所有可行的裝載方案，然后利用裝滿率（裝載量/箱子重量）來判斷那種方案是最優(yōu)的裝載方案。這樣做必定會增加程序的時間和空間復(fù)雜度，當(dāng)數(shù)據(jù)量很大時，不適合（此時可以改變輸入數(shù)據(jù)的順序去試探裝載方案，然后人為確定一個相對最有的裝載方案）。 7 題目a