当前位置:首页 >> 机械/仪表 >>

GIS空间分析中两种改进的路径规划算法


?】2?

地矿测绘

2008。24(3):12一14
Mineral Resources

CN 53一1124/rID

IssN 1007—9394

of Surveying and Mapping Geology and

GIS空间分析中两种改进的路径规划算法’
候建国1”,王腾军’
(1.长安大学地测学院,陕西西安710054;2.黑龙江工程学院测绘工程系,黑龙江哈尔滨150001) 摘簧:通过对经典Dijkstra算法和启发式搜索的分枝算法各自的不足之处进行分析,并分别对它们进行了改进。利用Vc编程 进行实验。实验表明:改进的Dijkstra算法可以减少大缀的无关节点的计算,使其时间复杂性得到降低,同时运算空间开销也减少;改 遴的分较算法则霹以提裹搜索列最优路经鳇成功率。 关键词:路径规划;GIS;空闻分析;Dijkstra算法;努枝算法 巾图分类号:P
208;P283.7

文献标识码:A

文意编号:1007—9394(2008)03—0012—03

Two Kinds of

Improved Pam
HOU

Planning Algorithms in GIS Spatial Analysis

(1.School ofGeological Sum.ying Engineering,Chang'an neering,Heilon面inag
College

Jiang。gu01一。WANG Teng-junl University,Xi'an Shanxi 750054,Ch/na;2。挠譬ofSu,婶ing and Mapping

Engl-

of Technology,Harbin Heilon毋iang 150001,China)

Abstract:Based

on

the analysis of the tradition

Dijkstra

algorithm's and Branch.and—bound search algorithm。all im-

proved algorithm is given.The experiment in the VC programming shows that the improved
crease

Dijkstra

algorithm

Can
can

de- find

the computing of uneorrelated nodes and enhances the calculation efficiency and the improved algorithm

the more optimum path。 Key words:optimum path planning;Geographic Information

System(GIS);spatial analysis;Dijkstra

algorithm;

branching

algorithm

O引言
空闼分板是GIS的一项卡分重要戆任务和最具有特色戆功 能,是基于地理目标的位置和形态特征的空间数据分析,其目的 是提取和发现隐禽的空间信息或规律,是密间数据挖掘和知识 发现的基本方法之一。空阕分耩不是麓攀地通过“竣索”、“查 询”或“统计”从地理数据库巾提取时空倍怠,而是利稍各种空 间分析模型及空间操作对地理数据库中的空间数据进行深加 工,送纛产生凝的妇识。空闻分耩是空翘数据的空间特性与非 空间特性的联合分析,亦郎拓扑与属性数据的联合分斩。路径 分析题GIS的基本功能,其核心是最优路径的求解。所谓最优 路经麓指惩络强令结点之阉阻抗最零的路径,“阻抗最小”有多 种理解,如基于革因素考虑的时间最短、赞厢最低、风荣最好、路 况最健、收费站最少和经过乡村最多等。和基于多因索综合考 瘩的城景最好且经避乡村最多,或时阕较娥翻路况较德且收费 站最少等。最优路径的求解算法有几十种,知:基于贪心策略的 最近点接近法、最优插入法,慕于启发式搜索策略的分枝算法,

基于局部搜索策略的对边交换调整法以及广泛采用的Dijkstra 算法等。举文主要讨论Dijkstra和启发式搜索的分枝算法。

1.1

Dijkstra算法的问题和改进

mjks蛔算法的基本步骤
最短路径是指在髑络D(V,A)中,找出从越点t出发测终

