v k 的可达到最短路径长度, 如果 d k > d j + c jk
则修改 d k 为: d k = d j + c jk 4) 重复操作 2, 3 公 n - 1 次, 由此求得按路 径长度递增次序排列的从出发至图中其余各顶 点的最短路径序列。 以上算法将产生从源点出发至其余各顶点 的最短路径。 对于路径规划而言, 我们只需要从 源点至制定终点的一条路径, 为此可将算法作简 单的修改。 设目标路径终点为v t i, 则在操作2 中, 如果发现v j = v t , 算法即终止, 此时与d t 对应的路 径就是从源点 v s 至终点 v t 的最短路径。
1 引 言
路径规划是帮助驾驶员在旅行前或者旅行 中规划行使线路的过程, 是车辆导航中的一个基 本问题, 也是实现导航功能的前提条件。 在复杂环境下的车辆导航系统中, 尽管人们 尝试用神经网络、 遗传算法等方法来解决路径规 划问题, 并取得一定成功。 但是由于这些算法在 实时性、 收敛速度等方面的一系列缺点, 使得复 杂环境下的路径规划问题却一直没有得到很好 的解决。 文中正针对这一问题, 提出一种基于 D ijk st ra 算法的最优路径规划新算法。
[ 关键词 ] 车辆导航; 路径规划; 图论; D ijk stra 算法 [ 中图分类号 ] P 228. 42 [ 文献标识码 ] A
An O pti m a l Pa th P lann ing A lgor ithm in Com plex Env ironm en t Veh icles Nav iga tion System
i
的路径就是从v 出发的长度最短的一条路径。设
S 为已求得的最短路径的终点的集合, 则可以证
明: 下一条最短路径 ( 终点为 x ) 或者是弧 < v , x > , 或者是中间只经过 S 的终点而最后到达顶点
x 的路径。 因此, 下一条长度次短的最短路径的
长度必为:
d j = m in {d j v i ∈ S }
与之相关的问题就可利用图论的方法进行分析。
3 最短路径问题与D ijk st ra 算法
给定带权有向图G = (V {E } ) , 其中V 是包含
n 个顶点的顶点集, E 是包含 m 条弧的弧集, < v , Ξ> 是 E 中从 v 至 Ξ 的弧, c< v , Ξ> 是弧< v , Ξ
顶点 v ′ , 顶点 v ′ 邻接自顶点 v , 且弧< v , v ′ > 与顶 点v 和v′ 相关联。 ( 4) 度: 在无向图中, 顶点v 的度是指与顶点 v 相关联的边的数目, 记为TD ( v ) 。在有向图中, 顶点 v 的度是指与顶点 v 相关联的弧的数目, 其 中以 v 为头的弧数目称为 v 的入度, 记为 ID ( v ) ; 以v 为尾的弧数目称为v 的出度, 记为OD (v ) ; 顶 点v 的度等于二者之和, 即TD (v ) = ID (v ) + OD ( v ) 。对于一个有 n 个顶点和 e 条边或弧的图, 若 记其中顶点 i 的度为 TD ( v i ) , 则有:
< v ij - 1 , v ij > ∈E , 1≤ j ≤n。 路径的长度是指路径
上的边或弧的数目。 序列中第一个顶点和最后一 个顶点相同的路径称为回路或环。 序列中顶点不 重复出现的路径称为简单路径。 ( 7) 连通: 在无向图中, 如果从顶点 v 到v ′ 有 路径存在, 则称 v 和 v ′ 是连通的。 图中任意两个 顶点都连通的无向图称为连通图。 在有向图中, 如果从顶点 v 到顶点 v ′ 有路径存在, 则称 v ′ 相对 于v 是可到达的; 如果从v 到v ′ 和从v ′ 到v 都存在 路径, 则称 v 和 v ′ 是连通的。 图中的每一对顶点 都连通的有向图称为强连通图。 ( 8) 权与网: 如果图的边和弧具有与之相关 的数, 则这种与边或弧相关的数就称为边或弧的 权。 权可以用来描述从一个顶点到另一个顶点的 距离或花费。 带权的图就称为网, 其中的顶点称 为节点。 如果把道路交通网中的道路起点、 终点和交 叉口表示为节点, 把道路表示为连接节点的弧, 把道路的长度、 通行时间等属性表示为道路的 权, 那么道路网就被抽象成为带权的有向图, 而
1 2
n
∑T D (v )
i i= 1
( 5) 子图: 假设有两个图 G = (V , { E } ) 和 G ′ = (V ′ , {E ′ } ) , 如果V ′ Α V 且E ′ Α E , 则称图G ′ 为 图 G 的子图。 ( 6) 路径: 在无向图中G = (V , {E } ) , 顶点序 ) 称为从顶点 v 到顶点 v ′ 列 ( v i0 = v , v i1 , + , v in = v ′ 的一条路径, 其中 ( v ij - 1 , v ij ) ∈E , 1≤ j ≤n。 如果 是有向图, 则路径也是有向的, 顶点序列应满足
e=
> 的非负权值, 设 v s , v t , 为V 中的顶点, P st = { v 0 = v s , v 1 + , v n = v t } 为 V 中由 v s 到 v t 的一条路径,
则路径的权值总和可表示为:
n- 1
TW ( P st ) =
∑) c (v , v
i i= 0
i+ 1
)
Ξ 收稿日期: 2004211209
或初始点, 称 y 为弧头或终端点, 此时的图称为 有向图。 若V R 是对称的, 既有< x , y > ∈V R , 又 有< y , x > ∈V R , 则以无序对 ( x , y ) 代替这两个 有序对, 称为从 x 到 y 的一条边, 此时的图称为 无向图。
d j = m in {d i v i ∈ V - S }
i
1) 初次运算, 不考虑 v 1 , 因为 v 1 到本节点权 值为零 d 2 = m in {d i v i ∈ V - S } = 10
i
则 v 2 就是当前从 v 1 出发的最短路径的终点。 令
S = {v 2 }
则 v j 就是当前从 v s 出发的最短路径的终点。 令 S = S U {v j } 3) 修改从 v s 出发到集合V - S 中任一顶点
・10・
弹箭与制导学报
2005 年
( 3) 邻接与关联: 对于无向图G = (V , {E } ) , ) ∈E , 则称v , v ′ 若有边 ( v , v ′ 互为邻接点或v 和v ′ ) 依附于顶点 v 和 v ′ 相邻接; 且边 ( v , v ′ , 或称边 ) 与顶点v 和v ′ (v , v ′ 相关联。 对于有向图G = (V , ) {A } , 若有弧< v , v ′ > ∈A , 则称顶点 v 临接到
ZHAN G Y i ( In stitu te of E lectron ic Info rm a tion, N o rthw estern Po lytechn ica l U n iversity, X i’ an 710072, Ch ina ) Abstract: T h is p ap er discu sses a new a lgo rithm in so lu tion of op ti m a l p a th p lann ing fo r com p lex environm en t. W e first in troduce som e theo ries abou t p a th p lann ing and som e concep t abou t grap h theo ry, then w e discu ss in deta il D ijk stra a lgo rithm in the sho rtest p a th p rob lem so lu tion , and describe in som e deta il its p rocess. F ina lly, the exp eri m en t resu lts a re given. Key words: veh icle naviga tion; p a th p lann ing; grap h theo ry; dijk stra a lgo rithm
i
其中d i 或者是弧< v , v i > 的权值, 或者是d k ( v k ∈ S ) 和弧< v k , v i > 的权值之和。 根据以上原理可 得到如下描述的最短路径生成算法: 1 ) 利用邻接矩阵C 来表示带权有向图G , 其 元素 c ij 表示弧< v i , v j > 的权值; 若弧< v i , v j > 不 存在, 则将 c ij 设为∞。令S 为已找到从 v s 出发的 最短路径的终点的集合, 将其初始化为空集。 d i 用表示从 v s 出发到终点 v i 的可能到达的最短距
所谓最短路径问题就是指在带有权的有向 图中, 寻找从指定起点到终点的一条具有最小权 值总和的路径问题。 如果把权值看成是弧的长度 ( ) 属性 距离 , 那么目标路径就是从起点到终点的 最短路径。 如果把路径规划中的优化标准量化为 道路的旅行代价, 则最优路径规划就可以总结为 在特定道路网中寻找具有最小旅行代价总和的 最优路径问题。 首先讨论单源点最短路径问题, 即给定带权 有向图G = (V , {E } ) 和源点 v , 求 v 到G 中其余各 顶点的最短路经。 关于这一问题, D ijk st ra 提出 了按路径长度递增的次序产生最短路径的算法, 其产生最短路径的原理如下: 首 先设置一个辅助向量D , 它的每个分量 d i 表示当前所找到的从起点到每个终点的最短路 径的长度。设置D 的初始状态为: 若从 v 到 v i 有 弧, 则 d i 为弧上的权值; 否则令d i 为∞。显然, 长 度为: d j = m in {d i v i ∈ V }