最短路径问题及其解法研究

摘要:最短路径问题是在给定的网络图中寻找出一条从起始点到目标点之间的最短路径。该文分别从动态规划、Dijkstra、A*算法、遗传算法这四种算法设计方法入手,概述了各种设计方法的原理,提出了求解最短路径的算法思想,并对算法进行分析,提出了改进方法。

关键词:最短路径;动态规划;Dijkstra算法;A*算法;遗传算法

Shortest Path Problem and its Solution Methods Study

ZHOU Xian-shu

(People's Liberation Army 75742 Units, Guangzhou 510515, China)

Abstract: Shortest path problem is to find a shortest path from the start point to the end point in a given net graph. This paper will introduce four algorithm design methods, which are Dynamic programming, Dijkstra algorithm, A-star algorithm, Genetic algorithm, summarize their basic tenets, give the solving algorithm thought to the shortest path problem, analyse the algorithms and put forward the improving methods.

Key words: shortest path; dynamic programming; Dijkstra algorithm; A-star algorithm; genetic algorithm

最短路径问题是在给定的网络图中寻找出一条从起始点到目标点之间最短路径。最短路算法不仅在 GIS 的交通路线导航、路径分析领域应用广泛, 在解决路径搜索相关的应用中也十分普遍, 包括网络路由算法、机器人探路、人工智能、游戏设计等等。本文分别从动态规划、Dijkstra、A*算法、遗传算法这四种算法设计方法入手,概述了各种设计方法的原理,提出了求解最短路径的算法思想,并对算法进行分析,提出了改进方法。

1 最短路径的搜索算法概要

1.1 动态规划算法

动态规划算法的基本思想是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。动态规划算法使用于解最优化问题。通常可以按以下步骤设计动态规划算法:

1)找出最优解的性质,并刻画其结构特征;

2)递归地定义最优解;

3)以自底向上的方式计算出最优解;

4)根据计算最优值时得到的信息,构造最优解。

步骤1)~3)是动态规划算法的基本步骤。在只需要求最优值的情形,步骤4)可以省去。若需要求问题的最优解,则必须执行步骤4),此时,在步骤3)中计算最优解时,通常需记录更多的信息,以便在步骤4)中,根据所记录的信息,快速构造出最优解。

1.2 Dijkstra算法

Dijkstra算法是Dijkstra提出的一个按路径长度递增的顺序逐步产生最短路径的算法。该算法的基本思想是:设置两个定点的集合T和S,集合S中存放已找到最短路径的定点,集合T中存放当前还未找到的最短路径的定点。初始状态时,集合S中只包含原点v0,然后不断从集合T中选取到定点v0路径长度最短的顶点u加入集合S,集合S中每加入一个新的顶点u,都要修改定点v0到集合T中剩余顶点的最短路径长度值,集合T中个顶点新的最短路径长度值为原来的最短路径长度值与定点u的最短路径长度值加上u到该顶点的路径长度值中的较小值。次过程不断重复,直到集合T的顶点全部加入到集合S为止。

1.3 A*算法

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

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

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

1.4 遗传算法

遗传算法是一类借鉴生物界自然选择和自然遗传机制的随机化的搜索算法, 由美国 J.Holland 教授提出, 其主要特点是群体搜索策略、群体中个体之间的信息交换和搜索不依赖于梯度信息。因此它尤其适用于处理传统搜索方法难于解决的复杂和非线性问题。遗传算法是一种群体型操作, 该操作以群体中所有个体为对象。选择、交叉和变异是遗传算法的三个主要算子, 他们构成了遗传算法的主要操作, 使遗传算法具有了其它传统方法所没有的特性。

2 最短路径问题的提出

如图1,给定一个运输网络,两点之间连线上的数字表示两点间的距离。求一条从A到E的运输线路,使总距离为最短。

3 求解最短路径问题

3.1 利用动态规划解最短路径问题

3.1.1 算法实现

