实验报告：分支限界法

1、XXXX大学计算机学院实验报告计算机学院 2017 级软件工程专业班指导教师学号 姓名2019年11月18日 成绩课算法分析与设计实验名称分支限界法一单源最短路径问题实验:理解分支限界法的基本思想理解的分支限界法的剪枝搜索策略通过分支限界法一单源最短路径问题练习，加深对该算法的理解实 验 仪 器和 器 材电脑、jdk、eclipseI实 验 内 容上 调 试 程 序程 序 运 行 结果分支限界法一单源最短路径问题：给定一个带权有向图G=(V,E)，其中每条边的权都是非负数， 给定V中的一个顶点成为源，计算从源到所有其他各顶点的最短路径长度，这里路径长度指的 是各边权之和。核心代码如下：impo

2、rt java.util.Collections;import java.util.LinkedList;import java.util.Scanner;public class BBShortPath /*实*单源最短路径问题-分支界限法验* param args内 容、 上 机 调 试 程序、 程 序 运 行 结果*/public static class Heapnode implements Comparable int id;/顶点编号 float length;/当前路长public Heapnode(int ii,float ll)id = ii;length = ll;Ove

3、rridepublic int compareTo(Object x) float x1 = (Heapnode)x).length;if(lengthx1) return -1;if(length=x1) return 0;return 1;public static void shortPath(floata,int v,float dist,int p) int n = p.length-1;LinkedList nodes = new LinkedList();/用 LinkedLi st 存储小堆 Heapnode enode = new Heapnode(v,0);for(int

4、j=1;j=n;j+)distj=Float.MAX_VALUE;/distj保存从源顶点到顶点j的距离 while(true)/搜索问题解空间for(int j=1;j=n;j+)if(aenode.idj != -1 & enode.length+aenode.idjdistj)/顶点i到j可达，同时长度小于distjdistj = enode.length + aenode.idj;pj=enode.id;/pj记录从源到顶点J的路径上的前驱节点 Heapnode e = new Heapnode(j,distj);nodes.add(e);Collections.sort(nodes)

5、;/取下一个扩展节点if(nodes.isEmpty() break;else enode = nodes.poll();实 验 内 容、for(int i=2;i=n;i+)System.out.println(i+”节点的最短距离是：+disti+;前驱点是：+pi);public static void main(String args) 机System.out.println（请输入图顶点个数：）;调 试 程 序、 程 序Scanner sc = new Scanner(System.in);String line = sc.nextLine();int n = Integer.par

6、seInt(line);System.out.println(请输入图的路径长度：)；float a = new float n+1n+1;/下标从 1 开始，以下都是 float dist = new floatn+1;int prev = new intn+1;for(int i=0;in;i+)line = sc.nextLine();运彳亍结String ds = line.split(,);for(int j=0;jds.length;j+)ai+1j+1 = Float.parseFloat(dsj); int v=1;果 shortPath(a,v,dist,prev); 完成效

7、果峋 e-cISpse.wakipace - Aiaorkhn/src/BBShonPaihijaMji - EdipseFile Edk Source- Refacta*- NaMiate- Search Reject RunHsp日-可皿5曰尊厂新国H31.01固jTl EBShc-rtpAthjHvwi E：T 同 B hud4.jY i | EECIfiqiu乒侦 js- impQF javfc util. Co-llectioHns-sD 45 publicBBSh&rt Pjith (a* /*=K肯支器眼志蹭.gpTHn angsdihatc-my.jBViii KrtapMck

8、Prabiern Jsvs OpTifiilPckiHg.JiSii1 quiekSiDrt Ja7iH Sha*testPdihpubliccl* HEHpnQd七 mpl4rti4i：4 Coniparebletiftt id-/THrSIHt YIojH Length;/%*路荷 public He-a p node- (J. nt i i p loa 11) id = i;lencth = 11耍 HuHmanTrwh JRE 导He Libravy lwnE-1lJB : 沼 chapre TW chapteriM:- 贽 chspreGTchaptHi-O chaptelO cha

9、pre-J-pracike chaparOB- CompuReSiore HQUieRens-HlkK-rriateHpublic nt ampar-aTo(Obji-ctlioa: x 1 = (Heapnndejx . lengthjiif Q-e-nElhx:!)1 rtwirin -1 2 h*chlvrna JHWrdcEDaul.:Bti&rif 口n.T. E：3MmMmedh 0 BShortP-sth IJ-ava pkibon) CP-ogr*m *vai-eT。.0_ ST旧2占心” se HE ?1卫月9 日 下午蜃晌.：-.陌的希置长.厦I 1,3 -! ,!.5-备

10、昌nwServers Wtor.mm 如乳LLL全*点的ntRjc荐是：。.也点是=i 砰卢的。输3点蜃I 1 %触点的RKff局夏：b-bsWE.SS： a心得与体会:实 验 内 容、 上 机 调 试 程序、 程 序 运 行结 果分支限界法-单源最短路径问题算法思想：给定一个带权有向图 G=(V,E),其中每条边的权都是非负数，给定V中的一个顶点成为源， 计算从源到所有其他各顶点的最短路径长度(即各边权之和)，算法从G 的源头s和空优先队列开始，结点s被扩展之后，他的3个儿子结点被 一次插入堆中，此后，算法从堆中取出具有最小当前路长的结点作为当 前扩展结点，并依此检查与当前扩展结点相邻的所有顶点，如果从当前 扩展结点i到顶点j有边可达，且从源出发，途经结点i再到顶点j有 边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小 于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列 中，结点的扩展过程一直继续到活结点优先队列为空时为止。由于带权 有向图G=(V,E),其中每条边的权都是非负数，所以节点所对应的当前 路长也是解空间树中以该结点为根的子树中所有结点所对应的路长的 一个下界，在算法扩展结点的过程中，一旦发现一个结点的下界不小于 当前找到的最短路长，则算法减去以该结点为根的子树。源到当前节点 的和都是最小。分支限界法类似于回溯法，也是在问题的解空间