算法分析与设计实验五分枝—限界算法

HUBEI UNIVERSITY OF AUTOMOTIVE TECHNOLOGY算法设计与分析实验报告实验项目实验五实验类别验证性学生姓名王龙学生学号201400797 完成日期2016-5-6指导教师刘振章实验成绩评阅日期评阅教师刘振章实验五：分枝限界法【实验目的】应用分枝限界法的算法设计思想求解单源最短路径问题。

【实验性质】验证性实验。

【实验内容与要求】采用分支限界法编程求源点0到终点6的最短路径及其路径长度。

要求完成：⑴算法描述⑵写出程序代码⑶完成调试⑷进行过程与结果分析。

【算法思想及处理过程】由于要找的是从源到各顶点的最短路径，所以选用一个数组存起来.Fenzhi函数: 由于先前赋值时, 用一个二维数组将结点的有向图标记存起来了( 有边为1, 无边为0 ),并且又用另外一个二维数组将其权重存起来了; 首先, 通过双重for循环, 通过if语句判断, 如果标记为1, 并且相加的权重小于先前最优权重( 在初始化的时候, 对最优权重赋上一个最大值 ), 则求得最优权重, 并且用一维数组将权重存起来, 而且用一维数组将前驱结点存起来.你然后, 一直循环下去, 直到循环到目的结点.【程序代码】for (z=0; z<k; z++){scanf ("%d %d %d", &i, &j, &m);t[i][j] = m;ti[i][j] = 1;}for (i = 0; i < n; i++) //初始化数组{d[i] = 99; // 赋个最大值s[i] = -1;}}void fenzhi (int d[], int s[],int t[][MAX], int ti[][MAX], int n, int k) {int i, j, zi;d[0]=0; s[0]=-1;for (i=0; i<n; i++){printf ("当前扩展节点：%d，权重：%d : \n", i, d[i]);for (j=0; j<n; j++){if (ti[i][j] == 1 ){if ( d[j]>t[i][j]+d[i]){d[j]=t[i][j]+d[i]; //最短长度s[j]=i; //前驱结点}if (j != n /* && j != 6 */ )printf ("入队结点：%d ,最优权重：%d \n", j, d[j]);}}printf ("\n");}}void output (int d[], int s[], int n){int i, j=0, zi[MAX];printf ("从源点到各个结点的最短路径: \n");for (i=0; i<n; i++)printf ("dist[%d] = %d \n", i, d[i]);printf ("\n");printf ("从源点到终点的最短路径长度为: %d \n", d[n-1]);printf ("其路径为: %d ", n-1);zi[j] = s[n-1];printf ("----> %d ", zi[j]);while (zi[j] != 0){j++;zi[j] = s[zi[j-1]];printf ("----> %d ", zi[j]);}printf ("\n");}【运行结果】图1 输入数据图2 输出扩展结点图3 最终结果【算法分析】本程序的主要函数ShorestPaths的时间复杂度为: O ( n * (n-1) ), 最坏时间复杂度为: O ( n*n )【实验总结】。

算法分析与设计分支限界法分支限界法是一种常用的优化算法，它通过剪枝和分支的方式在空间中找到最优解。

在算法设计与分析中，分支限界法在求解组合优化问题和图论问题中有广泛应用。

分支限界法的基本思想是将问题划分为一个个子问题，并对每个子问题进行求解，同时通过剪枝操作减少空间。

算法从一个初始状态开始，通过扩展子节点来生成树。

在每个节点上，先判断该节点是否需要剪枝操作。

如果需要剪枝，则舍弃该节点及其子节点；如果不需要剪枝，则继续扩展该节点为新的可能解。

通过不断扩展和剪枝操作，最终找到最优解。

分支限界法的核心是选择一个合适的策略来确定节点的扩展顺序。

常用的策略包括优先级队列、最小堆、最大堆等。

这些策略可以根据问题的性质和特点来选择，以保证效率。

同时，剪枝操作也是分支限界法中关键的一环。

剪枝操作有多种方式，如上界和下界剪枝、可行剪枝、标杆剪枝等。

通过剪枝操作，可以减少空间，提高算法的效率。

分支限界法的时间复杂度通常是指数级别的，因为每个节点需要根据策略进行扩展，并进行剪枝操作。

然而，通过合理选择策略和剪枝操作，可以显著减少空间，降低时间复杂度。

此外，分支限界法还可以通过并行计算等技术进一步提高效率。

分支限界法在求解组合优化问题中有广泛应用。

组合优化问题是在有限的资源条件下，通过组合和选择来达到最优解的问题。

例如，旅行商问题、背包问题等都是经典的组合优化问题，而分支限界法可以在有限的时间内找到最优解。

在图论问题中，分支限界法也有重要的应用。

例如，最短路径问题、图着色问题等都可以通过分支限界法求解。

