【作者】 胡伟凡；

【导师】 杨恢先；

【作者基本信息】 湘潭大学 ， 控制理论与控制工程， 2009， 硕士

【摘要】 GIS技术在当前计算机应用领域中很热门,本文研究了GIS技术在实际工程中的应用及实现问题。地理信息系统的研究产生于上世纪六十年代,随着计算机技术的发展,其研究也越来越深入,其应用越来越广泛。从军事上的战场电子指挥到日常生活中的个人导航系统,无不应用了GIS技术。如何快速又节省系统资源的实现大型网络图中的最短路径搜索是GIS技术在实际应用非常有意义的一个课题,很多具有现实意义的功能需求,比如:如何最快?如何路程最短?如何最少经费?都和GIS技术息息相关,因而对GIS系统中最短路径搜索算法的研究具有重要的研究价值和实际意义。详细介绍了一种最短路径搜索算法的设计及其优化。经典的Dijkstra算法是针对网状图中求取任意两个结点间的最短路径的一种贪心算法,具有原理简单,易于实现,技术成熟,可扩展性强等优点。但是面对例如中大型城市交通网络这种大型的网络计算,经典的算法也暴露出多次迭代后误差增大,效率低下,资源耗费大等缺点,无论是计算精度还是算法响应时间都无法满足实际应用的要求。因此如何保证精度和速度求解大规模复杂网络的最短路径问题成为了实现GIS应用系统的瓶颈问题。针对这个问题,从算法精度和算法优化两方面对经典的Dijkstra算法进行了优化设计。算法精度方面,由于经纬度求算的实际距离在多次叠加后误差增大,提出采用参数修正的高斯投影算法,不仅大大减少了迭代计算误差也提高了计算速度。算法优化方面,采用效率更高,更加智能的A*算法控制搜索过程;数据结构方面采用邻接矩阵表示网络图的拓扑结构,然后用动态十字链表结构存储邻接矩阵元素,把计算所需的数据分块提炼精简到内存中,通过多次到内存中交换数据达到减少内存使用的目的。实践结果表明,优化后的算法在计算时间上和计算精度上都比经典Dijkstra算法有明显改善。较为详细地介绍了一个GIS系统的设计,内容包括地图信息的处理和优化,针对城市交通网络的数据结构优化等等。重点介绍了系统显示和动态地图的相关问题和原理等。最后介绍了系统的人机交互和紧急中心的相关内容。更多还原

【Abstract】 GIS technology is very popular in the field of current computer applications. This paper researches the application and implementation of GIS technology in actual engineering. The study of GIS is started in the 60’s of last century. With the development of computer technology, its research becomes further and the application is widespread from electronic command on the military battlefield to personal navigation system of daily life. How to realize shortest path search of large scale network fleetly and saving system resources is a very significant subject of actual application of GIS. Many functional requirements that has practical significance is closely bound up to this technology such as how to the fastest, the shortest distance and the least cost and so on. So the research of shortest path search algorithm has an important value and practical significance to GIS.In this paper, the design of one kind of shortest path search algorithm and its optimization were introduced. Classic Dijkstra algorithm is a greedy algorithm to get the shortest path between two nodes in network graph. It has the advantage of simple principle, easy implementation, technical maturity and strong extensiblity. But when using in large scale network computing such as large city transport network, the disadvantage of classic algorithm is appeared such as error increasing, inefficient and resource consuming. Not only calculation accuracy but also the algorithm response time can’t satisfy the requirements of practical applications. So how to guarantee the accuracy and speed to solve shortest path problem of large scale complex networks become bottleneck problem of realizing GIS application system. According to this problem optimize the design of classical Dijkstra algorithm from algorithm accuracy and algorithm optimization. In the aspects of algorithm accuracy, due to the error increase in calculating actual distance of latitude and longitude after multi-iterations, put forward parameters amendments Gaussian projection algorithm. Not only greatly reduces the iterative calculation error but also improve the computing speed. In the aspects of optimization algorithm, use efficient and intelligent A* algorithm to control search process. And in data structure using adjacency matrix to express the topology of network graph. Then use dynamic Cross-Chain to storage the elements of adjacency matrix and put the data use for calculating into compter memory one by one. Through repeat data exchanges in memory to achieve the purposes of reduce memory usage. Practice results show that the optimized algorithm has significantly improved than classic Dijkstra algorithm both in the calculation time and calculation accuracy. This paper describes the design of a GIS system. It includes map information processing and optimization, data structure optimize of city transport network and so on. Emphatically introduce the related issues and theory of system display and dynamic map. Finally introduce the contents of human-computer interaction system and emergency center.更多还原