基于地理信息系统的最短路径搜索算法研究

基于地理信息系统的最短路径搜索算法研究

本文笔者对基于地理信息系统的最短路径搜索算法进行了简单的探析，对地理信息系统做了简要的介绍并分析了其当前的情况，然后对基于地理信息系统的最短路径搜索算法进行了探讨，并对最优的最短路径搜索算法进行了分析，最后做出了总结。

一、地理信息系统的简要介绍及现状分析

地理信息系统是一种以空间数据为基础，并在计算机软硬件的支持下进行空间数据的分析综合，并以系统工程和信息科学理论为 基础对规划管理和研究等提供信息的技术系统。地理信息系统在储存和处理数据的时候是通过对地理位置进行编码使得该地理位置的地物属性信息成为主要的数据收集检索部分。地理信息系统具有空间性和动态性，具有较强的信息处理功能。而且还支持进行空间地理数据管理，能够作用于空间数据，有利于信息利用率的提高。地理信息系统的另一个特征是拥有计算机系统的支持，能够高效准确的完成对复杂地理信息数据的处理。在进行数据处理的时候拥有数据输入输出、数据库管理系统和分析工具等功能。随着计算机科学技术的发展，计算机图形学得到了高速的发展，使得地理信息系统也得到了飞速的发展。同时，计算机行业的发展也使得计算机软硬件的成本降低，但是功能越来越强。而且，计算机数据库管理系统的普及也使得计算机的制图成本和地理信息系统的成本也开始下降。地理信息系统是一个综合的系统，它可以通过其软件控制关系数据库管理系统（RDMBS）以及地理属性的数据，并且对数字图形文件进行解析分析。当前的地理信息系统行业主要有数字化、数据转换和专业应用方面的不同服务。前国防系统的一些销售商也瞄准了地理信息系统技术，并开始向这一市场转变同样也推动了地理信息系统技术的发展与普及。而我国的地理信息系统与国外的差距还是比较大的。由于起步比较晚，所以我们必须要找出我们与国外先进水平之间的差距，从而向着明确的目标前进。1978年到1985年，我国地理信息系统开始组建队伍、组织个别实验研究并在理论探索和区域性实验研究的基础上制定国家地理信息系统规范。而从1986年开始，我国的地理信息系统研究逐步的面向全国，并且取得了重要的进展，形成了很多专业的地理信息系统软件和产业化公司产业。

二、基于地理信息系统的最短路径搜索算法探讨

1、最短路径介绍

最短路径算法是计算机科学与地理信息科学等领域的研究热点，经典的图论与不断发展完善的计算机数据结构算法的有效结合使得新的最短路径算法不断涌现，针对不同的网络特征，应用需求具体的软硬件环境，各种最短路径算法在空间复杂度，时间复杂度易实现性及应方范围等方面各具特色。网络图的预处理技术是最短路径计算问题中的重要的技术，其在对城市道路网进行最短路径分析时具有重要的作用。网络图的预处理工作主要包括对原始的道路图进行线元素检查和处理，然后建立拓扑关系，最后生成拓扑文件。在生成最短路径分析系统的时候要解决好一些关键的问题，比如说能够怎样用矢量地图表达城市道路网，怎样高效的提取道路的网络拓扑结构等。

2、基于地理信息系统的交通网络中最短路径算法研究

基于地理信息系统的最短路径算法在很多领域都有涉及，而不同的环境下有着不同的算法。对最短路径的算法分类可以分为静态最短路径问题和时变最短路径问题，确定型和随机型最短路径算法，串行和并行最短路径算法，小规模网络和大规模网络最短路径算法等。网络中的权值固定时，我们将网络称之为静态网络。传统的最短路径算法，是从源结点到所有其它结点的最优路径，或者从所有结点之间选择最优的路径，该算法能够处理固定网络拓扑和固定的权值。而随着计算机网络和技术的不断发展，同时又有智能交通系统（TIS）的出现，直接产生了时变最短路径算法问题。时变网络，又称为依赖网络，其弧的权

值是时间的函数，到达弧尾结点的时刻不同相应的弧的旅行时间不同。时变网络最短路径计算法首次由著名的科学家Cooke和Halsey提出，Dreyfus在Cooke和Halsey的基础上优化了时变网络最短路径计算方法。后来，研究者认识到时变网络与静态网络差异性，对病态实例的情况不加限制，在没有任何限制性条件下，给出完整的理论研究和算法，能够求解FFIO网络和非FIOF网络的最优路径问题。

3、基于地理信息系统的最短路径算法选择

比较好的最短路径算法有经典的Dijkstra算法、Ford-Folkersno算法等。其中Dijkstra算法比较简单、在最优路径选择时比较稳定，所以在日常的运用比较广泛。该方法主要是由近及远寻找起点到其它所有结点得最优路径，直至到达目标结点。但是，该方法的搜索效率不高，花费也比较大，并且也很难满足人们在实际应用中的需要。Ford-Folkersno算法通过检查各条弧的结点，然后通过结点来求出最短的路径。Ford-Folkersno算法相对Dijkstra算法而言，能够有效地解决含负边长的网络图。还有一些其他的比较好的算法也可以求出最短的路径，但是同样也要根据不同的情况来选择不同的算法以达到最优的最短路径计算方法。

三、总结

最短路径问题是交通网络分析系统研究的一个基本的问题，现在我国在其理论和应用上有着较为广泛的研究。地理信息系统（GIS）的运行基础是计算机图像处理技术、数据库技术和数学研究方法等。其在很多的领域都有着广泛的用途，其中基于地理信息系统的交通网络，包含着网络的拓扑特征和一些相关的数据。在计算交通网络中的最短路径问题时，要充分的考虑到交通网络本身的特点。对最短路径算法的改进主要目的在于减少算法搜索的复杂度，提高系统运行效率，使之更符合工程需求。当前，时变最短路径算法并未在智能运输系统、地理信息系统等实际工程中广泛的应用，其运用主要依赖于成熟的系统工程理论和相关的数学知识以及一些相关的计算机系统技术的完善和结合。通过对国外先进技术的引进学习，我们可以不断的提高自己的技术水平，使得我国在基于地理信息系统的最短路径搜索算法研究中能够追赶上国际上的脚步。另外，在不同的领域我们要采用不同的算法进行最短路径的计算。要结合具体实际情况，建立完善的网络模型，探讨最短路径算法，对算法在大规模量化地图中的实施进行可行性研究，进而将算法在矢量化数字地图中实现将是对本课题下一步研究工作的展望。