devbox
凡人多烦事01
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

算法与程序设计(六)：分支限界法_分支限界法单源最短路径代码和运行结果c语言

作者：凡人多烦事01 | 2024-05-27 04:59:52

赞

踩

分支限界法单源最短路径代码和运行结果c语言

目录

一、概念

1.1 分支限界法的基本思想

1.2 分支限界法与回溯法的不同

1.3 分支限界法的搜索方式

1.4 常见的两种分支限界法

二、举例

2.1 单源最短路径问题

三、代码实现

3.1 源程序

3.2 运行结果

一、概念

1.1 分支限界法的基本思想

1.2 分支限界法与回溯法的不同

1.3 分支限界法的搜索方式

1.4 常见的两种分支限界法

二、举例

2.1 单源最短路径问题

下图是用优先队列式(FIFO)分支限界法解有向图G的单源最短路径问题的解空间树；其中，每一个结点旁边的数字表示该结点所对应的当前路长。

找到一条路径：

目前的最短路径是8，一旦发现某个结点的下界不小于这个最短路径，则剪枝：

同一个结点选择最短的到达路径：

剪枝的策略：

1、在算法扩展结点的过程中，一旦发现一个结点的下界不小于当前找到的最短路长，则算法剪去以该结点为根的子树。

2、在算法中，利用结点间的控制关系进行剪枝。从源顶点s出发，2条不同路径到达图G的同一顶点。由于两条路径的路长不同，因此可以将路长较长的路径所对应的树中的结点为根的子树剪去。

最终结果：

所以从源顶点到终点的最短路径值为8，最短路径为：0 2 6 9 10。

三、代码实现

