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

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和测绘工程理论教学和研究墨谗。

 


相关文章:
一种路径规划算法的改进与设计
全局路径规划的方法主要有:栅格法[2]、构形空间法[3-7]、可视图法[1,8]...每一个独立的功能模块需要单独的测 试的设计,主要依据为需求分析中的功能需求,...
GIS空间分析复习提纲及答案
6、最佳路径分析:也称最优路径分析,以最短路径分析...转换为连续 的数据曲面,它包括内插和外推两种算法...3、空间分析的内容及其在 GIS 中的地位和作用? 答...
GIS空间分析原理与方法个人总结复习资料
ⅰ.与传统分析大差异:①空间数据间并非独立,...算法发现空间数据库中空间目标间的关联程度.GIS 数据...指定网络的两个结点之间找一条阻碍强度最小的路径。...
GIS空间分析作业
GIS空间分析作业_电力/水利_工程科技_专业资料。中国...空间分析方法——外在 趋势克吕格来结合这两种类型...3.在考虑高程的地质空间分析算法中,局部均值的简单...
GIS空间分析原理与方法
GIS空间分析原理与方法_天文/地理_自然科学_专业资料...解析变换法、数值变换法、数值-解析变换法 4.空间...网络分析 网络分析功能:路径分析、连通分析、资源分配...
GIS空间分析复习
GIS空间分析复习GIS空间分析复习隐藏>> GIS 空间分析...获取方法:(1) 手工 网格法;(2) 扫描数字化法;(...30、网络分析的功能:路径分析、连通分析、资源分配、...
改进的Dijkstra算法
改进的Dijkstra算法_数学_自然科学_专业资料。湖北...适应网络拓扑,成为最短路 径规划中的一个经典算法。...用于 GIS 路径分析,希望能够同时提高时间与空间效率...
最优路径规划算法设计报告
最优路径规划算法设计一、问题概述 兵力机动模型的功能是支持实施机动的实体按照指定路线, 由作战空间的一 点向另外一点的位置移动,并带入实体在移动过程中发生变化...
开题报告 路径规划
在已有的路径规划方案中,仍有一些地方需要 改进,...2.4 路径规划总体设计 课题采用重遗传算法实现路径...所以,种群就表示为机器人在工作空间的多 条路径,...
GIS概论第2和1次作业
A、边 B、弧 C、路径 D、网络 正确答案:C 题...在 GIS 的开发设计中,将逻辑模型转化为物理模型的这个...A、空间矢量分析法 B、空间栅格分析法 C、拟合曲面...
更多相关标签:
改进型clock置换算法 | apriori算法改进 | 改进遗传算法 | 改进4.0算法 | 遗传算法的改进 | 改进算法 | kmeans聚类算法改进 | 改进粒子群算法 |