图1中,过程的始点是A,终点是E,过程的实际行进方向是由A经第1,2, 3, 4阶段到达终点E。

在第4阶段有两个初始状态D1和D2。那么,从A-E的全过程最短路径,在第4阶段究竟经过D1、D2中的哪一个呢?目前,我们还不得而知,因此只能各种可能都考虑:若全过程最短路径经过D1,,则有f(D1)=4;若全过程最短路径经过D2,则有f(D2)=3。

第3阶段假设全过程最短路径在第3阶段经过C1点,则有:

若由C1―D1―E,则有d3(C1,D1)+f4(D1)=4+4=8;

若由C1―D2―E,则有d3(C1,D2)+f4(D2)=6+3=9;因此,由C1到E的最短路径是由C1―D1―E ,最短距离是f3(C1) = 8。

假设全过程最短路径在第3阶段经过C2点,则有:

f3(C2)=min{[d3(C2,D1)+f4(D1)],[d3(C2,D2)+f4(D2)]}=7;因此,由C2到E的最短路径是由C2―D1―E,最短距离是f3(C2)=7。

同理由C3到E的最短路径是由C3-D1-E和C3-D2-E,最短距离是f3(C3)=6。

同理,可得到第2阶段由B到E的最短路径有三条:B1到E:B1―C2―D1―E或B1―C3―D1\2―E,最短距离都是14;B2到E:B2―C1―D1―E,最短距离是11;B3到E:B3―C3―D1\2―E,最短距离都是13。

第一阶段,计算如下:

f1(A)=min{[d1(A,B1)+f2(B1)],[d1(A,B2)+f2(B2),[d1(A,B3)+f2(B3)]}=15

因此,由A--E的全过程最短路径是A―B2―C1--D1--E,最短距离是15。

3.1.2 算法分析及改进

利用动态规划求解最短路径问题的复杂度为O(min{nc,2n})。动态规划主要是求解最优决策序列, 当最优决策序列中包含最优决策子序列时, 可建立动态规划递归方程, 它可以帮助高效地解决问题。用动态规划方法不仅能得到全局最优结果,还能得到一族最优结果。有了这一族最优结果,便于分析、比较不同的结果,且如果由于某种原因偏离了原始最优轨迹,也可以很方便地找出余下阶段的新的最优子策略。

3.2 利用Dijkstra算法解最短路径问题

3.2.1 算法实现

将图1采用邻接矩阵来存储,设为有向网G=(V,E);若邻接矩阵问C,并规定:

为wij表示顶点i和顶点j之间有直接边,且权值问wij,为0表示i = j,同一个顶点。为∞表示顶点i和顶点j没有边。

设置一个一维数组S,用来标记已找到的最短路径的顶点,并规定:

S[i]=0表示未找到源点到顶点vi的最短路径;

S[i]=1表示已找到源点到顶点vi的最短路径;

初始状态时,S[0]=1,对于其余的顶点vj(vj≠v0),有S[j]=0;设置另一个一维数组D,用来存放源点到其余各顶点的当前最短路径长度。初始状态时,D[i]=C[ORG(v0)][i](其中ORG(v0)表示源点v0在存储结构中的位置号),即一维数组D各分量的值为邻接矩阵C中ORG(v0)行上各元素的值。

首先利用D数组中各分量的值,选取当前具有最短路径的顶点u,使得,

然后将顶点u加入集合S中,即令S(u)=1,同时对于所有的S[i]=0的顶点vi,判断D[i]是否小于D[u]+C[u][i],使得

D[i]=min{D[i],D[u]+C[u][i]}

上述过程重复执行n-1后,就得到了按路径长度递增的顺序求源点到其余各顶点的最短路径值。

3.2.2 算法分析及改进

Dijkstra算法的成功率是最高的,因为它每次必能搜索到最优路径。另一方面,有利必有弊,如果要找到最优路径必然要在速度上做出牺牲。这导致Dijkstra算法的搜索速度是最慢的。Dijkstra算法求一个点到其他所有点的最短路径复杂度为O(n2),求一个点到其他所有点最短路径等效于求一个点到另一个点的最短路径n个点之间互相的最短路径复杂度为O(n3)。

3.3 A*算法解最短路径问题

3.3.1 算法实现

A*算法的基本思想是:

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.3.2 算法的分析与改进

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

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

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

3.4 遗传算法解最短路径问题

3.4.1 算法实现

1) 编码方案:设aij表示第i个结点到第j个结点的路径信息,l