总之，分支限界法是一种基于和剪枝的优化算法，通过合理选择策略和剪枝操作，在有限的时间内找到最优解。

该算法在组合优化问题和图论问题中有广泛应用，可以有效提高问题求解的效率。

在实际应用中，可以根据问题性质和特点选择合适的策略和剪枝操作，以达到最佳的求解效果。

五大常用算法之五：分支限界法五大常用算法之五：分支限界法分支限界法一、基本描述类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法。

但在一般情况下，分支限界法与回溯法的求解目标不同。

回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。

（1）分支搜索算法所谓“分支”就是采用广度优先的策略，依次搜索E-结点的所有分支，也就是所有相邻结点，抛弃不满足约束条件的结点，其余结点加入活结点表。

然后从表中选择一个结点作为下一个E-结点，继续搜索。

选择下一个E-结点的方式不同，则会有几种不同的分支搜索方式。

1）FIFO搜索2）LIFO搜索3）优先队列式搜索（2）分支限界搜索算法二、分支限界法的一般过程由于求解目标不同，导致分支限界法与回溯法在解空间树T上的搜索方式也不相同。

回溯法以深度优先的方式搜索解空间树T，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。

分支限界法的搜索策略是：在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展对点。

为了有效地选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。

分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。

问题的解空间树是表示问题解空间的一棵有序树，常见的有子集树和排列树。

在搜索问题的解空间树时，分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。

在分支限界法中，每一个活结点只有一次机会成为扩展结点。

活结点一旦成为扩展结点，就一次性产生其所有儿子结点。

在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被子加入活结点表中。

第八章分枝－限界法§1 算法基本思想本章叙述中为了区别图中的顶点和解空间树中的顶点，凡是在解空间树中出现的“顶点”一律称为“结点”。

分枝限界法同回溯法类似，它也是在解空间中搜索问题的可行解或最优解，但搜索的方式不同。

回溯法采用深度优先的方式，朝纵深方向搜索，直至达到问题的一个可行解，或经判断沿此路径不会达到问题的可行解或最优解时，停止向前搜索，并沿原路返回到该路径上最后一个还可扩展的结点。

从该结点出发朝新的方向纵深搜索。

分枝限界法则采用宽度优先的方式搜索解空间树，它将活结点存放在一个特殊的表中。

其策略是：在扩展结点处，首先生成其所有的儿子结点,将那些导致不可行解或导致非最优解的儿子舍弃，其余儿子加入活结点表中。

然后，从活结点表中取出一个结点作为当前扩展结点。

重复上述结点扩展过程。

所以，分枝限界法与回溯法的本质区别在于搜索方式的不同。

回溯法更适于处理那些求所有可行解的问题，而分枝限界法更适于处理那些只确定一个可行解，特别是最优解的问题。

从活结点表中选择下一扩展结点的不同方式导致不同的分枝限界法。

最常见的有以下两种方式：1).队列式（FIFO）分枝限界法：将活结点表组织成一个队列，并按队列的先进先出原则选取下一个结点作为当前扩展结点。

2).优先队列式分枝限界法：将活结点表组织成一个优先队列，并按优先队列给结点规定的优先级选取优先级最高的下一个结点作为当前扩展结点。

队列式分枝限界法搜索解空间树的方式类似于解空间树的宽度优先搜索，不同的是队列式分枝限界法不搜索不可行结点（已经被判定不能导致可行解或不能导致最优解的结点）为根的子树。

这是因为，按照规则，这样的结点未被列入活结点表。

优先队列式分枝限界法的搜索方式是根据活结点的优先级确定下一个扩展结点。

结点的优先级常用一个与该结点有关的数值p来表示。

最大优先队列规定p值较大的结点的优先级较高。

在算法实现时通常用一个最大堆来实现最大优先队列，用最大堆的Deletemax运算抽取堆中的下一个结点作为当前扩展结点，体现最大效益优先的原则。

实验5. 分支限界法Branch and Bound Method一、实验目的1.理解分支限界法的基本思想。

2.运用分支限界法解决实际问题。

二、实验环境与地点1.实验环境：Windows7,Eclipse2.实验地点：网络工程实验室三、实验内容与步骤编写程序完成下列题目，上机调试并运行成功。

1.单源最短路径问题：在下图所给的有向图G中，每一边都有一个非负边权。

要求图G的从源顶点s到目标顶点t之间的最短路径。

下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。

其中，每一个结点旁边的数字表示该结点所对应的当前路长。

算法思想：解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。

其优先级是结点所对应的当前路长。

算法从图G的源顶点s和空优先队列开始。

结点s被扩展后，它的儿子结点被依次插入堆中。

此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。

如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。

这个结点的扩展过程一直继续到活结点优先队列为空时为止。

算法结束后，数组dist返回从源到各顶点的最短距离。

相应的最短路径容易从前驱顶点数组记录的信息构造出。

算法：public class BBShortest {static final float M=Float.MAX_VALUE;static class HeapNode implements Comparable {int i; // 顶点编号float length; // 当前路长HeapNode(int ii, float ll) {i = ii;length = ll;}public int compareTo(Object x) {float xl = ((HeapNode) x).length;if (length < xl)return -1;if (length == xl)return 0;return 1;}}// 1,2,3,4,5,6,7,8,9,10,11static float[][] a={{0,0,0,0,0,0,0,0,0,0,0,0,},{0,0,2,3,4,M,M,M,M,M,M,M,},//1{0,M,0,3,M,7,2,M,M,M,M,M,},//2{0,M,M,0,M,M,9,2,M,M,M,M,},//3{0,M,M,M,0,M,M,2,M,M,M,M,},//4{0,M,M,M,M,0,M,M,3,3,M,M,},//5{0,M,M,M,M,M,0,1,M,3,M,M,},//6{0,M,M,M,M,M,M,0,M,5,1,M,},//7{0,M,M,M,M,M,M,M,0,M,M,3,},//8{0,M,M,M,M,M,M,M,M,0,M,2,},//9{0,M,M,M,M,M,M,M,M,2,0,2,},//10{0,M,M,M,M,M,M,M,M,M,M,0,},//11}; // 图G的邻接矩阵static float[] dist=new float[a.length];static int[] p=new int[dist.length];public static void shortest(int v, float[] dist, int[] p) {int n = p.length - 1;MinHeap heap = new MinHeap();// 定义源为初始扩展结点HeapNode enode = new HeapNode(v, 0);for (int j = 1; j <= n; j++)dist[j] = Float.MAX_VALUE;dist[v] = 0;while (true) { // 搜索问题的解空间for (int j = 1; j <= n; j++)if (a[enode.i][j] < Float.MAX_VALUE && enode.length + a[enode.i][j] < dist[j]) {// 顶点i到顶点j可达,且满足控制约束dist[j] = enode.length + a[enode.i][j];p[j] = enode.i;HeapNode node = new HeapNode(j, dist[j]);heap.put(node); // 加入活结点优先队列}// 取下一扩展结点if (heap.isEmpty())break;elseenode = (HeapNode) heap.removeMin();}}}注意：实现算法时，MinHeap直接用PriorityQueue创建优先级队列。

第1篇一、实验目的1. 理解并掌握分枝限界法的基本原理和实现方法。

2. 通过实际编程，运用分枝限界法解决实际问题。

3. 比较分析分枝限界法与其他搜索算法（如回溯法）的优缺点。

4. 增强算法设计能力和编程实践能力。

二、实验内容本次实验主要涉及以下内容：1. 分支限界法的基本概念和原理。

2. 分支限界法在单源最短路径问题中的应用。

3. 分支限界法的实现步骤和代码编写。

4. 分支限界法与其他搜索算法的对比分析。

三、实验环境1. 操作系统：Windows 102. 编程语言：Python3.83. 开发环境：PyCharm四、实验步骤1. 算法描述：分支限界法是一种用于解决组合优化问题的算法，其基本思想是在问题的解空间树中，按照一定的搜索策略，优先选择有潜力的节点进行扩展，从而减少搜索空间，提高搜索效率。

2. 程序代码：下面是使用Python实现的分支限界法解决单源最短路径问题的代码示例：```pythonimport heapqclass Node:def __init__(self, vertex, distance, parent): self.vertex = vertexself.distance = distanceself.parent = parentdef __lt__(self, other):return self.distance < other.distancedef branch_and_bound(graph, source):初始化优先队列和已访问节点集合open_set = []closed_set = set()添加源节点到优先队列heapq.heappush(open_set, Node(source, 0, None))主循环，直到找到最短路径while open_set:弹出优先队列中最小距离的节点current_node = heapq.heappop(open_set)检查是否已访问过该节点if current_node.vertex in closed_set:continue标记节点为已访问closed_set.add(current_node.vertex)如果当前节点为目标节点，则找到最短路径if current_node.vertex == target:path = []while current_node:path.append(current_node.vertex)current_node = current_node.parentreturn path[::-1]遍历当前节点的邻居节点for neighbor, weight in graph[current_node.vertex].items():if neighbor not in closed_set:计算新节点的距离distance = current_node.distance + weight添加新节点到优先队列heapq.heappush(open_set, Node(neighbor, distance, current_node))没有找到最短路径return None图的表示graph = {0: {1: 2, 2: 3},1: {2: 1, 3: 2},2: {3: 2},3: {1: 3}}源节点和目标节点source = 0target = 3执行分支限界法path = branch_and_bound(graph, source)print("最短路径为：", path)```3. 调试与测试：在编写代码过程中，注意检查数据结构的使用和算法逻辑的正确性。