单源路径分支界限java_分支限界法—单源最短路径问题

喜欢ヅ旅行 2022-11-07 05:48 180阅读 0赞

转自：http://www.cnblogs.com/chinazhangjie/archive/2010/11/01/1866136.html

分支限界法与回溯法

(1)求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。

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

分支限界法的基本思想

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

在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。

此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。

常见的两种分支限界法

(1)队列式(FIFO)分支限界法

按照队列先进先出(FIFO)原则选取下一个结点为扩展结点。

(2)优先队列式分支限界法

按照优先队列中规定的优先级选取优先级最高的结点成为当前扩展结点。

一、单源最短路径问题

1、问题描述

在下图所给的有向图G中，每一边都有一个非负边权。要求图G的从源顶点s到目标顶点t之间的最短路径。

![21a3dc138afe836ff2dd8a33771015aa.png][]

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

![6baf800fe01f1b0bdf00081984131a6a.png][]

找到一条路径：

![341fb2f92b079eb55652ba93293632e9.png][]

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

![cf537676d97ebb15b84a1fef4e02ff8a.png][]同一个结点选择最短的到达路径：

![b8b7d7edddcffbf7d9d6a7bbbffb9141.png][]

![60449c79140d2ea0f3d774eec1646cd2.png][]

2.剪枝策略

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

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

3.算法思想

解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。

算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。

实现

![8f900a89c6347c561fdf2122f13be562.png][]

![961ddebeb323a10fe0623af514929fc1.png][]

1 2.剪枝策略在算法扩展结点的过程中，一旦发现一个结点的下界不小于当前找到的最短路长，则算法剪去以该结点为根的子树。 在算法中，利用结点间的控制关系进行剪枝。从源顶点s出发，2条不同路径到达图G的同一顶点。由于两条路径的路长不同，因此可以将路长长的路径所对应的树中的结点为根的子树剪去。 3.算法思想解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。实现2 /\*主题：单源最短路径问题3 \* 作者：chinazhangjie4 \* 邮箱：chinajiezhang@gmail.com5 \* 开发语言：C++6 \* 开发环境：Mircosoft Virsual Studio 20087 \* 时间: 2010.11.018 \*/

10 \#include

11 \#include

12 \#include

13 \#include

14 using namespacestd;15

16 structnode\_info17 \{18 public:19 node\_info (int i,intw)20 : index (i), weight (w) \{\}21 node\_info ()22 : index(0),weight(0) \{\}23 node\_info (const node\_info &ni)24 : index (ni.index), weight (ni.weight) \{\}25

26 friend27 bool operator < (const node\_info& lth,const node\_info&rth) \{28 return lth.weight > rth.weight ; //为了实现从小到大的顺序

29 \}30

31 public:32 int index; //结点位置

33 int weight; //权值

34 \};35

36 structpath\_info37 \{38 public:39 path\_info ()40 : front\_index(0), weight (numeric\_limits::max()) \{\}41

42 public:43 intfront\_index;44 intweight;45 \};46

47 //single source shortest paths

48 classss\_shortest\_paths49 \{50

51 public:52 ss\_shortest\_paths (const vector >& g,intend\_location)53 :no\_edge (-1), end\_node (end\_location), node\_count (g.size()) , graph (g)54 \{\}55

56 //打印最短路径

57 void print\_spaths () const\{58 cout << "min weight :" << shortest\_path < (cout, " "));62 cout <

65 //求最短路径

66 voidshortest\_paths () \{67 vectorpath(node\_count);68 priority\_queue >min\_heap;69 min\_heap.push (node\_info(0,0)); //将起始结点入队

71 while (true) \{72 node\_info top = min\_heap.top (); //取出最大值

73 min\_heap.pop ();74

75 //已到达目的结点

76 if (top.index ==end\_node) \{77 break;78 \}79 //未到达则遍历

80 for (int i = 0; i < node\_count; ++i) \{81 //顶点top.index和i间有边，且此路径长小于原先从原点到i的路径长

82 if (graph\[top.index\]\[i\] != no\_edge &&

83 (top.weight + graph\[top.index\]\[i\])

94 shortest\_path =path\[end\_node\].weight;95 int index =end\_node;96 s\_path\_index.push\_back(index) ;97 while (true) \{98 index =path\[index\].front\_index ;99 s\_path\_index.push\_back(index);100 if (index == 0) \{101 break;102 \}103 \}104 \}105

106 private:107 vector > graph ; //图的数组表示

108 int node\_count; //结点个数

109 const int no\_edge; //无通路

110 const int end\_node; //目的结点

111 vector s\_path\_index; //最短路径

112 int shortest\_path; //最短路径

113 \};114

115 intmain()116 \{117 const int size = 11;118 vector >graph (size);119 for (int i = 0;i < size; ++i) \{120 graph\[i\].resize (size);121 \}122 for (int i = 0;i < size; ++i) \{123 for (int j = 0;j < size; ++j) \{124 graph\[i\]\[j\] = -1;125 \}126 \}127 graph\[0\]\[1\] = 2;128 graph\[0\]\[2\] = 3;129 graph\[0\]\[3\] = 4;130 graph\[1\]\[2\] = 3;131 graph\[1\]\[5\] = 2;132 graph\[1\]\[4\] = 7;133 graph\[2\]\[5\] = 9;134 graph\[2\]\[6\] = 2;135 graph\[3\]\[6\] = 2;136 graph\[4\]\[7\] = 3;137 graph\[4\]\[8\] = 3;138 graph\[5\]\[6\] = 1;139 graph\[5\]\[8\] = 3;140 graph\[6\]\[9\] = 1;141 graph\[6\]\[8\] = 5;142 graph\[7\]\[10\] = 3;143 graph\[8\]\[10\] = 2;144 graph\[9\]\[8\] = 2;145 graph\[9\]\[10\] = 2;146

147 ss\_shortest\_paths ssp (graph, 10);148 ssp.shortest\_paths ();149 ssp.print\_spaths ();150 return 0;151 \}

测试数据(图)

![ba2cfea389ca2ab0851c01ca4dfe551b.png][]

测试结果

min weight : 8

path: 0 2 6 9 10

[21a3dc138afe836ff2dd8a33771015aa.png]: /images/20221023/c59dc219589a489eb0ec00524b89a4ee.png
[6baf800fe01f1b0bdf00081984131a6a.png]: /images/20221023/dba0b72502434267acddb786ad3a3ac0.png
[341fb2f92b079eb55652ba93293632e9.png]: /images/20221023/eb9fdd5f9b8f4b1b806bc1903c9e604c.png
[cf537676d97ebb15b84a1fef4e02ff8a.png]: /images/20221023/8dd5cd1a69c24e79b8534410c360ad15.png
[b8b7d7edddcffbf7d9d6a7bbbffb9141.png]: /images/20221023/468525284cfb441ea47714b91ed8d103.png
[60449c79140d2ea0f3d774eec1646cd2.png]: /images/20221023/6c450e110a214f5fadfa24fb275b2d1f.png
[8f900a89c6347c561fdf2122f13be562.png]: /images/20221023/82378ed3e9bb457987e276efd8260f11.png
[961ddebeb323a10fe0623af514929fc1.png]: /images/20221023/77b3eee028934bf8a9faf41d8d5c4aed.png
[ba2cfea389ca2ab0851c01ca4dfe551b.png]: /images/20221023/e8ebabdff8b84c2f8eaa902998f372b6.png