点E的累计行程最短路径。Dijkstra算法是解裁短路径问题的 一种算法,它不仅可以找到最短的(E,匕)路径,而且可以给出 从霆点t爨发到图中掰有节点的簸短路径,冀法过程如下: 第一步:初始亿,起点s设置为《=O,P。为空;其它所肴点 i,di=∞,记Pi=?(朱知);标记点k=j(5为起点的编号)。 第二步:距离计算,诗算扶所标记的点k戮与其直接粳连的 所有其它米作标记的点f的距离气,并令《=rain[d,,文+氏】。 第三步:选取下一点,从上述结点集中,选取d;最小所对应 豹点为最短路径孛的下一连接点歹,劳作标记。 第因步:找到歹的翦一点,驮已标记的所裔点中找到直接连 接点,的前一点i’,并令J=i’作为前一点。

?收稿日期:2007—04—05

 

第24卷第3期

侯建国,王腾军:GIS空间分析中两种改进的路径规划算法

?13?

第五步:标记点.『。如果所有的点均已标记,则最短路径寻 找结束;否则,记k=.『,转第二步继续。
1.2

I啪tra算法应用举例
利用Dijkstra算法求图1中结点A到其它各结点的最优路

J】If—D—P,

表1可以看出.A到P的最短路径为A—C…F
119次。 表l

径。根据算法的实现步骤,其计算过程可归纳为表l所示。从

且A到P的距离d(A,P)=18.3。在求A到P最短路径过程 中,A到其余各点的最短路径也相应求出。若以计算一次d。= rain[dj,d。+k]为计算单位,则利用Dijkstra算法计算A到P的 最短路径时所需要的计算次数为T(P)=15+14+……+2=
Fig.1

图1最优路径计算网络图
Optimum path computing network chart

采用Dijkstra算法求解A到其它各结点最优路径的过程
to

17出l
旁号
l A

111e process of calculating optimum path from A C 3.4 3.4/A
∞ D ∞

other nodes by means of I J
∞ ∞ ∞ ∞

Dijkstra


algorithm N
OD




a10

F ∞


∞ ∞




∞ ∞


∞ ∞


∞ ∞



一4.2

∞ ∞

2 3


—4.2



9.0 8.3 8.3 8.3/口

6.9 6.9







。 ∞

—4.2朋一 一 一 一 一 一


8.6 8.6 8.5



∞ ∞





∞ ∞

∞ ∞

∞ ∞

OD

OO

一 一 一 一 一 一 一 一 一 一 一 一

一 一
一 一

6.9/C∞

11.9 11.2 11.2 11.2 11.2

10.9 10.9 10.9 10.9





∞ ∞ ∞

5 6


一 一 一 一 一 一 一 一 一 一 一



10.3 lO.3 lO.3/D

aid

aD

∞ ∞? ∞

∞ ∞

∞ ∞

8.6/B一

11.5 11.5 11.5 11.5





一 一 一 一 一 一 一 一 一

一 一 一 一 一 一 一

13.5

13.7 13.7 13.7 13.7 13.7

OD

∞ ∞

∞ ∞

8 9

一 一 一 一 一 一 一 一



lO.9/,13.5 13.5 13.5 13.5

13.1 13.1 13.1

∞ ∞



11.2/E— 一 一 一 一 一


∞ ∞

∞ ∞

10一 lI一 12一
13

11.5/D一

一 一 一 一




一 一



一 一

13.1/J∞

16.1 16.1 16.1
16.1



13.5/日13.7



18.O 15.9
15.9/L

at,





13.7/.『jr一 一 一 一 一



14一 15一
1.3







一 一




18.7





16.1/肘18.3

DUkstra算法的不足 在地理信息系统中,网络模型的规模常常较大,结点数成千

预见d。是无穷大时,不对它进行计算,避免大量无效的计算,提 高搜索效率。 利用改进的Dijkstra算法求图l中结点A到其它各结点的 最优路径,同Dijkstra算法基本一致,只是表l中所有无穷大标 记的部分在改进Dijkstra算法中被省去了,利用改进的Dijkstra 算法计算A到P最短路径时所需计算次数为T(P)=47次。由 此可见,改进的Dijkstra算法确实减少了计算量。 1.5实验对比 为了更好的说明改进Dijkstra算法的有效性,利用VC语言 编制最短路径搜索程序,并对5幅网络地图进行计算,计算结 果,见表2。最短路径搜索程序实现关键代码如下: void:ProcessPendingAccept() I CClientSocket’p,%cket=new CClientSocket();

上万,并且对网络模型的查询要求实时性。虽然。Dijkstra算法 在理论上可行,但是该算法在求解从起点到某一终点的最短路 径过程中,时间复杂性为0(n2)。在求解网络系统中多点对乃

至所有结点之间的最短路径,可重复Dijkstra算法多次或厅次,
时间复杂性为O(厅3)。因此,对于海量数据的地理信息,传统的 Dijkstra算法计算量较大,时间花费较多,效率非常低。 1.4改进Dijkstra算法的基本思想和实现 表1中的数值大多数是无穷大,都是无用的运算,如果结点 数很多,将及其浪费运算时间。由于d。=min[d。,五+k],i结 点是否在上次已经被计算出最短路径未知,当前结点i是否与 结点I|}相连也未知,也就是k未知,这时以为已知,故本次计算 的dj到底是不是无穷大,取决于上一步di数值和k的数值。从 表达式可以看出,只要这两个数值不同时为无穷大,本次计算的 正就不会趋于无穷大。所以在前文Dijkstra算法实现第二步 时,先判断一下,只要原来的d。和k的数值中至少有一个不是无 穷大,才进行下面的计算di=rain[d;,d。+k],这样就保证了当

