实验五、优先队列式分支限界法解装载问题

实验五 优先队列式分支限界法解装载问题

09电信实验班 I09660118 徐振飞

1、实验题目

实现书本P201所描述的优先队列式分支限界法解装载问题

2、实验目的

（1）掌握并运用分支限界法基本思想

（2）运用优先队列式分支限界法实现装载问题

（3）比较队列式分支限界法和优先队列式分支限界法的优缺点

三、实验内容和原理

（1）实验内容

有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为Wi，且，要求确定是否有一个合理的装载方案可将这n个集装箱装上这2艘轮船。如果有，请给出方案。

（2）实验原理

解装载问题的优先队列式分支限界法用最大优先队列存储活结点表。活结点x在优先队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和。优先队列中优先级最大的活结点成为下一个扩展结点。优先队列中活结点x的优先级为x.uweight。以结点x为根的子树中所有结点相应的路径的载重量不超过x.uweight。子集树中叶结点所相应的载重量与其优先级相同。因此在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解，此时终止算法。

上述策略可以用两种不同方式来实现。第一种方式在结点优先队列的每一个活结点中保存从解空间树的根结点到该活结点的路径，在算法确定了达到最优值的叶结点时，就在该叶结点处同时得到相应的最优解。第二种方式在算法的搜索进程中保存当前已构造出的部分解空间树，在算法确定了达到最优值的叶结点时，就可以在解空间树中从该叶结点开始向根结点回溯，构造出相应的最优解。在下面的算法中，采用第二种方式。

4、源程序

import java.util.Comparator;

import java.util.Iterator;

import java.util.PriorityQueue;

import java.util.Scanner;

public class test5 {

public void addLiveNode(PriorityQueue 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[] 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);

HeapNode N;

N=H.poll();

i = N.level;

E = N.ptr;

Ew = N.uweight - r[i-1];

}

//构造最优解

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("请输入物品总数：");

Scanner sc1 = new Scanner(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();

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(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("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]+" "); /*输出一个可行方案*/

}

}

}

}

/*堆结点类*/

class HeapNode{

bbnode ptr;

int uweight;

int level;

public HeapNode(){}

public HeapNode(bbnode 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;

}

}

//定义比较器类

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;

}

else

{

return 1;

}

}

}

5、实验结果和分析

a.输入格式说明：

（1）首先输入物品总数量

（2）第二栏输入所有物品重量

（3）第三栏输入2个箱子的重量

b.输出格式说明：

（1）首先输出first的字样，后面的数字表示第一个箱子所能装载的最大重量，紧接着的一行输出一种可以选择装载的方案

（2）Second字样后面的数字表示第二个箱子所能装载的最大重量，紧接着的一行输出一种可行方案

经过分析，上述结果正确。

6、实验心得和体会

通过实验，了解了分支限界法的基本思想。掌握了利用优先队列式分支限界法实现具体的装载问题。由于本次实验利用java.util包下的PriorityQueue代替算法中的最大堆，免去了编写实现最大堆的程序代码（但这并不表示我不会编写最大堆程序，在这次实验中，最大堆的实现并不是主要部分），所以本次实验实现的相对顺利。

存在的问题及分析：

在此例中最合理的装载方法是第一个箱子装载重量为：10 50的物品，第二个箱子装载重量为20 20的物品。

分析：由于程序中先装载第一个箱子，然后再装载第二个箱子；而分支限界法一旦扩展结点到达叶子结点时，程序便终止退出。所以在此例中当第一个箱子装满后（此时重量为10 20 30的物品已被装走），余下的物品重量只有 50 20 两个，因此第二个箱子无法装满。

解决方法：可以对程序稍作改变，寻找所有可行的装载方案，然后利用装满率（装载量/箱子重量）来判断那种方案是最优的装载方案。这样做必定会增加程序的时间和空间复杂度，当数据量很大时，不适合（此时可以改变输入数据的顺序去试探装载方案，然后人为确定一个相对最有的装载方案）。