实验六_分支限界法.doc

算法分析与设计实验报告 学号姓名班级上课地点教师上课时间实验六 分支限界法1. 实验目的1.1掌握分支限界法的设计思想；1.2理解分支限界法的剪枝搜索策略；1.3掌握分支限界法的算法框架；1.4学会利用分支限界法解决实际问题。2. 实验环境2.1 Eclipse2.2 Window XP3. 实验内容3.1装载问题3.2旅行售货员问题4. 教师批改意见签字：日期：成绩实验报告细表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 booleann+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=n;i+)if(bestxi)System.out.print(wi+ );count+;bestxi=false;System.out.println();if(n-count!=0)System.out.println(第二艘船可载重：+maxLoading(w,c2,n-count,bestx);System.out.print(第二艘船装载的货物为：);for(int i=1;i=n-count;i+)if(bestxi)System.out.print(wi+ );elseSystem.out.println(只需第一艘船便能装载完所有货物);/输入货物数量private static int inputN()n=scan.nextInt();if(n=0)System.out.println(货物数量有误，请重新输入！);System.out.print(n=);n=scan.nextInt();inputN();return n;/输入第一艘船的载重量private static int inputC1()c1=scan.nextInt();if(c1=0)System.out.println(第一艘船的载重量输入有误，请重新输入！);System.out.print(c1=);c1=scan.nextInt();inputC1();return c1;/输入第二艘船的载重量private static int inputC2()c2=scan.nextInt();if(c2=0)System.out.println(第二艘船的载重量输入有误，请重新输入！);System.out.print(c2=);c2=scan.nextInt();inputC2();return c2;/输入第一艘船的载重量private static int inputW()w=new intn+1;for(int i=1;i=n;i+)wi=scan.nextInt();for(int i=1;i=n;i+)if(wi=0)System.out.println(第i个货物的重量输入有误，请重新输入！);System.out.print(wi=);wi=scan.nextInt();inputW();return w;static class BBnodeBBnode parent;/父结点boolean leftChild;/左儿子标记/构造方法BBnode(BBnode par,boolean ch)parent=par;leftChild=ch;static class HeapNodeBBnode 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)/优先队列式分支限界法，返回最优载重量，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 intn+1;rn=0;/定义剩余集装箱重量for(int j=n-1;j0;j-)rj=rj+1+wj+1;/搜索子集空间树while(i!=n+1)/非叶结点/检查当前扩展的儿子结点if(ew+wi0;j-)bestxj=e.leftChild;e=e.parent;return ew;class comp implements Comparatorpublic int compare(HeapNode o1,HeapNode o2)int dif=o1.uweight-o2.uweight;if(dif0)return -1;if(dif=0)return 0;return 1;1.3 实验结论1.4 心得体会 很大一部分是参考别人的2旅行售货员问题2.1 算法设计思想 由于要找的是最小费用旅行售货员回路，所以选用最小堆表示活结点优先队列。最小堆中元素的类型为HeapNode。该类型结点包含域x，用于记录当前解；s表示结点在排列树中的层次，从排列树的根结点到该结点的路径为x0:s，需要进一步搜索的顶点的是xs+1:n-1。cc表示当前费用，lcost是子树费用的下界，rcost是xs:n-1中顶点最小出边费用和具体算法描述如下。算法开始时创建一个最小堆，用于表示活结点优先队列。堆中每个结点的lcost值是优先队列的优先级。接着算法计算出图中每个顶点的最小费用出边并用minout记录。如果所给的有向图中某个顶点没有出边，则该图不可能有回路，算法即告结束。如果每个节点都有出边，则根据计算出的minout做算法初始化。算法的第1个扩展结点是排列树中根节点的唯一儿子结点。该结点处，已确定的回路中唯一顶点为顶点1。因此，初始时有s=0，x0=1，x1:n-1=(2,3, ,n)，cc=0且rcost=。算法中用bestc记录当前最优值。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(请输入顶点个数(010)：n=);String line=s.nextLine();/输入顶点个数 n=Integer.parseInt(line); a=new floatnn; /邻接矩阵int vv=new intn; /输入邻接矩阵System.out.println(请输邻接矩阵：);for(int i=0;in;i+) line=s.nextLine(); String sArray=line.split( ); for(int j=0;jsArray.length;j+) aij=Integer.parseInt(sArrayj); /若两点间无通路则权值为无穷大for(int i=0;in;i+)for(int j=0;jn;j+)if(aij=0)aij=Float.MAX_VALUE;/输出最小耗费System.out.println(最小耗费为:+bbTsp(vv); static float a;/图的邻接矩阵 SuppressWarnings(rawtypes)private static class HeapNode implements Comparable float lcost,/子树费用下界 cc,/当前费用 rcost;/Xs:n-1中顶点最小出边费用和 int s;/根节点到当前结点的路径为X0:s int x;/需要进一步搜索的结点是xs+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(lcostxlc) return -1; if(lcost=xlc) return 0; return 1; /优先队列分支限界搜索算法public static int bbTsp(int v) int n=v.length; MinHeap heap=new MinHeap(100); float minOut=new floatn;/minOuti是顶点i的最小出边费用 float minSum=0;/最小出边费用和 /计算最小出边费用和 for(int i=0;in;i+) float min=Float.MAX_VALUE; for(int j=0;jn;j+) if(aijFloat.MAX_VALUE & aijmin) min=aij;/有回路 if(min=Float.MAX_VALUE) return -1;/无回路 minOuti=min; minSum+=min; /更新最小出边费用和 /初始化 int x=new intn; for(int i=0;in;i+) xi=i; HeapNode enode=new HeapNode(0,0,minSum,0,x); float bestc=Float.MAX_VALUE; /搜索排列空间树 while(enode!=null&enode.sn-1) /非叶结点 x=enode.x; if(enode.s=n-2)/叶子结点 /当前扩展结点是叶子结点的父结点/再加2条边构成回路/所构成回路是否优于当前最优解if(axn-2xn-1Float.MAX_VALUE& axn-11Float.MAX_VALUE| bestc=Float.MAX_VALUE)/当前最优解还不存在的情况 /找到费用更小的回路 bestc=enode.cc+axn-2xn-1+axn-10; enode.cc=bestc; enode.lcost=bestc; enode.s+; heap.put(enode); else /产生当前扩展结点的儿子结点 for(int i=enode.s+1;in;i+) if(axenode.sxiFloat.MAX_VALUE) /可行儿子结点float cc=enode.cc+axenode.sxi; float rcost=enode.rcost-minOutxenode.s; float b=cc+rcost; /下界if(bbestc) /子树可能含有最优解，结点插入最小堆int xx=new intn; for(int j=0;jn;j+) xxj=xj; xxenode.s+1=xi; xxi=xenode.s+1; HeapNode node=new HeapNode(b,cc,rcost,enode.s+1,xx); heap.put(node); /取下一个扩展结点enode=(HeapNode)heap.removeMin(); /复制最优解到v0:n-1for(int i=0;in;i+) vi=xi;return (int)bestc; /构造最小堆 public static class MinHeap private HeapNode heapArray; /堆容器 private int maxSize; /堆的最大容量 private int currentSize=0; /堆大小 /构造方法 public MinHeap(int _maxSize) maxSize=_maxSize; heapAr