a算法在矢量地图最优路径搜索中的应用

《a算法在矢量地图最优路径搜索中的应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、A*算法在矢量地图最优路径搜索中的应用刘浩,鲍远律(中国科学技术大学自动化系，安徽合肥230027)摘要:A*算法是启发式搜索算法的一种，广泛应用于图搜索和路径规划。本文简要介绍了A*算法，并通过对A*算法可接纳性和一致性的分析，说明了A*算法是一类适合矢量地图最优路径搜索的较好算法。关键词:最优路径，A*算法，矢量地图，GISA*AlgorithmfortheShortestPathonVectorMapsLIUHao，BAOYuanlu(DepartmentofAutomation,UniversityofScienceandTechnologyofChin

2、a,HefeiAnhui230027)【Abstract】A*algorithmisoneofheuristicsearchalgorithms,whichcommonlyusedingraphsearchandpathplan.ThisthesisintroducesA*algorithmbriefly.ThroughtheanalysisofadmissibilityandconsistencyofA*algorithm,theauthorillustratesthatA*algorithmisakindoffairlygoodalgorithmsuitab

3、leforvectormaps.【Keywords】optimalpath,A*algorithm,vectormap,GIS1问题的由来求解最短路径问题的首选算法，同时也是经典算法，最优路径问题是一个很古老的问题，其原型是其优势在于求解单个顶点到其余所有顶点间的最优运筹学中的最短路径间题，目前在互联网的寻址计路径，但用以求解单对顶点间的最优路径问题时必算、智能交通系统，地理信息系统等领域有着广泛然产生冗余，故不是一个应用到实际路径寻优的较的应用。现代意义上的最优路径已不再仅仅是指地好算法。基于启发式搜索的A*算法，因其在路径搜理意义上的距离最短，它还可以是指时

4、间最少、费索过程中对问题域信息的充分利用，使得搜索的目用最省、线路容量最大等等。但无论采用何种标准，标性更加明确，是求解单对顶点间最优路径的一类最优路径问题都可归结为在带权网络中寻找最短路较好算法。[1～5]径的研究，即图论中的最短路径问题。2最优路径的研究现状随着信息科学的发展,地理信息系统(GIS)广泛最优路径问题的本质是路径搜索。从搜索算法应用于人们生产和生活的各个领域，在各类的GIS的实时性的角度可以分为两类：静态最优路径和动应用中，交通地理信息系统(GIS-T)又是其中的一个态最优路径。前者在路径寻优的过程中路径的权值热点研究领域。当代世界各发达国家和

5、部分发展中为定值，后者路径的权值则可以根据交通状况实时国家都在积极发展智能交通系统(ITS)，以缓解由于变化，以适应动态寻优。虽然后者更能反应实际的经济发展导致的出行需求增长和由于交通智能化不情况，但是对交通环境的智能化要求也较高，即要够导致的出行需求不能得到较好满足之间的矛盾。求能够实时接收交通信息以更新路径的权值。在国[1]在ITS所包含的6个高级交通系统中，有4个与外，动态最优路径算法研究是的一个热点，尤其是GIS-T支持下的交通网络分析直接相关。交通网络在一些发达国家。我国目前在交通网络最优路径方分析的一个重要组成部分是路径分析，而路经分析面的研究主要还

6、是集中在静态最优路径算法上，其的核心为最优路径算法。因此，对最优路径问题的中一个重要原因在于我国的交通智能化水平不高，研究不但具有重要的理论价值,而且具有重要的应限于人口、环境、经济发展等种种因素，我国的ITS用价值。总体上仍然还处在一个初级的发展阶段。矢量地图是大多数GIS应用(如定位、导航、监从问题求解目标的不同，可将搜索算法分为求控等等)的基础，是对实际交通网络拓扑的一个近似基金项目：国家自然科学基金资助项目(60272040)反映。从而，我们可将在交通网络分析中的最优路作者简介：刘浩(1980-),男,硕士研究生,主研方向：智径问题的研究转化为在矢量地图

7、中求解最优路径算能交通网络系统，最优路径；鲍远律,教授。法的研究。Dijkstra算法是目前GIS应用领域用于E-mail：haohanliu@gmail.com解单源点多汇点的最优路径和所有顶点对之间的最[3]4A*算法的简介优路径。前者的典型代表如Dijkstra算法，后者的4.1算法的提出典型代表如Floyd算法。Nilsson曾开发一个通用的图搜索算法。根据插入到OPEN表(一种表示已搜索到但尚未扩展的节从搜索算法的是否具有智能性的角度，可将其点集合的数据结构)中的新产生节点重排方式的不分为两大类，即盲目搜索和启发搜索。前者如BFS同，这个图搜索算法可以

8、演化成宽度优先算法算法、