资源描述：
《gis领域基于图论的最短路径算法研究与应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、GIS领域基于图论的最短路径算法研究与应用科技信息博士?专家论坛GIS领域基于国论明最短路径算法研究与应用湖南警察学院童宇杨卫平段丹青[摘要]本文分析了Di]kstra算法在GIS中解决实际最短路径问题时存在的不足,针对存在的问题,提出了一种将Dijkstra算法与A算法相结合,采用邻接表进行教据存储的优化算法通过实验证明,改进后的算法较原算法在执行效率上有了明显的提高.[关键词]GIS最短路径A算法1.引言公安行业管理所涉及的信息是多方面的,且绝大多数警务信息都与"地"息息相关.但是在传统MIS业务管理信息系统中,只对地址做出文字性的描述,不能对目标进行快速空间定位,显然
2、无法满足公安业务中对犯罪嫌疑人的快速追踪定位,对灾难事件的快速应急反应和紧急救助等领域的要求.GIS(GeographicInformationSystem)引入警务系统后,我们可以对地理位置进行编码,并根据目标在GIS上的定位迅速地找到实际位置,从而进行后继相关处理.要在最短的时间内到达目标地点,必须进行最短路径分析.最短路径搜索是GIS网络路径分析中的一项很重要的功能1.对GIS中的数据(女口道路,管网,水系等)进行最短路径的汁算,就必须首先将其按结点和边的关系抽象为图的结构,这在GIS中称为构建网络的拓扑关系.只有建立了拓扑关系,我们才能进行网络路径分析.于是最短路径
3、计算实现的关键在于网络拓扑结构的建立和高效能最短路径算法.2.国内外研究现状目前提出的最短路径方法有很多,主要有图论法,启发式搜索法,动态规划法和神经网络算法等.其中基于图论的最短路径的算法大约有17种.经专家测试,其中有3种效果比较好,它们分别是:TQQ,DKA以及DKD.其中TQQ算法的基础是图增长理论;后两种算法则是基于Dijkstra的算法.目前多数系统解决最短路径问题都采用了Dijkstrz算法为理论基础,只是不同系统对Dijkstra算法采厢r不同的实现方法.3,Dijkstra算法存在的不足Dijkstra算法主要用来解决单源多目标最短路径问题,这个算法的主要
4、思想如下:将顶点分成两个集合s和T,已求出最短路的点(被最终标记的结点)置于s中,其它点(被临时标记的结点)置于T中.开始时s中仅含起点v.,其它点全在T中,随着求最短路迭代工作的进行,S中的点逐渐增多,当终点v也被纳入s中时,迭代结束.为了便于计算和区分各顶点是否已进入集合s,给已求出到起点最短路的点v赋以标号.这个标号由两部分组成,记为(d(v.,VO,i)其中i为V到起点最短路上的前点,d(V,V)为从起点v.到vk的最短路长.Dijkstra算法是一种基于"局部最短之和必为总体最短"思想的贪心算法.如果直接应用到GIS中解决最短路径问题,会存在以下几点不足:该算法本
5、质是搜索源点到其他每个结点的最短路径,并按长度非递减的顺序列出从源点到各个目标点的最短路径.该算法在计算一条最短路径时,并不考虑目标点的位置或方向,既可能会向目标点相反方向进行搜索,其搜索过程可近似为以源点为圆心的一系列同心圆,这样就大大增加了算法的复杂度,降低了执行效率.该算法的核心步骤就是从临时标记结点中选择一个权值最小的弧段.这是一个循环比较的过程,因为临时标记结点(即集合T中的元素)是无序地存储,如果不采用任何技巧,要选择一个权值最小的弧段就必须多次遍历所有的临时标记结点,甚至包括那些路径为无穷大或方向完全相反的结点,在大数据量的情况下,这无疑是一个制约计算速度的瓶
6、颈.该算法是基于网络图的模型,是一种静态环境下最短路径的选择算法.但在实际应用中,可能因为交通流量,路段突发状况及天气各方面因素的影响,使得原本的最短路径成为耗时最长甚至不可达的路径.4.对Dijkstra算法的改进针对以上提出的关于Dijkstra算法几点问题,本文对该算法做如下改进.(1)Dijkstra算法和A算法相结合假设有某网络拓扑结构图如图1所示,假定s为源点,T为目标点,P,q为途中任意两个临时标记结点.若已知s—p和s—q的最短路径分别为8和12,且s—p的距离小于s—q的距离.按照原始算法,我们将选取P最为最终标记结点,并以此对它的邻接点进行遍历,以计算s
7、—T的最短路径.但实际上,P可能处在与终点相反的方向,或P与终点并无可直达路线,q才是正确的选择.为了在算法计算过程中避免此类错误造成的计算时间的大量浪费,假设I临时标记结点(P,q)到日标结点(T)存在一条直接连线(图中用虚线标记),这条直线的距离就是他们之间可能存在的最短距离.为了使算法的搜索方向更智能地趋向于目标结点方向,可以采用A算法这样启发式搜索算法的思想,通过选择更合适的估价函数,使Dijkstra算法的搜索区域更小,如选用临时标记结点到源点的最短路径与到目标结点的直线距离之和(即s—p加上p—T的距离