if(m_pListenSocket.Accept(‘pSocket)) {
CMessg msg;

 

?14?

地矿测绘 2.3分枝算法分析

2008串9月

msg.m_strText=。。”:

m_sShowString+=””:
POSITION pos;

分枝算法是利用对问题的了解和对问题求解过程的了解, 寻零某种鸯瘸子闼题求孵酶襄发镑怠,鲠秀剩髑这些毫发僖息

for(pos=nl—connectionList.GetHeadPosition();pos!=


去搜索最优路径。它不用遍历整个地图,而是每一步搜索都根
据启发函数朝着某个方向搜索,当地图很大很簸杂时,它的计算 复杂性大大优于Dijkstra算法,是一种搜索速度非常快、效率非 常高莳算法。僵是它也稽映点,启发性信怠是人为魏入的.凌穰 大的主j【!Il性,直接取决甲操作者的经验,对于不问的情形要用不 同的启发傣息和启发函数,且它们的选取难度比较大,很大程度 主我不到簸傀路径。下嚣逶过其薅例子说碉。 利用分枝算法求圈1中从A点出发到Ⅳ点的最优路径。 将评价函数以n)=g(玮)+h(扎)中的g(n)取为肖前结点到起始 结点A鹩簸短距离,瑟矗(拜)取为当戆结点到毯豁结点Ⅳ豹数氏 距离,在应糟分枝算法时除采用上蕊Dijkstra算法所用避的拓 扑结构外,还应该冉给定所有结点的坐标Node(髫,Y),如备点坐 标为A(0,13),0(3,16),C(3,11)。……。根据分枝算法的具体

NULL;)


CClientSocket‘t=(CClientSocket‘)In—conneetionList。Get-

Next(pos); t一>SendMessage(&msg); } pSocket一>Init(this);


connectionList.AddTail(pSoeket);


else
delete pSocket;



实现步骤,掰求得f9,A弱N的最短路径是矗一卜卜扣玉~帮,
表2改进的Dijkstra算法和缎典Dijkstra算法计算次数比较
Tab.2
Computing number comparison
stra

其距离是d(A,Ⅳ)=16.6。查看表l可知,用Dijkstra算法搜索 的最优路径是A—B一肛~舟一£一JIv,其路径长度15.9,很明显 分较算法没毒我到最傥路径,瑟显遴过毙较嚣条鼹径霹以发瑗, 当采用分枝算法搜索路径时,从第二个结点就把最优路径舍 弃了。 2。4分棱篝法改进嚣懋及实现 为了克服最优路径町能被轻易舍弃的缺赢,本文提蹬采用 多次搜索的方法,用增火计算量为代价来换取尽量多的最优路 径备选结黎。具体的方法如下:将经典的分枝算法搜索出原始 最优路径审豹绩熹依次送行封堵爨,再按慧经典分棱算法搜索 在每一次对堵情况下的最优路径。最后将这些新的最优路径与

between improved Dijk—

algorithm and classical

Dijkstra algorithm

从表2可以看出,两种算法计算量有很大区别,改进的Di— jkstra箕法较之经典的Dijkstra算法在计算蹩方瑟有缳犬蠖度的 减少,褥且这种减少程度在结点数目增加时会变得越来越孵显, 由于GIS地图都较大,所以使用改进Dijkstra算法的改进效果将 菲常显著。

原始最优路径进行对比以便确定最后的最优路径。现举例说明 改进分技算法约其捧疲鬻。剩用改进懿分技算法求图l巾轶A 点出发到Ⅳ点的最优路径。

1)按分枝算法寻找路径得到:A—c一肛肛£广.|I\,,路径长
发16.6。

