四种最短路径算法实例分析

摘要：通过理论分析，结合实际应用，在GIS节点数很大的数字地形图中，从完备性、最优性、时间复杂度、空间复杂度几种性能问题实例分析，较系统地总结出深度优先搜索(DFS)、广度优先搜索(BFS)、双向广度优先搜索(DBFS)、A*算法四种算法代价及优缺点。

关键词：最短路径算法；深度优先搜索；广度优先搜索；双向广度优先搜索；A*算法

中图分类号：TP312文献标识码：A文章编号：1009-3044(2007)16-31030-03

The Case Analysis of Four Shortest Path Algorithm

CHEN Sheng-qun,TENG Zhong-jian,HONG Qing,CHEN Qing-hua

(Key Laboratory of OptoElectronic Science and Technology for Medicine,Ministry of Education,Fujian Normal University, Fuzhou 350007,China)

Abstract:Throughout theoretical analysis,connected with practical application,we compared these performance problem such ascategoricalness,optimality,time complexity, space complexity in GIS(Geographic Information Systems) digital relief mapwhich have many nodes.Then sum up systemicly the algorithm cost and The superiorities and deficiencies of Depth First Search(DFS),Breadth First Search(BFS),Double Breadth First Search(DBFS),A-star.

Key words:shortest path algorithm;Depth First Search;Breadth First Search;Double Breadth First Search;A-star algorithm

1 引言

最短路算法不仅在GIS的交通路线导航、路径分析领域应用广泛，在解决路径搜索相关的应用中也十分普遍，包括网络路由算法、机器人探路、人工智能、游戏设计等等。

在搜索问题中，主要的工作是找到正确的搜索策略。一般搜索策略可以通过下面4个准则来评价[1]。

完备性：如果存在一个解答，该策略是否保证能够找到？

时间复杂性：需要多长时间可以找到解答？

空间复杂性：执行搜索需要多少存储空间？

最优性：如果存在不同的几个解答，该是否可以发现最高质量的解答？

2 最短路径的搜索算法

2.1深度优先搜索

深度优先搜索总是扩展搜索树的当前边缘中最深的节点，当那些节点扩展完之后，它们被边缘中去掉，然后搜索算法“向上回到”下一个还有末扩展后继节点的稍浅的节点[1]。本算法和一般教科书中不同，它遍历图所有分枝，以找出最优解。一般教科书深度优先搜索算法不是最优解。

算法如下：

Procedure Depth First Search

Begin

(1)把初始节点压入栈，并设置栈顶指针；

(2)While 栈不空do

Begin

弹出栈顶元素；

If 栈顶元素==goat,更新源节点到目节点的最短路径；/*为了遍历图所有分枝，故不是直接成功返回并结束*/

Else以任意次序把栈顶元素的子女压入栈中；

End While

End

2.2广度优先搜索

广度优先搜索是一个简单的搜索策略，首先扩展根节点，接着扩展根节点的所有后继，然后再扩展它们的后继，依此类推[1]。一般来讲，在下一层的任何节点扩展之前搜索树上本层尝试的所有节点都已经扩展过。BFS和DFS两种算法每次都扩展一个节点的所有子节点，而不同的是，深度搜索下一次扩展的是本次扩展出来的子节点中的一个，而广度搜索扩展的则是本次扩展的节点的兄弟节点。算法如下:

Procedure Breadth First Search

Begin

(1)把初始节点放入队列；

(2)While 队列不空do

Begin

取得队列最前面的元素为current；

If current==goat,成功返回并结束；

Else

If current有子女，把它的子女以任意次序添加到队列的尾部；

End While

End

2.3双向广度搜索

所谓双向广度搜索指的是搜索沿两个力向同时进行：正向搜索：从初始结点向目标结点方向搜索；逆向搜索：从目标结点向初始结点方向搜索；当两个方向的搜索生成同一子结点时终止此搜索过程。

算法说明：

设置两个头指针head:array[0..1] of integer 分别表示正向和逆向当前将扩展结点的头指针。

设置两个尾指针tail:array[0..1] of integer 分别表示正向和逆向的尾指针。

maxn表示队列最大长度。

算法如下：

Procedure Double Breadth First Search

Begin

Repeat

{选择节点数较少且队列未空、未满的方向先扩展}

if (tail[0]=tail[0])or(tail[0]>=maxn))

then expand(0);

if (tail[1]=tail[1])or(tail[1]>=maxn))

then expand(1);

{如果一方搜索终止，继续另一方的搜索，直到两个方向都终止}

if not((head[0]>=tail[0])or(tail[0]>=maxn)) then expand(0);

if not((head[1]>=tail[1])or(tail[1]>=maxn)) then expand(1);

Until ((head[0]>=tail[0])or(tail[0]>=maxn)) And ((head[1]>=tail[1])

or(tail[1]>=maxn))

End

2.4 A*算法

A*算法则是人工智能领域的一种图搜索策略，采用了启发式函数对搜索过程中产生的分支进行评估，以选择最佳的分支进行搜索。其更一般的引入了一个估价函数f(n),其定义为f(n)=g(n)+h(n)。其中g(n)为到达当前节点的耗费，而h(n)表示对从当前节点到达目标节点的耗费的估计，要求评估函数满足h (n)