2) 初始群体的生成:将个体初始化成零个体,即置个体点的集合信息为:al=0,ai=0(0≤i≤N-1),ai=N(i=N),对每个个体作同样操作。然后对整个群体进行初始化。

3) 适应度函数的设计:根据个体所指示的路径信息,判断这条路径中没两个点间的距离大小,,若两点间存在路径且没有到达最后一个点,则将适应值的值加上当前两点间的路径长度,若不存在连线,则将适应值加上惩罚值,最后保存该个体的适应值,以便在选择时进行优先选择。对每一个个体进行此操作,直到整个群体适应度求解完毕。最后根据计算结果确定是否更新最小路径信息。

4) 选择操作: 算法中选择机制采用适应度比例法(即赌轮选择)实现选择。设群体大小为n,其中个体i的适应度fi,则i被选择的概率Psi为:

概率Psi反映了个体i的适应度在整个群体的个体适应度总和中所占的比例。按式(1)计算出群体中各个个体的选择概率。

5) 交叉操作:文中采用一点交叉,但因路径交叉以后出现实际不存在的路径,所以对交叉采取一定的限止措施,防止交叉后出现不存在的路径。并对生成的新个体做相应的修正,使其成为满足条件的新个体。

6) 变异操作:文中采用常规变异策略,变异后再根据确定的位对原来的个体进行修正,防止出现不存在的路径,避免程序发生异常。

7) 程序进行选择与交叉过程中,根据运行前指定的参数,对群体中一定概率的最优个体进行了直接保留,从而大大提高了优秀个体被保留的概率,提高了算法的搜索效率。

4.4.2 算法的分析与改进

利用遗传算法求解最短路径问题具有与传统方法不同的效益, 它可以获得最优解, 解决传统算法设计方法所不能解决的问题。该算法的复杂度为: O(n2n)。对于遗传算法的改进体现在基于惩罚函数修正方法和译码方法上, 通过修正得到最优解。

4 各种算法设计方法比较

通过以上对最短路径问题的求解分析, 我们可以看到各种算法设计方法有各自不同的特点, 针对不同的问题领域,它们有不同的效率。对于求解最短路径问题, 各算法的时间复杂、优缺点以及改进方法的比较如表1所示。

5 结束语

以上是对动态规划,Dijkstra算法,A*算法,遗传算法这四种常用算法设计方法原理的概要介绍, 并具体应用于求解最短路径问题中, 以及对各种设计方法的算法分析。通过论述研究, 得出各种算法在求解特定问题领域的优缺点和改进方法。

参考文献:

[1] 余祥宣,崔国华,邹海明.计算机算法基础[M].武汉:华中科技大学出版社,2003.

[2] 王志和,凌云.Dijkstra最短路径算法的优化及其实现[J].软件时空,2007(11).

[3] 王凌.智能优化算法及其应用[M].北京:清华大学出版社,2001.

[4] 陈圣群,滕忠坚,洪亲,等.四种最短路径算法实例分析[J].开发研究与设计技术,2007(7).

[5] 梁娟,郭军丽,魏勇.利用动态规划算法求解最短路径[J].河南机电高等专科学校学报,2006(5).

[6] 江务学,李成银,李黎明.一种基于遗传算法的网络最短路径的求解[J].沙洋师范高等专科学校学报,2007(3).