2分棱算法的问题和改进
2.1分枝算法的基本思想 努较算法在人工蟹襞孛蹙一;黪典型黪襄发式蓑索筻法。 通过选择合适的估价函数,指鼯搜索朝着最有希望的方向前进, 以求得最优解。分枝算法中,关键是求估价函数:,(n)=g(n) +矗《毪)。其孛,g(,1)是致起点E到当前缕点拜已付如酶代份, 毳(n)怒获当前结基到目标结点玩的代价佑计函数,必须保证矗 (n)《^‘(n),其中。h’(n)愚从当前点到目标点的嶷际最小 代价。 2.2努棱算法瓣步骤 分枝算法的步骤如下: 1)给定起始结点标记,对它的没有标记过的子结点进行 扩曩。 2)对每一个予结点计算评价函数值,按评价值的穴小进行 排列,找出评价值最小的结点,并给它作标记,如果当前结点就 是基据结点,剐停止搜索。 3)否则,对最薪被标记的络点进行筹麓步处瑾,辨记录最 短路径。

2)封闭就路径牵终点e磊得到的最往路径秀:A一跏弘一
肛一L--N,路径长度15,9。

3)封闭此路径中结点E后得到的最优路径为:A一卜,o
卜玉一群,路径长度|7。l。

4)封闭此路径中络点片后褥到的最优路径为:A一卜肛
卜L一,v,路径长度17.2。

5)鸷阕戴路径中绩点£磊德劐的最优路撩隽:A—c_肛
謦一I卜Ⅳ,路径长度18.7。
对前颟求得的5种路径长度进行对比,得到最优路径为

A一卜E一肛卜Ⅳ,冀长度为15.9,从两将此路径定位改进分
技算法求褥鸵最傀路磁。查看表l霹知,既路撩歪是采瘫Dijk- stra算法时求得的最优路径。 2.5实验对比 鸯了遴一步验证改进分技冀港的有效性,穰餍Vc编涮爱 短路径搜索程序。以78个结点的地图作为对象得到实验络采 如下:采用经典分枝算法对77个结点分别进行路径规划,有45 个找到r皴优路径。iil;采用改进的分枝算法对77个结点进行 路径规划时,有6s个找翻7最优骆径,有8个维点虽未我翻最 优路径但得到了比经浆分枝算法煦短的路径,(下转第17页)

 

第24卷第3期

孙慧敏,姚遵镁:线形坐标与工程坐标的转换履其应用

?17?

线翔一条壹线缀成(鲡黧l掰示),耀痘元素鹃参数,冕表l、 袭2。

表4孛的第一、二列秀4个点静工程坐标,由该诤舞方法获 得的距该点最近的元素起点坐标列于第三、四列,该起点的切线 方向至待计算点的夹角列于第赢列,计算出的里程和偏距列于 第六、电穰。 表4
Tab,4

由工程坐标反算的线路坐标
calculated from engineer-

Alignment coordinate inversely ing coordinate

豳2线路图
Fig。2

Route diagram

表i题点坐标和方位角
Tab.1 Coordinates and azimuth of the starting

poi.t

4结束语
本文所述方法采矮鐾覆、镯眍坐标系统,缀据设计懿参数与 工程坐标系统进行稠互转换,不仅可以较好地解决RTK在线路 定测过程中的加桩问题,而且在高速公路整治、隧道工稷等方面 同样透用,易于编稷,提高了工作效率,降低了劳动强度。