3.1 源程序

  1. package SufaLjh.Exp1.Homework_8.Day_6_11;
  2.  
  3.  
  4. import SufaLjh.Exp1.Homework_8.Day_6_11.tool.Heap;
  5. import SufaLjh.Exp1.Homework_8.Day_6_11.tool.HeapNode;
  6.  
  7. /**
  8.  * 分支限界法求单源最短路径问题
  9.  */
  10. public class E2 {
  11.     //定义变量
  12.     int heapsize = 0,n=10,inf = 1000;//inf 表示距离为无穷
  13.     int c[][] = new int[11][11],dist[]=new int[11],prev[]=new int[11];
  14.  
  15.     /**
  16.      * 主方法 程序入口
  17.      * @param args
  18.      */
  19.     public static void main(String[] args) {
  20.         new E2();
  21.     }
  22.     public E2(){
  23.         for (int i = 0; i <= n; i++) {
  24.             for (int j = 0; j <= n; j++)c[i][j] = inf;
  25.             dist[i]=inf;
  26.         }
  27.         c[0][1]=2;c[0][2]=3;c[0][3]=4;
  28.         c[1][2]=3;c[1][4]=7;c[1][5]=2;
  29.         c[2][5]=9;c[2][6]=2;
  30.         c[3][6]=2;c[4][7]=1;c[4][8]=2;c[5][6]=1;c[5][8]=3;
  31.         c[6][8]=5;c[6][9]=1;c[7][10]=2;c[8][10]=2;
  32.         c[9][8]=2;c[9][10]=2;
  33.  
  34.         Shostestpaths(0,10);
  35.         System.out.printf("从源点到最后一个点的最短路径的值为:%d\n",dist[10]);
  36.         print(10);
  37.     }
  38.  
  39.     /**
  40.      * 分支限界法
  41.      * @param v 源点
  42.      * @param end 终点
  43.      */
  44.     private void Shostestpaths(int v,int end){
  45.         Heap heap = new Heap();
  46.         HeapNode E = new HeapNode(),N = new HeapNode();
  47.         E.i=v;E.d=0;
  48.         dist[v]=0;
  49.         while (true){
  50.             for (int j = 1; j <= n; j++) {//找当前节点(下标为E，i)的所有儿子节点
  51.                  //int d=E.d+c[E.i][j];
  52.                  //if (c[E.i][j]<inf&&d<dist[j]&&d<dist[end])
  53.                 if (c[E.i][j]<inf&&E.d+c[E.i][j]<dist[j]&&E.d<dist[end]){
  54.                      dist[j]=E.d+c[E.i][j];//更新到第j个顶点的最短距离
  55.                      prev[j]=E.i;//取到第j个顶点的最短距离时，第j个顶点的前一个顶点为E.i
  56.                      N.i=j;N.d=dist[j];//给堆的新节点赋值
  57.                      N.key=N.d;//用最短距离作为堆中关键值
  58.                      heap.minHeapInsert(N);//将所有节点插入堆中
  59.                  }
  60.             }
  61.             E=heap.minHeapDelete();//取出堆顶元素作为当前节点
  62.             if (E.key==-1)break;//堆为空时退出
  63.         }
  64.     }
  65.  
  66.     /**
  67.      * 打印输出的方法
  68.      * @param v 源点
  69.      */
  70.     private void print(int v) {
  71.         int t[] = new int[11];
  72.         int i = v,j=0;
  73.         while (i>0){
  74.             t[j++]=i;i=prev[i];
  75.         }
  76.         t[j]=0;
  77.         System.out.printf("最短路径为:");
  78.         for (; j >= 0; j--) {
  79.             System.out.printf("%d ",t[j]);
  80.         }
  81.     }
  82. }
  83.  
  84.  
  85.  
  86.  
  87. 定义最大堆和最小堆的类文件Heap.java：
  88. package SufaLjh.Exp1.Homework_8.Day_6_11.tool;
  89.  
  90.  
  91. //大顶堆
  92. public class Heap {
  93.     int heapsize=0;//堆的大小
  94.     HeapNode A[]=new HeapNode[1000];//存放堆的数组
  95.  
  96.     /**
  97.      * 主方法
  98.      * @param args
  99.      */
  100.     public static void main(String[] args) {
  101.         new Heap();
  102.     }
  103.     /*public Heap(){
  105.     }*/
  106.  
  107.     /**
  108.      * 构造器
  109.      */
  110.     public Heap() {
  111.         for(int i=0;i<1000;i++)A[i]=new HeapNode();
  112.         /*System.out.println("小顶堆：");
  113.         //System.out.println("大顶堆: ");
  114.         for (int i = 0; i < 10; i++) {
  115.             HeapNode heapNode = new HeapNode();
  116.             heapNode.key = i;
  117.             //maxHeapInsert(heapNode);
  118.             minHeapInsert(heapNode);
  119.         }*/
  120.         //HeapNode E = maxHeapDelete();
  121.         HeapNode E = minHeapDelete();
  122.         while (E.key!=-1){
  123.             System.out.println(E.key+"  ");
  124.             //E=maxHeapDelete();
  125.             E=minHeapDelete();
  126.         }
  127.     }
  128.  
  129.     //大顶堆插入
  130.     public  void maxHeapInsert(HeapNode a) {
  131.             heapsize++;
  132.             int i = heapsize;
  133.             while (i > 1 && A[i / 2].key < a.key) {
  134.                 A[i].clone(A[i/2]);
  135.                 i=i/2;
  136.             }
  137.             A[i].clone(a);
  138.         }
  139.     //大顶堆返回堆顶元素
  140.     public  HeapNode maxHeapDelete() {
  141.             if (heapsize < 1) {
  142.                 A[0].key = -1;
  143.                 A[0].i = 0;
  144.                 return A[0];
  145.             }
  146.             HeapNode max = new HeapNode();
  147.             max.clone(A[1]);
  148.             A[1].clone(A[heapsize]);
  149.             heapsize--;
  150.             maxHeapify(1);//堆化
  151.             return max;
  152.         }
  153.     //大顶堆堆化
  154.     public  void maxHeapify(int i) {
  155.             int L, R, max;
  156.             L = 2 * i;
  157.             R = 2 * i + 1;
  158.             if (L <= heapsize && A[L].key > A[i].key)
  159.                 max = L;
  160.             else
  161.                 max = i;
  162.             if (R <= heapsize && A[R].key > A[max].key)
  163.                 max = R;
  164.             if (max != i) {
  165.                 HeapNode t = new HeapNode();
  166.                 t.clone(A[i]);A[i].clone(A[max]);A[max].clone(t);
  167.                 maxHeapify(max);
  168.             }
  169.         }
  170.     //小顶堆
  171.     public void minHeapInsert(HeapNode a)
  172.     {
  173.         heapsize++;
  174.         int i=heapsize;
  175.         while(i>1&&A[i/2].key>a.key)
  176.         {
  177.             A[i].clone(A[i/2]);
  178.             i=i/2;
  179.         }
  180.         A[i].clone(a);
  181.     }
  182.  
  183.     public HeapNode minHeapDelete()
  184.     {
  185.         if(heapsize<1){A[0].key=-1;return A[0];}
  186.         HeapNode min=new HeapNode();
  187.         min.clone(A[1]);
  188.         A[1].clone(A[heapsize]);
  189.         heapsize--;
  190.         minHeapify(1);
  191.         return min;
  192.     }
  193.     //小顶堆堆化
  194.     public void minHeapify(int i)
  195.     {
  196.         int L,R,min;
  197.         L=2*i;
  198.         R=2*i+1;
  199.         if(L<=heapsize&&A[L].key<A[i].key) min=L;
  200.         else min=i;
  201.         if(R<=heapsize&&A[R].key<A[min].key) min=R;
  202.         if(min!=i)
  203.         {
  204.             HeapNode  t=new HeapNode();
  205.             t.clone(A[i]);A[i].clone(A[min]);A[min].clone(t);           
  206.             minHeapify(min);
  207.         }
  208.     }
  209.  
  210. }
  211.  
  212. 定义堆节点的类文件HeapNode.java：
  213. package SufaLjh.Exp1.Homework_8.Day_6_11.tool;
  214.  
  215. public class HeapNode {
  216.     public int ew,wt,i,x,key,d;
  217.     public double p, up;
  218.     public void clone(HeapNode t) {
  219.         this.i=t.i;
  220.         this.ew=t.ew;
  221.         this.wt=t.wt;
  222.         this.x=t.x;
  223.         this.p=t.p;
  224.         this.up=t.up;
  225.         this.key=t.key;
  226.         this.d=t.d;
  227.     }
  228. }

3.2 运行结果

算法与程序设计的复习嘻嘻嘻蟹蟹٩('ω')و 

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/凡人多烦事01/article/detail/629988
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号