实验六_分支限界法
算法分析与设计实验报告
实验报告细表
1装载问题
1.1 算法设计思想
解装载问题的优先队列式分支限界法用最大优先队列存储活结点表。活结点x在优
先队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和。优先队列中优先级最大的活结点成为下一个扩展结点。以结点x为根的子树中所有结点相应的路径的载重量不超过它的优先级。子集树中叶结点所相应的载重量与其优先级相同。在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。此时可终止算法。
1.2 程序源码
package lab06;
import java.util.Comparator; import java.util.PriorityQueue; import java.util.Scanner;
import lab06.FIFOBBLoading.HeapNode;
public class FIFOBBLoading {
static int n; //货物数量 static int c1; //第一艘船的载重量 static int c2; //第二艘船的载重量 static int []w; //货物重量的数组 static int bestw; //当前最优载重量 static boolean []bestx; //当前最最优解
static Scanner scan=new Scanner(System.in);
public static void main(String[] args) { //输入货物数量 System.out.print("请输入货物数量：n="); n=inputN(); bestx=new boolean[n+1]; //输入第一艘船的载重量 System.out.print("请输入第一艘船的载重量：c1="); c1=inputC1(); //输入第二艘船的载重量 System.out.print("请输入第二艘船的载重量：c2="); c2=inputC2();
//输入各个货物的重量 System.out.println("请输入各个货物的重量："); w=inputW(); System.out.println("第一艘船可载重："+maxLoading(w,c1,n,bestx)); int count=0; System.out.print("第一艘船装载的货物为："); for(int i=1;i
//输入货物数量
private static int inputN() { n=scan.nextInt(); if(n
//输入第一艘船的载重量 private static int inputC1()
{ c1=scan.nextInt(); if(c1
//输入第二艘船的载重量 private static int inputC2() { c2=scan.nextInt(); if(c2
//输入第一艘船的载重量 private static int[] inputW() { w=new int[n+1]; for(int i=1;i
static class BBnode { BBnode parent; //父结点 boolean leftChild; //左儿子标记 //构造方法 BBnode(BBnode par,boolean ch) { parent=par; leftChild=ch; } }
static class HeapNode { BBnode liveNode; int uweight; //活结点优先级(上界) int level; //活结点在子集树中所处的层序号 //构造方法 public HeapNode(BBnode node,int up,int lev) { liveNode=node; uweight=up; level=lev; } public boolean equals(Object x) { return uweight==((HeapNode) x).uweight; } }
private static void addLiveNode(PriorityQueue H,int up,int lev,BBnode par,boolean ch)
{ //将活结点加入到表示活结点优先队列的最大堆H中 BBnode b=new BBnode(par,ch); HeapNode node=new HeapNode(b,up,lev); H.add(node); }
public static int maxLoading(int [] ww,int c,int n,boolean[] bestx) { //优先队列式分支限界法，返回最优载重量， //生产最大堆 PriorityQueue H = new PriorityQueue(1000,new comp());
//初始化 n=w.length-1; BBnode e=new BBnode(null,false);
int i=1; 所处的层
int ew=0; 所相应的载重量
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]; //搜索子集空间树 while(i!=n+1) { //非叶结点 //检查当前扩展的儿子结点 if(ew+w[i]0;j--) { bestx[j]=e.leftChild;
//当前扩展结点//当前扩展结点//当前扩展结点
e=e.parent; } return ew; } }
class comp implements Comparator {
public int compare(HeapNode o1,HeapNode o2) { int dif=o1.uweight-o2.uweight; if(dif>0) return -1; if(dif==0) return 0; return 1; } }
1.3 实验结论
1.4 心得体会
很大一部分是参考别人的
2旅行售货员问题
2.1 算法设计思想
由于要找的是最小费用旅行售货员回路，所以选用最小堆表示活结点优先队列。最
小堆中元素的类型为HeapNode。该类型结点包含域x，用于记录当前解；s表示结点在排列
树中的层次，从排列树的根结点到该结点的路径为x[0:s]，需要进一步搜索的顶点的是x[s+1:n-1]。cc表示当前费用，lcost是子树费用的下界，rcost是x[s:n-1]中顶点最小出边费用和具体算法描述如下。
算法开始时创建一个最小堆，用于表示活结点优先队列。堆中每个结点的lcost值是优先队列的优先级。接着算法计算出图中每个顶点的最小费用出边并用minout记录。如果所给的有向图中某个顶点没有出边，则该图不可能有回路，算法即告结束。如果每个节点都有出边，则根据计算出的minout做算法初始化。算法的第1个扩展结点是排列树中根节点的唯一儿子结点。该结点处，已确定的回路中唯一顶点为顶点1。因此，初始时有s=0，x[0]=1，n
x[1:n-1]=(2,3, …,n)，cc=0且rcost=
∑minout[i]。算法中用bestc记录当前最优值。i=s
2.2 程序源码
package lab06;
import java.util.Scanner;
public class FIFOTsp { @SuppressWarnings("resource") public static void main(String args[]) { Scanner s=new Scanner(System.in); int n=0; //结点的个数 System.out.print("请输入顶点个数(0~10)：n="); String line=s.nextLine(); //输入顶点个数 n=Integer.parseInt(line); a=new float[n][n]; //邻接矩阵 int []vv=new int[n]; //输入邻接矩阵 System.out.println("请输邻接矩阵："); for(int i=0;i
//输出最小耗费 System.out.println("最小耗费为:"+bbTsp(vv)); }
static float [][]a; //图的邻接矩阵
@SuppressWarnings("rawtypes")
private static class HeapNode implements Comparable { float lcost, //子树费用下界 cc, //当前费用 rcost; //X[s:n-1]中顶点最小出边费用和 int s; //根节点到当前结点的路径为X[0:s] int []x; //需要进一步搜索的结点是x[s+1:n-1] //构造方法
HeapNode(float lc,float ccc,float rc,int ss,int []xx) { lcost=lc; cc=ccc; s=ss; x=xx;
}
public int compareTo(Object x) { float xlc=((HeapNode)x).lcost; if(lcost
//优先队列分支限界搜索算法 public static int bbTsp(int []v) { int n=v.length; MinHeap heap=new MinHeap(100); float []minOut=new float[n]; //minOut[i]是顶点i的最小出边费用
float minSum=0; //最小出边费用和
情况
//计算最小出边费用和 for(int i=0;i
if(min==Float.MAX_VALUE) { return -1; }
minOut[i]=min; minSum+=min;
//无回路
//更新最小出边费用和
//初始化
int []x=new int[n]; for(int i=0;i
HeapNode enode=new HeapNode(0,0,minSum,0,x); float bestc=Float.MAX_VALUE;
//搜索排列空间树
while(enode!=null&&enode.s
{
//找到费用更小的回路
bestc=enode.cc+a[x[n-2]][x[n-1]]+a[x[n-1]][0];
enode.cc=bestc;
enode.lcost=bestc;
enode.s++;
heap.put(enode);
}
}
else
{ //产生当前扩展结点的儿子结点
for(int i=enode.s+1;i
{
if(a[x[enode.s]][x[i]]
{
//可行儿子结点
float cc=enode.cc+a[x[enode.s]][x[i]];
float rcost=enode.rcost-minOut[x[enode.s]];
float b=cc+rcost; //下界
if(b
{
//子树可能含有最优解，结点插入最小堆
int []xx=new int[n];
for(int j=0;j
xx[j]=x[j];
xx[enode.s+1]=x[i];
xx[i]=x[enode.s+1];
HeapNode
HeapNode(b,cc,rcost,enode.s+1,xx);
heap.put(node);
}
}
}
}
//取下一个扩展结点
enode=(HeapNode)heap.removeMin();
}
//复制最优解到v[0:n-1]
for(int i=0;i
v[i]=x[i];
return (int)bestc;
}
//构造最小堆
public static class MinHeap
node=new
{
private HeapNode[] heapArray; //堆容器
private int maxSize; //堆的最大容量
private int currentSize=0; //堆大小
//构造方法
public MinHeap(int _maxSize)
{
maxSize=_maxSize;
heapArray=new HeapNode[maxSize];
currentSize=0;
}
//自上而下调整
public void filterDown(int start, int endOfHeap)
{
int i=start;
int j=2*i+1; //j是i的左子女位置
HeapNode temp=heapArray[i];
while(j
{ //检查是否到最后位置
if (j
&&heapArray[j].cc>heapArray[j+1].cc)
{
j++;
}
if (temp.cc
{ //小则不做调整
break;
}
else
{ //否则小者上移，i，j下降
heapArray[i]=heapArray[j];
i=j;
j=2*j+1;
}
}
heapArray[i]=temp;
}
//自下而上的调整:从结点start开始到0为止，自下向上比较，如果子女的值小于双亲结点的值则互相交换
public void filterUp(int start)
{
int j=start;
int i=(j-1)/2;
HeapNode temp=heapArray[j];
while(j>0)
{ //沿双亲结点路径向上直达根节点 if(heapArray[i].cc
}
else
{ //双亲结点值大，调整 heapArray[j]=heapArray[i]; j=i;
i=(i-1)/2;
}
heapArray[j]=temp; //回送 }
}
//插入结点
public void put(HeapNode node) {
HeapNode newNode=node;
heapArray[currentSize]=newNode; filterUp(currentSize);
currentSize++;
}//put
//删除堆中的最小值
public HeapNode removeMin()
{
HeapNode root=heapArray[0];
heapArray[0]=heapArray[currentSize - 1]; currentSize--;
filterDown(0,currentSize-1);
return root;
}
}
}
2.3 实验结论
2.4 心得体会 这次实验真的很难