【参考文献】
口 娥连璧,朱照宏.RTK技术猩道路定测中腹用的研究【J】.中国公 爨攀援,2000,13《1):14一17. 口 豢世伟,旅,j、枝.快速确定交通路线加桩的简易方法探讨[J】.测

计算出的各段元素终点的坐标和切线方位,如裘3所示。


轰3各段元素终点酌垒耩和切线方德
骶h 3
Coordinates and tangential each segraent azimuth of end point
on

,』1j
1J 1j

绘通报,200 1.(1):14一15. 攀仕东,燕春歌,窦守连.基乎RTK技术下黛点法放样路线中线加 梭Cj】。孛羚公爨,2006,26(6):156—158。 张正禄,等.工稷测量学[M].武汉:武汉犬学出版杜,2005. 姚连罐,周小平.线路与桥隧GPS测量[M】.上海:上海科学技术 文簸蹬舨拄,1999.

H瞪



攀震出,李少嚣.弱用复纯睾需生公式辫冀线路热柱赢的坐标鞠 熙程[J】.石家威铁道学院学报,2000,(4):79—82.

缘寮麓赍:耱慧敏(1984一),女,玉末辫城人,瑗毒研究生, 主要研究方向:精密工程测量和变形监测。

(点耧第14页) 只有一个结点和经典分枝算法结果一致。这充分说明,改进的 分技算法较经典盼分棱箕法在搜索最优鼹径的成功率方瑟具鸯 鞠驻的优势。
社.2003.

[参考文赫】
[1]受窥新,史文中.地理信息系统原理与算法[M].北京:科学出版

【2】秘仁塞.空瘸分辑【麓】。武汉:获汉嚣绘转获大学蹬菠挂,1996. [3】董家耀.空间信息系统原理[M 3.北京:科学出版社,2001. [4]徐立华.求解最短路径问题的一种计算机算法[J].系统工程,

3结论
本文对经典Dijkstra算法和分枝算法进行了改进,改进瑶 的算法具有以下特点:改进的Dijkstra算法能在很大程度上节 誊诤箕量,提蒜路径规戴速度;改进酶分校篓法虽程一定程度上 增太了计算堂(但远远小予Dijkstra算法的计算量),却大大增 大了搜索到最优路径的成功率。

1993。33(4):62—67。

【5】爨溶辉,自玲,嵩健美。最短魏径算法豹改遴及其实凌【jj.辩竣军
测绘学院学报,1998,15(2):23. [6]Lee J.Calculation of the dlortest pal}I sbyoptimai decomposition[J】. 珑EE Tran§Sys*Man Cybem,1982。≤3):410,

作者简介:侯建国(1968一),男,黑龙江呼兰人。副教授,博 士研兜发,现主要从事GIS和测绘工程理论教学和研究墨谗。

 


相关文章:
GIS空间分析与建模期末复习
GIS空间分析与建模期末复习_理学_高等教育_教育专区...正解变换法、反解变换法 地理空间坐标系的转换:...最优路径分析、网络流分析、通达性分析等 5) 统计...
GIS空间分析原理与方法个人总结复习资料
⑶地理空间关联分析:地理空间关联分析利用空间关联规则提取算法发现空间数据库中空间目标间的关联程度.GIS 数据库是典型的空间数据库, 从 GIS 数据库中挖掘空间关联...
GIS空间分析的功能和广泛应用
GIS 中可以实现空间分析的基本功能,包括空间查询与量算,叠加分析、缓冲区分析、网络分析等,并 描述了相关的算法,以及其中的计算公式。 1、叠加分析 叠加分析至少要...
GIS和空间分析的基本方法
GIS 可以处理矢量和栅格两种空间数据。在处理矢量数据,GIS 用地理坐标点来构建...INFO 文件或 ArcInfo 属性表(.PAT or .AAT)转换成 ASCII 文件,方 法如下。...
GIS空间分析 考试
GIS空间分析考试资料 11页 免费 空间分析复习资料 16...为一所新学校寻最佳位臵时, 有两种分析的途径。 ...第二、将球 面坐标转换为平面坐标的过程(投影算法)...
嵌入式GIS中大区域路径规划算法研究
嵌入式GIS中大区域路径规划算法研究_计算机软件及应用_IT/计算机_专业资料。嵌入式GIS中大区域路径规划算法研究1 嵌入式 GIS 中大区域路径规划算法研究随着卫星空间定位...
中国科学院大学GIS空间分析考试资料
6、地理空间分类与聚类算法的差别是什么? (1)地理...GIS空间分析基础 10、地理空间一般被被定义为哪两种...功能:(1)路径分析(2)连通分析(3)资源分配(4)流...
基于GIS的路径规划算法研究与实现_图文
基于GIS的路径规划算法研究与实现_教育学/心理学_人文社科_专业资料。龙源期刊网...GIS空间分析中两种改进的... 32人阅读 4页 1下载券 GIS中最短路径的算法研...
GIS空间分析作业
GIS空间分析作业_电力/水利_工程科技_专业资料。中国科学院GIS空间分析作业将...3.在考虑高程的地质空间分析算法中,局部均值的简单克吕格和外在趋势克吕格产生...
GIS空间分析名词解释
GIS空间分析名词解释_工学_高等教育_教育专区。GIS空间分析名词解释第...第八讲 克里格方法体系 克里格法:又称空间局部估计或空间局部插值法,克里格法是...
更多相关标签: