您现在的位置:首页 > >

最短路径搜索算法的几种优化改进

发布时间:

第 25卷第 4期 2008年 4月

计算机应用与软件 Com puter Applications and Softw are

Vo l 25 No. 4 Apr. 2008

最短路径搜索算法的几种优化改进
顾运筠
( 上海体育运动技术学院 上海 200030 )
摘 要 介绍了 G IS领域最短路径搜索的一种 优化模式。在 D ijkstra s算法的基础上, 从三个方 面改进了最短路径的计算。首先 引入了多级路线图, 在读取线路数据时, 根据路线的级别 有所选 择; 其 次, 在计算 最短距离 时考虑 速度的 影响; 最后, 在道 路的转 弯 处, 引入虚拟路径来估算转弯对汽车行驶的影响。应用以上三种方法的实验, 取得了很好的效果。 关键词 最短路径 地图 子地图 速度的影响 转弯处

SEVERAL OPTIM IZATION FOR THE SHORTEST PATH SEARCH ALGORTHM

Gu Yunyun
( Shang hai Sport Techn ique C ollege, S hangha i 200030, China )
Abstrac t A n optim ized patte rn for the sho rtest path com puta tion in G IS is presented. Based on D ijkstra s sho rtest path a lgo rithm, the shortest path com putation is optim ized in three aspec ts. F irstly, a graph subg raph structural h ierarchy is imposed on an input da ta set. Second ly, speed e ffect is taken into conside ration in the shortest pa th compu tation. F ina lly, a pseudo path is added to reckon the turn ing po in t. T he experim ent utilizing these three optim iza tion m eans has ach ieved satisfacto ry resu lts.
K eywords Sho rtest path G raph subg raph Speed e ffect T urn ing po int

0引 言
地理信息系统在 交通 (导 航 )、公 安 ( 紧急 出警 和救助 )、城 市规划 (供水、供电和供气管线的 设计等 ) 等方面具 有广泛 的应 用。最短路径问题是地理信息系统网络 分析中的最基本最关键 的问题, 在交 通网络结 构的分析, 交通运 输线路的选 择, 通 讯线 路的建造与维护, 运输货流的最小成本分析, 城市公共交通网络 的规划, 供水、供电和 供气的 规划等 方面, 都有直 接应用。 本文 探讨在公共交通中两 点之间的最短路径搜索的一种优化模型。
关于最短路径搜 索, 目前常用 的是 1959年 由 E. W. D ijkstar 提出的方法。本文对 W. D ijkstar方法作了三方面的改 进。首先 引入了多级路线图。在 读取线 路数据 时, 根 据路线 的级别 有所 选择。其次, 在计算最短距离时考虑速度的影响。最后, 在 道路 的转弯处, 引入虚拟路径来估算转弯对汽车行驶的影响。
1 算法概述
1. 1 算 法
D ijkstra方法搜 索最短路径的算法如下: 令 dj是从起 点 S 到 j点的最短路径, p j是从 S 到 j点的最短 路 径的前一点, E 为终点, 则起点 S到终点 E 的 D ijkstra算法为: ( 1) 初始化: a) 读取地图数据: 节点数据和 线路数据 b) 起始点设置: ds = 0, p s 为空 c) 所有其他点: d i = 0, p i 为空

d) 标记起始点为己检索点 S , 记 k = S ( 2) 搜索从全部已检索的点 k到与其直接相连的未检索 点 j的距离, 求最短距离 dj :
dj = m in[ dj, dk + lkj ] 其中 lkj 为 k 点到 j 点的距离。
( 3) 取下一点。从所有未检索 的点中, 选取 dj 中最小的 一 个 i:
di = m in[ dj, 所有未检索的点 j] 节点 i就被选为最短路径中的一点, 并标记为已检索的。 ( 4) 找到点 i的前一点。从已检索 的点中找 到直接连接 点 i的点 j* 。作为前一点, 设置:
i = j* ( 5) 标记检索点 i。如果 i = E , 则算法完成; 否则, 记 k = i, 转到步骤 ( 2)再继 续。
1. 2 数据结构
节点数据文件和线路数据文件的格式如下: 1) 节点数据文件格式 (数据为虚拟的 ):

节点序号

经度 ( lon)

纬度 ( lat)

C1

39

137

C2

51

222

C3

2 04

222

!

!

!

2) 线路数据文件格式:

收稿日期: 2006- 06- 15。顾运筠, 硕士, 主研领域: 软件的应用。

第 4期

顾运筠: 最短路径搜索算法的几种优化改进

