《實驗五、優(yōu)先隊列式分支限界法解裝載問題【參照內(nèi)容】》由會員分享，可在線閱讀，更多相關(guān)《實驗五、優(yōu)先隊列式分支限界法解裝載問題【參照內(nèi)容】（7頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、
實驗五 優(yōu)先隊列式分支限界法解裝載問題
09電信實驗班 I09660118 徐振飛
一、 實驗題目
實現(xiàn)書本P201所描述的優(yōu)先隊列式分支限界法解裝載問題
二、 實驗?zāi)康?
（1） 掌握并運用分支限界法基本思想
（2） 運用優(yōu)先隊列式分支限界法實現(xiàn)裝載問題
（3）比較隊列式分支限界法和優(yōu)先隊列式分支限界法的優(yōu)缺點
三、實驗內(nèi)容和原理
（1）實驗內(nèi)容
有一批共n個集裝箱要裝上2艘載重量分別為c1和c2的輪船，其中集裝箱i的重量為Wi，且，要求確定是否有一個合理的裝載方案可將這n個集裝箱裝上這2艘輪船。如果有，請給出方案。
（2）實驗原理
解裝載問題的優(yōu)先隊列式分支限界法
2、用最大優(yōu)先隊列存儲活結(jié)點表。活結(jié)點x在優(yōu)先隊列中的優(yōu)先級定義為從根結(jié)點到結(jié)點x的路徑所相應(yīng)的載重量再加上剩余集裝箱的重量之和。優(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é)點成為當(dāng)前擴展結(jié)點，則可以斷言該葉結(jié)點所相應(yīng)的解即為最優(yōu)解，此時終止算法。
上述策略可以用兩種不同方式來實現(xiàn)。第一種方式在結(jié)點優(yōu)先隊列的每一個活結(jié)點中保存從解空間樹的根結(jié)點到該活結(jié)點的路徑，在算法確定了達(dá)到最優(yōu)值的葉
3、結(jié)點時，就在該葉結(jié)點處同時得到相應(yīng)的最優(yōu)解。第二種方式在算法的搜索進(jìn)程中保存當(dāng)前已構(gòu)造出的部分解空間樹，在算法確定了達(dá)到最優(yōu)值的葉結(jié)點時，就可以在解空間樹中從該葉結(jié)點開始向根結(jié)點回溯，構(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é)點類*/
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;
}
}
}
五、 實驗結(jié)果和分析
a.輸入格式說明：
（1）首先輸入物品總數(shù)量
（2）第二欄輸入所有物品重量
（3）第三欄輸入2個箱子的重量
b.輸出格式說明：
（1） 首先輸出first的字樣，后面的數(shù)字表示第一個箱子所能裝載的最大重量，緊接著的一行輸出一種可以選擇裝載的方案
（2） Second字樣后面的數(shù)字表示第二個箱子所能裝載的最大重量，緊接著的一行輸出一種可行方案
經(jīng)過分析，上述結(jié)果正確。
六、 實驗心得和體會
通過實驗，了解了分支限界
14、法的基本思想。掌握了利用優(yōu)先隊列式分支限界法實現(xiàn)具體的裝載問題。由于本次實驗利用java.util包下的PriorityQueue代替算法中的最大堆，免去了編寫實現(xiàn)最大堆的程序代碼（但這并不表示我不會編寫最大堆程序，在這次實驗中，最大堆的實現(xiàn)并不是主要部分），所以本次實驗實現(xiàn)的相對順利。
存在的問題及分析：
在此例中最合理的裝載方法是第一個箱子裝載重量為：10 50的物品，第二個箱子裝載重量為20 20的物品。
分析：由于程序中先裝載第一個箱子，然后再裝載第二個箱子；而分支限界法一旦擴展結(jié)點到達(dá)葉子結(jié)點時，程序便終止退出。所以在此例中當(dāng)?shù)谝粋€箱子裝滿后（此時重量為10 20 30的物品已被裝走），余下的物品重量只有 50 20 兩個，因此第二個箱子無法裝滿。
解決方法：可以對程序稍作改變，尋找所有可行的裝載方案，然后利用裝滿率（裝載量/箱子重量）來判斷那種方案是最優(yōu)的裝載方案。這樣做必定會增加程序的時間和空間復(fù)雜度，當(dāng)數(shù)據(jù)量很大時，不適合（此時可以改變輸入數(shù)據(jù)的順序去試探裝載方案，然后人為確定一個相對最有的裝載方案）。
7
題目a
實驗五、優(yōu)先隊列式分支限界法解裝載問題【參照內(nèi)容】
