logo资料库

分支限界法-单源最短路径.docx

发布时间：2022-06-08 发布人：admin 分类：说明书 资料大小：0.08M 资料格式：docx 举报 版权申诉
第1页 / 共8页
第2页 / 共8页
第3页 / 共8页
第4页 / 共8页
第5页 / 共8页
第6页 / 共8页
第7页 / 共8页
第8页 / 共8页
资料共8页，全文预览结束
    《算法设计与分析》实验报告 实验环境： Window7 旗舰版 操作系统 myeclipes 编译器 实验内容与完成情况： 一、 实验目的 了解分支限界法的概念和使用条件，知道在遇见题目的时候可以使用分支界限法的思想来解决问题 二、 实验内容 1、分支限界法 (1)描述：采用广度优先产生状态空间树的结点，并使用剪枝函数的方法称为分枝限界法。 所谓“分支”是采用广度优先的策略，依次生成扩展结点的所有分支（即：儿子结点）。 所谓“限界”是在结点扩展过程中，计算结点的上界（或下界），边搜索边减掉搜索树的某些 分支，从而提高搜索效率。 (2)原理：按照广度优先的原则，一个活结点一旦成为扩展结点（E-结点）R 后，算法将依次生 成它的全部孩子结点，将那些导致不可行解或导致非最优解的儿子舍弃，其余儿子加入活结点 表中。然后，从活结点表中取出一个结点作为当前扩展结点。重复上述结点扩展过程，直至找 到问题的解或判定无解为止。 (3)分支限界法与回溯法 1)求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求 解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。 1
    2)搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最 小耗费优先的方式搜索解空间树。 2、单源最短路径问题 问题描述 在下图所给的有向图 G 中，每一边都有一个非负边权。要求图 G 的从源顶点 s 到目标顶点 t 之间的最短路径。 下图是用优先队列式分支限界法解有向图 G 的单源最短路径问题产生的解空间树。其中， 每一个结点旁边的数字表示该结点所对应的当前路长。 2
    算法设计 算 法从图 G 的源顶点 s 和空优先队列开始。结点 s 被扩展后，它的儿子结点被依次插入堆 中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依 次检查与当前扩 展结点相邻的所有顶点。如果从当前扩展结点 i 到顶点 j 有边可达，且从源出发，途经顶点 i 再 到顶点 j 的所相应的路径的长度小于当前最优路径长 度，则将该顶点作为活结点插入到活结点 优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。 在算法扩展结点的过程中，一旦发现一个结点的下界不小于当前找到的最短路长，则算法剪去以该结点为根 的子树。 在算法中，利用结点间的控制关系进行剪枝。从源顶点 s 出发，2 条不同路径到达图 G 的同 一顶点。由于两条路径的路长不同，因此可以将路长长的路径所对应的树中的结点为根的子树 剪去。 import java.util.Collections; import java.util.LinkedList; import java.util.Scanner; /** * 单源最短路径问题--分支限界法 * @author Lican * */ 3
    public class BBShortest { public static class Heapnode implements Comparable{ int id;//顶点编号 float length;//当前路长 public Heapnode(int ii,float ll){ id=ii; length=ll; } @Override public int compareTo(Object x) { float xl=((Heapnode)x).length; if(length nodes=new LinkedList();//用 LinkedList 存储最小堆 4
    Heapnode enode=new Heapnode(v,0); for(int j=1;j<=n;j++){ dist[j]=Float.MAX_VALUE; } while(true){//搜索问题解空间 for(int j=1;j<=n;j++){ if(a[enode.id][j]!=-1&&enode.length+a[enode.id][j]
    } } for(int i=2;i<=n;i++){ System.out.println(i+"节点的最短距离是："+dist[i]+"；前驱点是："+p[i]); } } public static void main(String[] args) { System.out.println("请输入图顶点的个数："); Scanner sc = new Scanner(System.in); String line = sc.nextLine(); int n = Integer.parseInt(line); System.out.println("请输入图的路径长度："); float[][] a = new float[n+1][n+1];//下标从 1 开始，以下都是 float[] dist = new float[n+1]; int[] prev = new int[n+1]; for(int i=0;i
    a[i+1][j+1]=Float.parseFloat(ds[j]); } } int v =1;//顶点从 1 开始 shortest(a,v,dist,prev); } } /** * 以下为输入输出 * * 输入： 5 -1,10,-1,30,100 -1,-1,50,-1,-1 -1,-1,-1,-1,10 -1,-1,20,-1,60 -1,-1,-1,-1,-1 * 输出： 7
    2 节点的最短距离是：10.0；前驱点是：1 3 节点的最短距离是：50.0；前驱点是：4 4 节点的最短距离是：30.0；前驱点是：1 5 节点的最短距离是：60.0；前驱点是：3 */ 实验结果： 8
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料