个人导航软件系统中的一种路径搜索算法及其优化
|
摘要
GIS技术在当前计算机应用领域中很热门,本文研究了GIS技术在实际工程中的应用及实现问题。地理信息系统的研究产生于上世纪六十年代,随着计算机技术的发展,其研究也越来越深入,其应用越来越广泛。从军事上的战场电子指挥到日常生活中的个人导航系统,无不应用了GIS技术。如何快速又节省系统资源的实现大型网络图中的最短路径搜索是GIS技术在实际应用非常有意义的一个课题,很多具有现实意义的功能需求,比如:如何最快?如何路程最短?如何最少经费?都和GIS技术息息相关,因而对GIS系统中最短路径搜索算法的研究具有重要的研究价值和实际意义。
详细介绍了一种最短路径搜索算法的设计及其优化。经典的Dijkstra算法是针对网状图中求取任意两个结点间的最短路径的一种贪心算法,具有原理简单,易于实现,技术成熟,可扩展性强等优点。但是面对例如中大型城市交通网络这种大型的网络计算,经典的算法也暴露出多次迭代后误差增大,效率低下,资源耗费大等缺点,无论是计算精度还是算法响应时间都无法满足实际应用的要求。因此如何保证精度和速度求解大规模复杂网络的最短路径问题成为了实现GIS应用系统的瓶颈问题。针对这个问题,从算法精度和算法优化两方面对经典的Dijkstra算法进行了优化设计。算法精度方面,由于经纬度求算的实际距离在多次叠加后误差增大,提出采用参数修正的高斯投影算法,不仅大大减少了迭代计算误差也提高了计算速度。算法优化方面,采用效率更高,更加智能的A*算法控制搜索过程;数据结构方面采用邻接矩阵表示网络图的拓扑结构,然后用动态十字链表结构存储邻接矩阵元素,把计算所需的数据分块提炼精简到内存中,通过多次到内存中交换数据达到减少内存使用的目的。实践结果表明,优化后的算法在计算时间上和计算精度上都比经典Dijkstra算法有明显改善。
较为详细地介绍了一个GIS系统的设计,内容包括地图信息的处理和优化,针对城市交通网络的数据结构优化等等。重点介绍了系统显示和动态地图的相关问题和原理等。最后介绍了系统的人机交互和紧急中心的相关内容。
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.
详细介绍了一种最短路径搜索算法的设计及其优化。经典的Dijkstra算法是针对网状图中求取任意两个结点间的最短路径的一种贪心算法,具有原理简单,易于实现,技术成熟,可扩展性强等优点。但是面对例如中大型城市交通网络这种大型的网络计算,经典的算法也暴露出多次迭代后误差增大,效率低下,资源耗费大等缺点,无论是计算精度还是算法响应时间都无法满足实际应用的要求。因此如何保证精度和速度求解大规模复杂网络的最短路径问题成为了实现GIS应用系统的瓶颈问题。针对这个问题,从算法精度和算法优化两方面对经典的Dijkstra算法进行了优化设计。算法精度方面,由于经纬度求算的实际距离在多次叠加后误差增大,提出采用参数修正的高斯投影算法,不仅大大减少了迭代计算误差也提高了计算速度。算法优化方面,采用效率更高,更加智能的A*算法控制搜索过程;数据结构方面采用邻接矩阵表示网络图的拓扑结构,然后用动态十字链表结构存储邻接矩阵元素,把计算所需的数据分块提炼精简到内存中,通过多次到内存中交换数据达到减少内存使用的目的。实践结果表明,优化后的算法在计算时间上和计算精度上都比经典Dijkstra算法有明显改善。
较为详细地介绍了一个GIS系统的设计,内容包括地图信息的处理和优化,针对城市交通网络的数据结构优化等等。重点介绍了系统显示和动态地图的相关问题和原理等。最后介绍了系统的人机交互和紧急中心的相关内容。
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.
引文
[1]欧福军,刘萍,涂亚平,吴海兵.大规模网络最短路径算法的优化及实现[J].海南大学学报自然科学版, 2008, 25: 339-344
[2]张水舰,李永树,蔡国林,杨骏.基于GIS和AI的城市区域内最佳路径算法研究[J].测绘科学, 2008, 39(10): 1269-1272
[3]计会凤,徐爱功,隋达嵬. Dijkstra算法的设计与实现[J].辽宁工程技术大学学报, 2008, 14(8): 1-8
[4]王行风,贾凌. GIS支持下的城市交通网络最短路径研究[J].计算机与现代化, 2008, (3): 92121
[5] NOTO M, SATO H1A Method for the Shortest Path Search by Extended Dijkstra Algorithm [J] IEEE, 2009, (3): 31623201
[6]陆忠,钱翔东.基于最短路径查询的城市公交网络拓扑建模研究[J].遥感信息, 2002 (1): 112141
[7]徐业昌,李树祥.基于地理信息系统的最短路径搜索算法[J].中国图象图形学报, 1998 (1): 392431
[8]乐阳,龚健雅. Dijkstra最短路径算法的一种高效率实现[J].武汉测绘科技大学学报, 1999, 24(3): 20922121
[9]吴泉源,刘江宁.人工智能与专家系统[M].长沙国防科技大学出版社, 1995: 272-331
[10]陆锋,卢冬梅.交通网络限制搜索区域时间最短路径算法[J].中国图象图形学报, 2003, (10): 84928531
[11]李雯静,等. GIS数据分析中权重确定的粗集方法研究[J].测绘科学, 2007, 32 (1)
[12]高伟,吴文凯,袁超.高斯投影坐标变换[J].钢铁技术, 2008
[13]殷海峰,白征东,程伯辉.高斯投影公式的机助推导[J].测绘科学, 2008, 42 (1)
[14]傅凯新,黄云清,舒适.数值计算方法[M].湖南:湖南科学技术出版社, 2008: 185-186
[15]孔祥元,梅是义.控制测量学(第二版)下册[M].武汉:武汉大学出版社, 1996.
[16]孙家广.计算机图形学(第三版)[M].北京:清华大学出版社, 1998
[17]邬熙娟,江国焰,高俊强.子午线收敛角计算公式及计算精度分析[J].现代测绘, 2005, 28(6)
[18]伍俊良. Visual C++课程设计与系统开发案例[M].北京:清华大学出版社.2002: 1-37
[19]姜晨光,阎桂峰.椭球子午线弧长计算的新方法[J].测绘工程, 1998, 7(4)
[20]李建成,等.卫星测高在大地测量学中的应用及进展[J].测绘科学, 2006, 31(6)
[21]黄文生. A*算法的证明及其在人工智能领域的应用,2005, 39(6): 64-65
[22]潘金贵.现代汁算机常用数据结构和算法[M].南京:南京大学出版社,2004
[23] RUSSELL S, NORVIG P. Artificial Intelligence: A Modem Approach[M].北京:人民邮电出版社, 2002
[24]樊莉,孙继银,王勇.人工智能中的A算法应用及编程[J].微机发展, 2003, 13(5): 33-35
[25] Nedjeljko Franula. Transformation of Coordinates from the Krim System in the Area of Istria to the Gauss-Krüger Projection, 2003, 44(2): 167-174
[23] Piegl L. Key developments in computer aided geometric design [J]. CAD, 1989, 21(5)
[26] The tricriterion shortest path problem with at least two bottleneck objective functions [J]. Computer-Aided Design, 1977, 9(1): 48-52
[27] Ahuja et al. Ahuja RK, Magnanti TL, Orlin JB. Network flows [J]. New Jersey, 1991, 32(2): 221-226
[28] Azevedo and Martins, J.A. Azevedo and E.Q.V. Martins. An algorithm for the multi-objective shortest path problem on acyclic networks[J], Investiga??o Operacional 11 (1) (1991), pp. 52–69.
[29] Batta and Chiu, 1988 R. Batta and S.S. Chiu. Optimal obnoxious paths on a network [J]. Transportation of hazardous materials, Operations Research 36 (1988), pp. 84–92.
[30] Berman et al. Berman, D. Einav and G. Handler. Shortest paths in networks with vector weights [J], Operations Research 38 (1990), pp. 178–181.
[31] A. D. Kathryn, B. D. William. Multi-objective design of transportation networks [J].European Journal of Operation Research, 1995, 184(3): 506-521
[32]中国质量技术监督局,中华人民共和国国家标准:初始图形交换规范Initial Graphic Exchange Specification, IGES 5.3(GB/T 14213-2001)[s].北京:中国标准出版社, 2001
[33] David C. Key(美),John R. Levine(美)著,柏东译.图形图像文件格式大全[M].北京:学苑出版社, 1994: 103-185
[34] Jain P, Fenyes P, Richer R. Optimal blank nesting using simulated annealing[J]. Trans ASME J Mech Des, 1992, 114: 160-165
[35] Day A M. Planar convex hull algorithm in theory and practice [J]. Computer Graphics Forum, 1998, 7: 177-193
[36] Downsland K A. Some experiments with simulated annealing techniques for packing problems[J]. European Opt Res, 1993, 68: 389-399
[37] M Shpitalni, V Manevich. Optimal orthogonal subdivision of rectangular sheets[J]. Transactions of AS ME Journal of Manufacturing Science and Engineering, 1996, 118(3): 281-288
[38]乐阳,龚建雅.最短路径算法的一种高效率实现.武汉测绘科技大学学报, 1999: 62-64
[39]章永龙. Dijkstra最短路径算法优化.南昌工程学院学报, 2006, 08: 30-33
[40]王春梅,周献中.网络系统中的最短路径分析及其应用研究.兵工学报, 2007, 05: 51
[41]赵长胜.高期投影坐标换算的迭代算法[J].测绘通报. 2004, (3)
[42]姜晨光,阎桂峰.椭球子午线弧长计算的新方法[J].测绘工程, 1998, 7(4)
[43]李建成,等.卫星测高在大地测量学中的应用及进展[J].测绘科学, 2006, 31(6)
[44]王德春,陈利敏,张孝芳. A*算法在游戏地图寻径中的应用与实现[J].计算机应用与实现, 2005, 22(12)
[45] Koopmans. Activity analysis of production and allocation [J]. John Wiley & Sons (2001)
[2]张水舰,李永树,蔡国林,杨骏.基于GIS和AI的城市区域内最佳路径算法研究[J].测绘科学, 2008, 39(10): 1269-1272
[3]计会凤,徐爱功,隋达嵬. Dijkstra算法的设计与实现[J].辽宁工程技术大学学报, 2008, 14(8): 1-8
[4]王行风,贾凌. GIS支持下的城市交通网络最短路径研究[J].计算机与现代化, 2008, (3): 92121
[5] NOTO M, SATO H1A Method for the Shortest Path Search by Extended Dijkstra Algorithm [J] IEEE, 2009, (3): 31623201
[6]陆忠,钱翔东.基于最短路径查询的城市公交网络拓扑建模研究[J].遥感信息, 2002 (1): 112141
[7]徐业昌,李树祥.基于地理信息系统的最短路径搜索算法[J].中国图象图形学报, 1998 (1): 392431
[8]乐阳,龚健雅. Dijkstra最短路径算法的一种高效率实现[J].武汉测绘科技大学学报, 1999, 24(3): 20922121
[9]吴泉源,刘江宁.人工智能与专家系统[M].长沙国防科技大学出版社, 1995: 272-331
[10]陆锋,卢冬梅.交通网络限制搜索区域时间最短路径算法[J].中国图象图形学报, 2003, (10): 84928531
[11]李雯静,等. GIS数据分析中权重确定的粗集方法研究[J].测绘科学, 2007, 32 (1)
[12]高伟,吴文凯,袁超.高斯投影坐标变换[J].钢铁技术, 2008
[13]殷海峰,白征东,程伯辉.高斯投影公式的机助推导[J].测绘科学, 2008, 42 (1)
[14]傅凯新,黄云清,舒适.数值计算方法[M].湖南:湖南科学技术出版社, 2008: 185-186
[15]孔祥元,梅是义.控制测量学(第二版)下册[M].武汉:武汉大学出版社, 1996.
[16]孙家广.计算机图形学(第三版)[M].北京:清华大学出版社, 1998
[17]邬熙娟,江国焰,高俊强.子午线收敛角计算公式及计算精度分析[J].现代测绘, 2005, 28(6)
[18]伍俊良. Visual C++课程设计与系统开发案例[M].北京:清华大学出版社.2002: 1-37
[19]姜晨光,阎桂峰.椭球子午线弧长计算的新方法[J].测绘工程, 1998, 7(4)
[20]李建成,等.卫星测高在大地测量学中的应用及进展[J].测绘科学, 2006, 31(6)
[21]黄文生. A*算法的证明及其在人工智能领域的应用,2005, 39(6): 64-65
[22]潘金贵.现代汁算机常用数据结构和算法[M].南京:南京大学出版社,2004
[23] RUSSELL S, NORVIG P. Artificial Intelligence: A Modem Approach[M].北京:人民邮电出版社, 2002
[24]樊莉,孙继银,王勇.人工智能中的A算法应用及编程[J].微机发展, 2003, 13(5): 33-35
[25] Nedjeljko Franula. Transformation of Coordinates from the Krim System in the Area of Istria to the Gauss-Krüger Projection, 2003, 44(2): 167-174
[23] Piegl L. Key developments in computer aided geometric design [J]. CAD, 1989, 21(5)
[26] The tricriterion shortest path problem with at least two bottleneck objective functions [J]. Computer-Aided Design, 1977, 9(1): 48-52
[27] Ahuja et al. Ahuja RK, Magnanti TL, Orlin JB. Network flows [J]. New Jersey, 1991, 32(2): 221-226
[28] Azevedo and Martins, J.A. Azevedo and E.Q.V. Martins. An algorithm for the multi-objective shortest path problem on acyclic networks[J], Investiga??o Operacional 11 (1) (1991), pp. 52–69.
[29] Batta and Chiu, 1988 R. Batta and S.S. Chiu. Optimal obnoxious paths on a network [J]. Transportation of hazardous materials, Operations Research 36 (1988), pp. 84–92.
[30] Berman et al. Berman, D. Einav and G. Handler. Shortest paths in networks with vector weights [J], Operations Research 38 (1990), pp. 178–181.
[31] A. D. Kathryn, B. D. William. Multi-objective design of transportation networks [J].European Journal of Operation Research, 1995, 184(3): 506-521
[32]中国质量技术监督局,中华人民共和国国家标准:初始图形交换规范Initial Graphic Exchange Specification, IGES 5.3(GB/T 14213-2001)[s].北京:中国标准出版社, 2001
[33] David C. Key(美),John R. Levine(美)著,柏东译.图形图像文件格式大全[M].北京:学苑出版社, 1994: 103-185
[34] Jain P, Fenyes P, Richer R. Optimal blank nesting using simulated annealing[J]. Trans ASME J Mech Des, 1992, 114: 160-165
[35] Day A M. Planar convex hull algorithm in theory and practice [J]. Computer Graphics Forum, 1998, 7: 177-193
[36] Downsland K A. Some experiments with simulated annealing techniques for packing problems[J]. European Opt Res, 1993, 68: 389-399
[37] M Shpitalni, V Manevich. Optimal orthogonal subdivision of rectangular sheets[J]. Transactions of AS ME Journal of Manufacturing Science and Engineering, 1996, 118(3): 281-288
[38]乐阳,龚建雅.最短路径算法的一种高效率实现.武汉测绘科技大学学报, 1999: 62-64
[39]章永龙. Dijkstra最短路径算法优化.南昌工程学院学报, 2006, 08: 30-33
[40]王春梅,周献中.网络系统中的最短路径分析及其应用研究.兵工学报, 2007, 05: 51
[41]赵长胜.高期投影坐标换算的迭代算法[J].测绘通报. 2004, (3)
[42]姜晨光,阎桂峰.椭球子午线弧长计算的新方法[J].测绘工程, 1998, 7(4)
[43]李建成,等.卫星测高在大地测量学中的应用及进展[J].测绘科学, 2006, 31(6)
[44]王德春,陈利敏,张孝芳. A*算法在游戏地图寻径中的应用与实现[J].计算机应用与实现, 2005, 22(12)
[45] Koopmans. Activity analysis of production and allocation [J]. John Wiley & Sons (2001)