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