247

节点 1序号 节点 2序号

线路距离

线路角度

C1

C2

9545. 635

1. 430547

C6

C3

8673. 522

1. 5708

C2

C3

12643. 44

0

!

!

!

!

其 中角度为 平面图中相 当于 x 轴的弧 度, 距 离的计算 公式 如下:
D is = 111. 199 ? (L at1- La t2 ) 2 + ( (L on 1- L on2 ) ?Cos ( ( La t1 + L at2) ? 0. 00872665) ) 2

2 算法的改进

2. 1 在数据输入时应用多级地图
根 据线路的级 别的不同 , 在实 际道路交 通图中可以 把线路 划分 成三个等 级: 0级: 高 速公 路 ( 省级 公 路 ) ; 1级: 城市 主 干 道 ; 2级: 所有道路 。本 文中 为了 简 化模 型采 用 了两 级 线路 作 一 个说明, 起到抛砖 引玉的作 用。使用的 虚拟地图如 图 1 粗线 表 示的是 1级地 图, 细线表示的 是 2级地图 。在读取数据 时取 三 个范围的数 据。在起始 点 S 周围 , 以 起 始点 为圆 心范 围, 读 取 1 级和 2级地图 的节点和 线路数 据; 在 结束 点 E 周围, 以 结 束点 为圆心范 围, 读 取 1级 和 2级 地图 的 节点 和线 路数 据; 以 起 始点和结束 点的连线 的中点 Cen ter为圆心, 起始 点 S 到 中点 Center的距离 D cs 加上扩展距 离 D se 为 半径, 仅读取 1级地 图的 数据 。这样仅在 起 始 点和 结 束点 读 取两 极 地 图的 数 据, 而 在 起 始点和结束 点中间地带 只读取 1级地图 的数据, 就可以 减少 数 据的读入量 , 加快 计算速 度。如 从上 海 到北 京, 就只 要读 取 上 海起始点附 近的 0、1、2 三级地图, 北京 结束 点附 近的 0、1、2 三 级地图, 而在中间 地带只要 读取 0级地图即 可。要注意 的是 数 据不能重复 。
在虚拟地图中根 据上述数 据读入 法进行计 算, 求得的 起始 点 S 到结束点 E 的最短路 径如图 2所示。由 图可以 看出, 起始 点 S 到结束点 E 之间 取的是 1级地 图, 所以最 短路 径没 有走 2 级线路。

图 2 取两级地图时最短距离计算结果
2. 2 速度的影响
由于在 1级道路和 2级 道路汽 车行驶的 速度 不同, 所以 在 计算 2级道路的节点之间的距离时引 入速度因子 ( > 1 )。 实际计算时 2级线路的节点之间的距离为:
dj = dj 速度因子对最短距离的影响的实验效果如图 3所示。为 了 显示速度因子的影响, 在读取节点和线路数据时, 把两级地图 的 数据全部读取。虚线为不用速度因子时, 所计算出的最短路径。

图 1 实验用地图

图 3 速度因子对最短距离的影响

2. 3 转弯的影响

在转弯的地方, 汽车往往要花更多的时间。在本文中, 用 虚 拟路径来代表转弯。虚拟路径的长度根据转弯的角度大小来 决

定。两条路径之 间的 角度 取 0, 180# , 用 0, 表示。 角

度越大转弯的虚拟路径越短。改进的距离计算公式为:

Shor tPa thL eng th = Sho rtP athLength + ! ? ( - j ) 转弯处优化前后计算的最短距离如图 4所示。没有优化 以 前从起点 S 到终点 E 的路线经过虚线标 出的路线, 要转四个弯。

优化以后从起点 S 到终点 E 的路 线经过 实线标 出的路 线, 只 转 两个弯。为了说明 问题, !植 相对 取得 较大。在 实际应 用中 !

需要经过实践合理取值。

( 下转第 278页 )

2 78

计算机应用与软件

2008 年

4 应用实例
以两个简单的实例说明 OpenCV 在图像处 理方面的强 大功 能及其 在 图 像 处 理 中 的 应 用。两 个 实 例 均 在 Borland C + + Bu ilde r 6. 0环境下实现。
4. 1 实例 1
利用 OpenCV 实现图像的 边缘提取。按照前面介 绍的方法 配置 OpenCV 应用环境, 同时在程序的 前面加 上头文 件 cv. h及 h ighgu.i h。该例简单, 边缘检测可以调用函数 cvCanny, 通过 cv LoadIm age调入 图像 及 cvShow Im age 显示 处理 结 果。原 始的 灰 度图像及处理结果如 图 1所示。

