算法分析与设计实验报告
学号姓名班级
上课地点教师上课时间
实验六分支限界法
1. 实验目的
1.1掌握分支限界法的设计思想；
1.2理解分支限界法的剪枝搜索策略；
1.3掌握分支限界法的算法框架；
1.4学会利用分支限界法解决实际问题。
2. 实验环境
2.1 Eclipse
2.2 Window XP
3. 实验内容
3.1装载问题
3.2旅行售货员问题
4. 教师批改意见
成绩
签字：
日期：
实验报告细表
1装载问题
1.1 算法设计思想
解装载问题的优先队列式分支限界法用最大优先队列存储活结点表。活结点x在优先队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和。优先队列中优先级最大的活结点成为下一个扩展结点。以结点x为根的子树中所有结点相应的路径的载重量不超过它的优先级。子集树中叶结点所相应的载重量与其优先级相同。在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。此时可终止算法。
1.2 程序源码
package lab06;
import https://www.doczj.com/doc/a33805250.html,parator;
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<=n;i++)
if(bestx[i])
{
System.out.print(w[i]+" ");
count++;
bestx[i]=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(bestx[i])
System.out.print(w[i]+" ");
}
else
System.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 int[n+1];
for(int i=1;i<=n;i++)
w[i]=scan.nextInt();
for(int i=1;i<=n;i++)
{
if(w[i]<=0)
{
System.out.println("第i个货物的重量输入有误，请重新输入！");
System.out.print("w[i]=");
w[i]=scan.nextInt();
inputW();
}
}
return w;
}
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中
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
//初始化
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]<=c)
//左儿子结点为可行结点
addLiveNode(H,ew+w[i]+r[i],i+1,e,true);
//右儿子结点总为可行结点
addLiveNode(H,ew+r[i],i+1,e,false);
//取下一扩展结点
HeapNode node=H.poll();
i=node.level;
e=node.liveNode;
ew=node.uweight-r[i-1];
}
//构造当前最优解
for(int j=n;j>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，x[1:n-1]=(2,3, …,n)，cc=0且rcost=
∑=n
s
i i out ][min 。算法中用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("请输入顶点个数(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 a[i][j]=Float.MAX_VALUE; //输出最小耗费 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 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 float[n]; //minOut[i]是顶点i的最小出边费用float minSum=0; //最小出边费用和 //计算最小出边费用和 for(int i=0;i { float min=Float.MAX_VALUE; for(int j=0;j { if(a[i][j] min=a[i][j]; //有回路 } if(min==Float.MAX_VALUE) { return -1; //无回路 } minOut[i]=min; minSum+=min; //更新最小出边费用和 } //初始化 int []x=new int[n]; for(int i=0;i { x[i]=i; } HeapNode enode=new HeapNode(0,0,minSum,0,x); float bestc=Float.MAX_VALUE; //搜索排列空间树 while(enode!=null&&enode.s { //非叶结点 x=enode.x; if(enode.s==n-2) //叶子结点 { //当前扩展结点是叶子结点的父结点 //再加2条边构成回路 //所构成回路是否优于当前最优解 if(a[x[n-2]][x[n-1]] a[x[n-1]][1] bestc==Float.MAX_VALUE) //当前最优解还不存在的情况 { //找到费用更小的回路 bestc=https://www.doczj.com/doc/a33805250.html,+a[x[n-2]][x[n-1]]+a[x[n-1]][0]; https://www.doczj.com/doc/a33805250.html,=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=https://www.doczj.com/doc/a33805250.html,+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 node=new 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 { 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<=endOfHeap) { //检查是否到最后位置 if (j &&heapArray[j].cc>heapArray[j+1].cc) { j++; } if (https://www.doczj.com/doc/a33805250.html,<=heapArray[j].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<=https://www.doczj.com/doc/a33805250.html,) { //双亲结点值小，不调整 break; } 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 心得体会 这次实验真的很难 分支限界法的研究与应用 摘要： 分支限界法与回溯法的不同:首先,回溯法的求解目标是找出解空间树中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出在某种意义下的最优解。其次，回溯法以深度优先的方式搜索解空间树，而分支限界法则一般以广度优先或以最小耗费优先的方式搜索解空间树。再者，回溯法空间效率高；分支限界法往往更“快”。 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 常见的分支限界法有：队列式分支限界法，按照队列先进先出原则选取下一个结点为扩展结点。栈式分支限界法，按照栈后进先出原则选取下一个结点为扩展结点。优先队列式分支限界法，按照规定的结点费用最小原则选取下一个结点为扩展结点（最采用优先队列实现）。 分支搜索法是一种在问题解空间上进行搜索尝试的算法。所谓分支是采用广度优先的策略国,依次搜索E-结点的所有分支,也就是所有的相邻结点。和回溯法一样,在生成的结点中,抛弃那些不满足约束条件的结点,其余结点加入活结点表。然后从表中选择一个结点作为下一个E-结点,断续搜索。 关键词： 分支限界法回溯法广度优先分支搜索法 目录 第1章绪论 (3) 1.1 分支限界法的背景知识 (3) 1.2 分支限界法的前景意义 (3) 第2章分支限界法的理论知识.................. 错误!未定义书签。 2.1 问题的解空间树 ............................................... 错误!未定义书签。 2.2 分支限界法的一般性描述 (6) 第3章作业分配问题 (7) 3.1 问题描述 (7) 3.2 问题分析 (7) 3.3 算法设计 (8) 3.4 算法实现 (10) 3.5 测试结果与分析 (12) 第4章结论 (13) 参考文献 (14) 实验四用分支限界法实现0-1背包问题 一.实验目的 1.熟悉分支限界法的基本原理。 2.通过本次实验加深对分支限界法的理解。 二.实验内容及要求 内容：?给定n种物品和一个背包。物品i的重量是w,其价值为v，背包容量为c。问应该如何选择装入背包的物品，使得装入背包中物品的总价值最大？ 要求：使用优先队列式分支限界法算法编程，求解0-1背包问题 三.程序列表 #inelude stack 实验五分支限界算法的应用 一、实验目的 1 ?掌握分支限界算法的基本思想、技巧和效率分析方法。 2?熟练掌握用分支限界算法的基本步骤和算法框架，FIFO搜索，LIFO搜索，优先队列式搜索的思想。 3 ?学会利用分支限界算法解决实际问题。 二、算法问题描述 批处理作业调度问题：n个作业｛1,2,…,要在两台机器上处理，每个作业必须先由机器1处理，然后再由机器2处理，机器1处理作业i所需时间为ai，机器2处理作业i 所需时间为bi ( K i菊n，批处理作业调度问题(batch-job scheduling problem)要求确定这n个作业的最优处理顺序，使得从第1个作业在机器1上处理开始，到最后一个作业在机器2上处理结束所需时间最少。 注意：由于要从n个作业的所有排列中找出具有最早完成时间的作业调度，所以，批处理作业调度问题的解空间是一棵排列树，并且要搜索整个解空间树才 能确定最优解，因此，其时间性能是O(n!)。在搜索过程中利用已得到的最短完成时间进行剪枝，才能够提高搜索速度。 三、算法设计 批处理作业调度问题要从n个作业的所有排列中找出具有最小完成时间和 的作业调度，所以如图，批处理作业调度问题的解空间是一颗排列树 业集:1--'……：。以该节点为根的子树中所含叶节点的完成时间和可 表示为： 匸工代+工的 设|M|=r ，且L 是以节点E 为根的子树中的叶节点，相应的作业调度为 {pk,k=1,2,……n}，其中pk 是第k 个安排的作业。如果从节点 E 到叶节点L 的 路上，每一个作业pk 在机器1上完成处理后都能立即在机器 2上开始处理，即 从p 叶1开始，机器1没有空闲时间，则对于该叶节点 L 有： IX 二￡ [%+心+1)仏+切」諾 踰 也'+! 注：(n-k+1)t1pk,因 为是完成时间和，所以，后续的(n-k+1)个作业完成时间和都得算上tlpk 。 如果不能做到上面这一点，则si 只会增加，从而有： 。 类似地，如果从节点E 开始到节点L 的路上，从作业p 叶1开始，机器2没 有空闲 时间，贝 n 炳辽画(咏凡+卿 同理可知，s2是 的下界。由此得到在节点E 处相应子树中叶 在作业调度问相应的排列空间树中, 每一个节点E 都对应于一个已安排的作 』+山“ + 1)抵]二￡ 2 B 2 2 3 3 F 3 2 2 3 IG L P M 19 20 21 实验五分支限界法实现单源最短路径 一实验题目：分支限界法实现单源最短路径问题 二实验要求：区分分支限界算法与回溯算法的区别，加深对分支限界法的理解。 三实验内容：解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。算法从图G的源顶点s和空优先队列开始。 结点s被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。 四实验代码 #include 实验四分支限界法实现单源最短路径 09电信实验班I09660118 徐振飞 一、实验名称 实现书本P194页所描述的单源最短路径问题 二、实验目的 （1）掌握并运用分支限界法基本思想 （2）运用分支限界法实现单源最短路径问题 （3）区分分支限界算法与回溯算法的区别，加深对分支限界法理解三、实验内容和原理 （1）实验原理 解单源最短路径问题的优先队列式分支限界法用一极小堆（本次实验我采用java.util包中的优先队列类PriorityQueue来实现）来存储活结点表。其优先级是结点所对应的当前路长。算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。 （2）实验内容测试用例： 1 2 3 4 5 6 3 4 2 7 6 13 9 5 四、源程序 import java.util.*; public class ShortestPath { private int n; private double matrix[][] = null; private double minpath[]; public ShortestPath(int n) { this.n = n; matrix = new double[n+1][n+1]; minpath = new double[n+1]; 算法分析与设计实验报告第八次附加实验 for(int i=1;i 完整代码（分支限界法） //分支限界法求最优装载 #include 问题描述 给定无向图G=(V, E)，其中V是非空集合，称为顶点集；E 是V中元素构成的无序二元组的集合，称为边集，无向图中的边均是顶点的无序对，无序对常用圆括号“( )”表示。如果U∈V，且对任意两个顶点u，v∈U有(u, v)∈E，则称U是G的完全子图(完全图G就是指图G的每个顶点之间都有连边)。G的完全子图U是G的团当且仅当U不包含在G的更大的完全子图中。G的最大团是指G中所含顶点数最多的团。 如果U∈V且对任意u，v∈U有(u, v)不属于E，则称U是G 的空子图。G的空子图U是G的独立集当且仅当U不包含在G的更大的空子图中。G的最大独立集是G中所含顶点数最多的独立集。 对于任一无向图G=(V, E)，其补图G'=(V', E')定义为：V'=V，且(u, v)∈E'当且仅当(u, v)∈E。 如果U是G的完全子图，则它也是G'的空子图，反之亦然。因此，G的团与G'的独立集之间存在一一对应的关系。特殊地，U是G的最大团当且仅当U是G'的最大独立集。 例：如图所示，给定无向图G={V, E}，其中V={1,2,3,4,5}，E={(1,2), (1,4), (1,5),(2,3), (2,5), (3,5), (4,5)}。根据最大团(MCP)定义，子集{1,2}是图G的一个大小为2的完全子图，但不是一个团，因为它包含于G的更大的完全子图{1,2,5}之中。{1,2,5}是G的一个最大团。{1,4,5}和{2,3,5}也是G的最大团。右侧图是无向图G的补 图G'。根据最大独立集定义，{2,4}是G的一个空子图，同时也是G的一个最大独立集。虽然{1,2}也是G'的空子图，但它不是G'的独立集，因为它包含在G'的空子图{1,2,5}中。{1,2,5}是G'的最大独立集。{1,4,5}和{2,3,5}也是G'的最大独立集。 算法设计 最大团问题的解空间树也是一棵子集树。子集树的根结点是初始扩展结点，对于这个特殊的扩展结点，其cliqueSize的值为0。算法在扩展内部结点时，首先考察其左儿子结点。在左儿子结点处，将顶点i加入到当前团中，并检查该顶点与当前团中其它顶点之间是否有边相连。当顶点i与当前团中所有顶点之间都有边相连，则相应的左儿子结点是可行结点，将它加入到子集树中并插入活结点优先队列，否则就不是可行结点。 接着继续考察当前扩展结点的右儿子结点。当 upperSize>bestn时，右子树中可能含有最优解，此时将右儿子结点加入到子集树中并插入到活结点优先队列中。算法的while循环的终止条件是遇到子集树中的一个叶结点(即n+1层结点)成为当前扩展结点。 实验5 分支界限法解0-1背包问题一、实验要求 1．要求用分支界限法求解0-1背包问题； 2．要求交互输入背包容量，物品重量数组，物品价值数组； 3．要求显示结果。 二、实验仪器和软件平台 仪器：带usb接口微机 软件平台：WIN-XP + VC++ 三、源程序 #include "" #include float ub; //结点的上界值 }; //类Knap中的数据记录解空间树中的结点信息，以减少参数传递及递归调用所需的栈空间class Knap { private: struct node *front, //队列队首 *bestp,*first; //解结点、根结点 int *p,*w,n,c,*M;//背包价值、重量、物品数、背包容量、记录大小顺序关系 long lbestp;//背包容量最优解 public: void Sort(); Knap(int *pp,int *ww,int cc,int nn); ~Knap(); float Bound(int i,int cw,int cp);//计算上界限 node *nnoder(node *pa,int ba,float uub);//生成一个结点 ba=1生成左节点 ba=0生成右节点 void addnode(node *nod);//向队列中添加活结点 void deletenode(node *nod);//将结点从队列中删除 struct node *nextnode(); //取下一个节点 void display(); //输出结果 void solvebag(); //背包问题求解 }; //按物品单位重量的价值排序 void Knap::Sort() { 算法设计与分析 目录 算法设计与分析 (1) 第6章回溯与分支限界 (3) 6.1回溯法的设计技术 (3) 6.2用回溯法求解装载问题 (7) 6.3用回溯法求解n皇后问题 (9) 6.4用回溯法求解0-1背包问题 (11) 6.5用回溯法求解旅行商问题 (13) 6.6 分支限界法的设计技术 (15) 6.7 用分支限界法求问题的解 (15) 本章小结 (15) 参考文献 (16) 第6章回溯与分支限界 内容导读 回溯法(Back Tracking Algorithm)与分支限界法（Branch and Bound Algorithm）都是基本的算法设计策略，属于树的搜索技术的范畴。在使用这两种算法求解问题前，均需要把解空间规划成一棵解空间树，并且在求解过程中使用剪枝策略来提高搜索效率。 回溯法也称试探法，可以把它看成是一个在约束条件下对解空间树进行深度优先搜索的过程，并在搜索过程中剪去那些不满足条件的分支。当用回溯法搜索到解空间树的某个结点时，如果发现当前路径不满足约束条件或不是历史最优时，则放弃对该结点的子树的搜索，并逐层向其祖先结点返回。否则，进入该结点的子树，继续进行深度优先搜索。实质上，这是一个先根遍历解空间树的过程，只是这个棵树不是遍历前预先建立的，而是隐含在遍历过程当中的。 分支限界法则是以最小代价优先的方式在解空间树上进行搜索，它可以找出满足问题约束的一个可行解，或者是从满足约束条件的可行解中找出一个使得目标函数达到极值的最优解。这里的可行解在搜索树中表现为一条由根到叶子结点的路径，这条路径上权值的和为可行解的值。其中，最优解就是使可行解的值达到最优的那条路径。分支限界算法的核心思想就是增加更多的约束条件，剪掉更多的分支，当对当前的树结点进行扩展时，一次性产生其所有儿子结点，并抛弃那些不可能产生可行解或最优解的结点，即剪枝；对于留下的儿子结点，计算一个函数值（限界），然后选取一个最有利的结点继续进行扩展，使得搜索朝着最优解的分支推进。重复这个过程直到找到最优解或没有可扩展的结点。 问题描述 将n块电路板以最佳排列方式插入带有n个插槽的机箱中。n块电路板的不同排列方式对应于不同的电路板插入方案。设B={1, 2, …, n}是n块电路板的集合，L={N1, N2, …, Nm}是连接这n块电路板中若干电路板的m个连接块。Ni是B的一个子集，且Ni中的电路板用同一条导线连接在一起。设x表示n块电路板的一个排列，即在机箱的第i个插槽中插入的电路板编号是x[i]。x所确定的电路板排列Density (x)密度定义为跨越相邻电路板插槽的最大连线数。 例：如图，设n=8, m=5，给定n块电路板及其m个连接块：B={1, 2, 3, 4, 5, 6, 7, 8}，N1={4, 5, 6}，N2={2, 3}，N3={1, 3}，N4={3, 6}，N5={7, 8};其中两个可能的排列如图所示，则该电路板排列的密度分别是2，3。 左上图中，跨越插槽2和3,4和5，以及插槽5和6的连线数均为2。插槽6和7之间无跨越连线。其余插槽之间只有1条跨越连线。在设计机箱时，插槽一侧的布线间隙由电路板的排列的密度确定。因此，电路板排列问题要求对于给定的电路板连接条件(连接块)，确定电路板的最佳排列，使其具有最小密度。 算法思路 电路板排列问题的解空间是一颗排列树。采用优先队列式分支限界法找出所给电路板的最小密度布局。算法中采用最小堆表示活节点优先级队列。最小堆中元素类型是BoradNode，每一个BoardNode类型的节点包含域x，表示节点所相应的电路板排列；s表示该节点已确定的电路板排列x[1:s]；cd表示当前密度，now[j]表示x[1:s]中所含连接块j中的电路板数。 《算法设计与分析》实验报告六 学号： 1004091130 姓名：金玉琦 日期：2011-11-17得分： 一、实验内容： 运用分支限界法解决0-1背包问题。 二、所用算法的基本思想及复杂度分析： 分支限界法 分支限界法按广度优先策略遍历问题的解空间树, 在遍历过程中, 对已经处理的每一个结点根据限界函数估算目标函数的可能取值, 从中选取使目标函数取得极值的结点优先进行广度优先搜索, 从而不断调整搜索方向, 尽快找到问题的解。因为限界函数常常是基于问题的目标函数而确定的, 所以, 分支限界法适用于求解最优化问题。 0-1背包问题 1）基本思想 给定n 种物品和一个容量为C 的背包, 物品i 的重量是W i, 其价值为V i, 0/ 1 背包问题是如何选择装入背包的物品(物品不可分割) , 使得装入背包中物品的总价值最大，一般情况下, 解空间树中第i 层的每个结点, 都代表了对物品1～i 做出的某种特定选择, 这个特定选择由从根结点到该结点的路径唯一确定: 左分支表示装入物品, 右分支表示不装入物品。对于第i 层的某个结点, 假设背包中已装入物品的重量是w, 获得的价值是v, 计算该结点的目标函数上界的一个简单方法是把已经装入背包中的物品取得的价值v, 加上背包剩余容量W - w 与剩下物品的最大单位重量价值vi + 1/ wi + 1的积,于是,得到限界函数: u b = v + ( W - w) × ( vi + 1/ wi + 1 ) 根据限界函数确定目标函数的界[ down , up]，然后, 按照广度优先策略遍历问题的空间树。 2）复杂度分析 时间复杂度是O(2n); 三、源程序及注释： #include 实验七分支限界法（2学时） 一、实验目的与要求 1、掌握旅行商售货员问题的分支限界算法； 2、区分分支限界算法与回溯算法的区别，加深对分支限界法的理解。 二、实验题： 某售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费)。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费)最小。 三、实验提示 旅行商问题的解空间是一个排列树。有两种实现的方法。第一种是只使用一个优先队列，队列中的每个元素中都包含到达根的路径。另一种是保留一个部分解空间树和一个优先队列，优先队列中的元素并不包含到达根的路径。以下为第一种方法。 由于我们要寻找的是最小耗费的旅行路径，因此可以使用最小耗费分枝定界法。在实现过程中，使用一个最小优先队列来记录活节点，队列中每个节点的类型为MinHeapNode。每个节点包括如下区域： x（从1到n的整数排列，其中x[0] = 1 ），s（一个整数，使得从排列树的根节点到当前节点的路径定义了旅行路径的前缀x[0:s], 而剩余待访问的节点是x [s + 1 : n - 1 ]），cc（旅行路径前缀，即解空间树中从根节点到当前节点的耗费），lcost（该节点子树中任意叶节点中的最小耗费）， rcost（从顶点x[s : n - 1]出发的所有边的最小耗费之和）。当类型为MinHeapNode( T )的数据被转换成为类型T时，其结果即为lcost的值。分枝定界算法的代码见程序 程序首先生成一个容量为100的最小堆，用来表示活节点的最小优先队列。活节点按lcost值从最小堆中取出。接下来，计算有向图中从每个顶点出发的边中耗费最小的边所具有的耗费MinOut。如果某些顶点没有出边，则有向图中没有旅行路径，搜索终止。如果所有的顶点都有出边，则可以启动最小耗费分枝定界搜索。根的孩子B作为第一个E-节点，在此节点上，所生成的旅行路径前缀只有一个顶点1，因此s=0, x[0]=1, x[1:n-1]是剩余的顶点（即顶点2 ， 3 ，.， n ）。旅行路径前缀1的开销为0 ，即cc = 0 ，并且，rcost=n && i=1时MinOut 。 毕业设计（论文）开题报告 计算机科学与信息工程学院2013 届 题目分支限界算法的研究与实现Research and application of branch threshold algorithm 课题类型应用研究课题来源老师指定 学生姓名李瑞杰学号200903010017 专业班级09届计算机科学与技术（应用） 指导教师冯慧玲职称讲师 填写日期：2013 年3 月30 日 一、本课题研究的主要内容、目的和意义 1.课题内容 以旅行售货员问题、0/1背包问题、作业分配问题、布线问题、货物装载问题为例进行算法的分析、设计、实现及模拟演示。 在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 在现实生活中，有这样一类问题：问题有n个输入，而问题的解就由n个输入的某种排列或某个子集构成，只是这个排列或子集必须满足某些事先给定的条件。把那些必须满足的条件称为约束条件；而把满足约定条件的排列或子集称为该问题的可行解。满足约束条件的子集可能不止一个，也就量说可行解一般来说是不唯一的。为了衡量可行解的优劣，事先也可能给出了一定的标准，这些标准一般以函数形式给出，这些函数称为目标函数。那些使目标函数取极值的可行解，称为最优解。如工作安排问题，任意顺序都是问题的可行解，人们真正需要的是最省时间的最优解。 2.研究方法 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 3.课题研究的意义 用回溯算法解决问题时，是按深度优先的策略在问题的状态空间中，尝试搜索可能的路径，不便于在搜索过程中对不同的解进行比较，只能在搜索到所有解的情况下，才能通过比较确定哪个是最优解。这类问题更适合用广度优先策略搜 实验四用分支限界法实现0-1背包问题 一．实验目的 1.熟悉分支限界法的基本原理。 2.通过本次实验加深对分支限界法的理解。 二．实验内容及要求 内容：.给定n种物品和一个背包。物品i的重量是w，其价值为v，背包容量为c。问应该如何选择装入背包的物品，使得装入背包中物品的总价值最大? 要求：使用优先队列式分支限界法算法编程，求解0-1背包问题 三．程序列表 #include void AddLiveNode(double up, double cp, double cw, bool ch, int level);//up是价值上界，cp是相应的价值，cw是该结点所相应的重量，ch是ture or false stack 实验四单源最短路径问题 一、实验目的： 1、理解分支限界法的剪枝搜索策略； 2、掌握分支限界法的算法柜架； 3、掌握分支限界法的算法步骤； 4、通过应用范例学习动态规划算法的设计技巧与策略； 二、实验内容及要求： 1、使用分支限界法解决单源最短路径问题。 2、通过上机实验进行算法实现。 3、保存和打印出程序的运行结果，并结合程序进行分析，上交实验报告。 三、实验原理： 分支限界法的基本思想： 1、分支限界法与回溯法的不同： 1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。 2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。 2、分支限界法基本思想： 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。 在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 3、常见的两种分支限界法： 1）队列式(FIFO)分支限界法 按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 2）优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。 四、程序代码： #include 《算法设计与分析》作业 作业四+五回溯法+分支限界法 1. 二元最大连通块搜索 因为下了场大雨，青蛙王子高兴坏了，它有机会重新划定自己的王国范围。在下图中，空白区域表示积水的地方，青蛙王子需要找到一块最大的连续积水区域（上下或左右相连）作为自己的新领地。 2. 三元最大连通块搜索 小明在玩一种消除游戏。游戏中有一个长方形的区域，被RGB(红绿蓝)三种颜色的小球充满。要求每次找出当前最大连通区域（上下左右相邻同种颜色即可算作连通），进行消除。 ####.### ###.#### ##.##### the ans is 7 12 8 ..#..... .##....# .#....#. .###.#.. ....#... ..##.#.. .#....#. .##..#.# ###..#.. ....#... ...#.... ..#..... the ans is 18 1.3 程序运行情况 1.4 程序源码（含注释） #include"bits/stdc++.h" using namespace std; #define inf 999 //代码下标从0始，输入时.为可走，#为不可走 int n,m;//行、列 int ans,now;//最大连通数，当前搜索时连通数 char e[inf][inf];//地图 int book[inf][inf];//标记地图 int pos[4][2]={-1,0,1,0,0,1,0,-1};//方位，上下右左 void read()//输入数据 { printf("input the row and the column of the map:"); scanf("%d%d",&n,&m); printf("now input the map:\n"); for(int i=0;i 算法分析与设计实验报告 ——最小重量机器设计分支限界法解决 一、实验目的 建立算法复杂度的理论分析与实验分析的联系，深刻体会算法复杂度作为算法的好坏评价指标的本质含义。 二、实验要求 1、用c++语言实现最小重量机器设计的分支限界算法。 2、分析算法的计算复杂性 三、实验原理 分支限界法以广度优先或以最小耗费优先的方式搜索解空间。搜索策略是，在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前当前的活结点表中选择下一个扩展节点。为有效的选择下一扩展节点，加速搜索的进程，在每一或节点处，计算一个函数值（限界），并根据函数值，从当前活结点表中选择一个有利于的节点作为扩展节点，使搜索朝着解空间上最优解的分支推进，以便尽快找出一个最优解 四、实验过程(步骤) 用分支定界法解题的一般步骤： 在解最小机器重量问题的优先队列式分支定界法中，活结点优先队列中结点元素N的优先级由该结点的重量给出，重量最小的为小顶堆堆顶元素，堆元素的类型为HeapNode，其私有成员有weight，level，对于任意活结点N.weight所相应的重量； 函数AddLive将一个新的活结点插入到子集树和优先队列中。 算法中N是当前的扩展结点，cw是相应的重量，cp是相应的价值，while循环不断的扩展结点，直到子集树的叶结点成为扩展结点为止。此时优先队列中所有活结点的都考察完了，故，该叶结点相应的解为问题的最优解。 While内部循环，算法首先检查当前儿子结点的可行性，如果可行，则加入到子集树和活结点队列中。 五、运行结果 六、实验心得 通过做这次试验，深刻体会到了堆所起到的作用和分支限界法求解问题的效率在很大情况下高于回溯法，由于访问树方式的不同，使得分支定界法对每个结点只有一次成为可扩展结点，而回溯法则不同。 常用算法之：分支限界法 一、基本描述 类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法。但在一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。 （1）分支搜索算法 所谓“分支”就是采用广度优先的策略，依次搜索E-结点的所有分支，也就是所有相邻结点，抛弃不满足约束条件的结点，其余结点加入活结点表。然后从表中选择一个结点作为下一个E-结点，继续搜索。 选择下一个E-结点的方式不同，则会有几种不同的分支搜索方式。 1）FIFO搜索 2）LIFO搜索 3）优先队列式搜索 （2）分支限界搜索算法 二、分支限界法的一般过程 由于求解目标不同，导致分支限界法与回溯法在解空间树T上的搜索方式也不相同。回溯法以深度优先的方式搜索解空间树T，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。 分支限界法的搜索策略是：在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展对点。为了有效地选择下一扩展结点， 以加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。问题的解空间树是表示问题解空间的一棵有序树，常见的有子集树和排列树。在搜索问题的解空间树时，分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被子加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。 三、回溯法和分支限界法的一些区别 有一些问题其实无论用回溯法还是分支限界法都可以得到很好的解决，但是另外一些则不然。也许我们需要具体一些的分析——到底何时使用分支限界而何时使用回溯呢？ 回溯法和分支限界法的一些区别： 方法对解空间树的搜索方式存储结点的常用数据结构结点存储特性常用应用 回溯法深度优先搜索堆栈活结点的所有可行子结点被遍历后才被从栈中弹出找出满足约束条件的所有解 分支限界法广度优先或最小消耗优先搜索队列、优先队列每个结点只有一次成为活结点的机会找出满足约束条件的一个解或特定意义下的最优解 算法分析与设计实验报告 学号姓名班级 上课地点教师上课时间 实验六分支限界法 1. 实验目的 1.1掌握分支限界法的设计思想； 1.2理解分支限界法的剪枝搜索策略； 1.3掌握分支限界法的算法框架； 1.4学会利用分支限界法解决实际问题。 2. 实验环境 2.1 Eclipse 2.2 Window XP 3. 实验内容 3.1装载问题 3.2旅行售货员问题 4. 教师批改意见 成绩 签字： 日期： 实验报告细表 1装载问题 1.1 算法设计思想 解装载问题的优先队列式分支限界法用最大优先队列存储活结点表。活结点x在优先队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和。优先队列中优先级最大的活结点成为下一个扩展结点。以结点x为根的子树中所有结点相应的路径的载重量不超过它的优先级。子集树中叶结点所相应的载重量与其优先级相同。在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。此时可终止算法。 1.2 程序源码 package lab06; import https://www.doczj.com/doc/a33805250.html,parator; 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();(完整版)分支限界算法作业分配问题
实验4用分支限界法实现0-1背包问题
分支限界算法报告
分支限界法实现单源最短路径问题
实验四 分支限界法实现单源最短路径
分支限界法实验(最优装载问题)
0037算法笔记——【分支限界法】最大团问题
分支界限法解0-1背包问题实验报告
算法设计与分析第6章回溯与分支限界
0039算法笔记——【分支限界法】电路板排列问题
实验报告 分支限界法01背包
实验七分支限界法
毕业设计(论文)开题报告 分支限界算法的研究与实现
最新实验 4 用分支限界法实现0-1背包问题
实验四 单源最短路径(分支限界法)
算法设计与分析---回溯+分支限界法实验报告
分支限界法
常用算法之：分支限界法
实验六_分支限界法
相关主题
文本预览