1. h(n)必须小于等于实际的从当前节点到达目标节点的最小耗费h*。

2. f(n)必须保持单调递增。

算法思想

Procedure A-star

Begin

(1)把源节点放入队列Q；

(2)For(i=2,i

Begin

If 队列Q为空 then 退出; 删除队列中最小代价结点current

If current==goat then 结束，找到最优;

If current有子女，源结点到本结点权值更小, 即有更新, 且该结点不在队列, 则插入；

End For

输出路费和路径

End.

3 实例分析

根据美国XX地区的模拟地图，数据放在file1.txt存放1至9292节点间的9292条边的权值,file2.txt存放各节点图坐标。各种最短路径算法和图的绘制均用mathematica5.1[4]编写实现，图的存储结构用邻接表方法。硬件配置：处理器为“Intel(R) Pentium(R) 4 CPU 3.00GHZ”,内存为“512MB”

3.1绘制地图

根据file2.txt绘制地形图，如图1所示。

3.2实际情况实验数据对比

搜索1 :(始点，终点)=（1，9292）

搜索2 :(始点，终点)=（1，4909）

搜索1和搜索2的路径图分别为图2、图3所示。

图1

图2

图3

3.3数据分析

3.3.1深度优先搜索

实现的算法是遍历图所有分枝，最终找出最优解，也属于完备解，也是最优解。对内存的需求较小，对一个分支因子为b，最大深度为m的状态空间，尝试优先搜索只要bm+1个节点[1]。最简单思路是用穷举法把所有可能的巡回路径全部列出来，最短的一个就是最优解，但花费巨大时间的，需要的扩展点也巨多的。时间复杂度为O（bm），从搜索1，2中看得出时间上的代价是相当大的。

3.3.2广度优先搜索

为了便于分析，考虑一棵树，设每个节点的分支系数都是b,最大深度为d。其中分支系数是指一个节点可以扩展产生的新的节点数目。

时间复杂度[3]：失败搜索的最小节点数目为: 1+b+b2+...+bd-1=( bd-1)/(b-1) b>>1而在找到目标节点之前可能扩展的最大节点数目为：1+b+b2+...+bd-1+bd =(bd+1-1)/(b-1)对于d层，目标节点可能是第一个状态，也可能是最后一个状态。因此，平均需要访问的d层节点数目为：(1+bd)/(b-1) 所以，平均总的搜索的结点数目为： (bd-1)/(b-1)+ (1+ bd)/2≈bd(b+1)/2(b-1) 可以看出，时间复杂度和搜索的节点数目成正比, 由于其保留了所有的前继节点，所以在产生后继节点时可以去掉一部分重复的节点，从而提高了搜索效率[3]。相对DFS来说，广度搜索是求解最优解的一种较好的方法，它并没有象DFS遍历所有分支才能找到最优解。

空间复杂度：树的所有的结点都同时需要储存起来。该算法的空间复杂度和队列长度有关，在最坏的情况下约为O(bd) , 如此多节点都要在内存中，所以耗费内存大。

3.3.3双向广度搜索

空间复杂度：广度搜索虽然可以得到最优解，但是其空间消耗增长太快。但如果从正反两个方向进行广度搜索，理想情况下可以减少二分之一的搜索量，从而提高搜索速度。

时间复杂度：双向搜索时间复杂度O(bd/2)远小于单向搜索O(bd+1)，节省了大量时间[1]。但是它并不总是可行的而且可能需要太多空间。

3.3.4A*算法

空间复杂性：A*算法生成的总节点数为N，解的深度为d,那么b*就是尝试为d的一致搜索树为了包括N+1个节点所必需的分支因子。因此，N+1=1+ b*+( b*)2+..+(b*)d，[1]从中可看出空间复杂度高。

时间复杂性：充分利用问题内在信息，启发函数设计的好，可以极大降低扩展的结点，从而在较小的时间内即可完成最佳路径搜索。

如果h(n)是可采纳的，那A*算法是完备的也是最优的。

4 结束语

我们通过对最短路径的算法的实例分析，了解基本算法和启发式的算法．同时，我们也注意到，搜索算法的评判建立在完备性、最优性、时间复杂度、空间复杂度的基础上。复杂度取决于状态空间中的分支因子b,和最浅的解的深度d。当然，具体问题具体分析，算法好坏，还得根据实际情况，而且读者还可以进一步优化，使其效果更加理想。

参考文献：

[1](美)Stuart Russell,(美)Peter Norvig著.姜哲.等译.人工智能――一种现代方法:中文版[M].人民邮电出版社,2004.

[2]王晓东.计算机算法设计与分析[M].北京:电子工业出版社,2001.

[3]王文杰,叶世伟.著.人工智能原理与应用[M].人民邮电出版社,2004.

[4]丁大正.Mathematica 5在大学数学课程中的应用[M].北京:电子工业出版社,2006.

注:“本文中所涉及到的图表、公式注解等形式请以PDF格式阅读原文。”