参 考文 献
[ 1 ] Y u Q ingcang, Ch engH arry H, Ch engW ayn eW, et a.l CH O penCV for In teractive O pen A rch itectu re C om pu ter V ision[ J] . A dvances in Engi neering Softw are, 2004, 35 ( 9) : 527 536.
[ 2 ] Y u Q ingcang, Cheng H arryH, Cheng W ayneW, et a.l In teractive O pen A rch itectu re C ompu ter V ision[ C ]. 15th IEEE International C on feren ce on Tools w ith A rtificial Intell igen ce ( ICTA I 03 ) , Sacram en to, C alifor n ia, U SA, 11, 2003: 406 410.
[ 3 ] 黎松, 平西建, 丁益洪. 开放源代 码的计算 机视觉类 库 O penCV 的 应用 [ J] . 计算机应用与软件, 2005, 22 ( 8) : 134 136.
[ 4 ] 吕学刚, 于明, 刘翠响. 数字图像处理与计 算机视觉编 程的有力 工 具 IPL和 O penCV [ J] . 现代计算机, 2002, 147: 69 71.
[ 5 ] Intel?RO pen Sou rce Com puter V is ion Lib rar R eferenceM anu als. 2003.

(上接第 247页 )

图 1 边缘检测实例
4. 2 实例 2
本例展示了在任意多边形 中实现提取骨架 /中轴线的方法。 提取骨架的方 法主要 有内 切圆法、轮 廓线 法线相 交法 及 de lau nay 三角形法。利用 O penCV 提供 的 cvF indCountours函 数寻 找 轮 廓, cvA pproxPo ly 逼 近 多 边 形 曲 线, 同 时 使 用 了 大 量 的 O penCV 数据结构进行数据表示。该例 用 O penCV 来 实现, 简单 及执行速度快。原始图像及处 理结果如图 2所示 。

图 4 转变对最短距离的影响
3结 论
以上是对 G IS领域的最短 路径计 算所作 的三 方面的 优化, 可以看到它在虚拟地图的模拟计算中取得了相当 好的效果。
在实际使用中, G IS 的地 图可以 以统 一的 格式 分布 在不 同 地区的网上。到不同的地 区, 就到指定 的网站 去搜索 地图信 息 并进行计算。
最短路径的计算还有从起点出发要经过几个 送货点如何走 最有效, 又如设计旅行的最短路线。此外, 最短路径的计算除 了 平面以外还有在三维空间中的计算。如消防员如何从底楼最 快 地到达大楼中的着火地点。这些问题都是值得探讨的课题 。

图 2 骨架提取实例
5结 论
O penCV 充分利用 C /C+ + 运行效 率高的 特点, 开发了 大量 的几乎遍及所有的图像及计算 机视觉处理函数。由于其代码完 全开放, 用户 不但可以 对源代码进 行修改, 加入新类 , 而且 可以 通过查看函数内的源 代码来理解图像处理中很多经典算法的原 理及实现过程, 这将对从 事图像 的工作 者提供 有益的帮 助。而 且 OpenCV 操作方便, 不但可以作为应 用程序的后 台处理程序, 而且可以作为控制台程序进行 操作。它 在图像处理及计算机视 觉的各个领域中具有 广阔的应用前景。

参考文献
[ 1 ] 夏宽理. 算法基础. 高等教育出版社, 2003. [ 2 ] Car A, Taylor G, Brunsdon C. A n analysis of the perform ance of a h ier
arch ical w ayf ind ing com putational model u sing syn thet ic graph s C om puters. E nvironm ent and U rban System s, 2001, 25: 69 88. [ 3 ] T arant ilis C D, et a.l Com b inat ion of geograph ical in form ation system and eff icient rou t ing algorithm s for real life d istribu tion operations. Eu ropean Journal of O perat ion al R esearch, 2004, 152: 437 453. [ 4 ] ChrisU pchurch, et a.l U s ingG IS to generate mu tua lly exclus ive service areas l ink ing travel on and off a netw ork. Jou rnal of T ran sport G eogra phy, 2004, 12: 23 33. [ 5 ] Zh ongR en Peng, et a.l D esign and developm en t of interact ive trip p lan n ing for w eb based trans it in form ation system s. T ransportation R esearch Part C, 2000, 8: 409 425.



热文推荐
猜你喜欢
友情链接: 简历 面试求职范文 职业规划 自我管理 社交礼仪 76242百科