资源描述：
《启发式最短路径算法研究.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、启发式最短路径算法研究——以庐山路网寻径为例摘要：最短路径算法的效率是GIS、智能交通系统等应用领域普遍关注和迫切需要解决的问题。在深入分析经典的Dijkstra和启发式最短路径算法的基础上，选取A*启发式最短路径算法，以庐山交通路网为数据基础，对A*算法和Dijkstra算法进行了对比分析和测试。实验结果表明A*算法能够限制条件扩展节点,减少算法遍历的节点数目,降低执行时间,较经典Dijkstra算法具有更高的效率。在A*启发性算法中，可以将启发函数h(n)看作是节点值估计的约束条件，如果h(n)包含的信息
2、越多或约束条件越多，则排除的节点就越多，估价函数f(n)越好。因此，选择合适的估价函数对算法整体效率有很大影响。关键词：DijkstraA*最短路径算法Heuristicshortestpathalgorithmresearch--anexampleofnetworkroutingonMountLuAbstract:ShortestpathalgorithmefficiencyisapplicationareassuchasattentionandurgentneedstosolvetheprobleminG
3、IS,intelligenttransportationsystem.IndepthanalysisoftheclassicalDijkstraandheuristicshortestpathalgorithmbasedonA*,selectingheuristicshortestpathalgorithmintrafficnetworkontheA*algorithmandDijkstraalgorithmareanalyzedandtestedasMountLuforthedatabase.Theexpe
4、rimentalresultsshowthatA*algorithmcanlimittheconditionsofextendednodetraversalalgorithm,reducethenumberofnodes,reducetheexecutiontime,comparedwiththeclassicalDijkstraalgorithmhashigherefficiency.InA*heuristicalgorithm,heuristicfunctionh(n)canbeasthenodevalu
5、eestimateoftheconstraints,ifh(n)containsmoreinformationormoreconstraintconditions,thenexcludingnodesnumber,evaluationfunctionf(n)aspossible.Therefore,choosingtheappropriatevaluationfunctiononthewholealgorithmefficiencyhasagreatinfluence.Keywords:Dijkstra;A*
6、;shortestpathalgorithm目录1.序论31.1研究目的和意义31.2国内外研现状42.Dijkstra和启发式最短路径算法研究62.1图搜索算法和Dijkstra算法62.2启发式算法62.3A*算法72.4A*算法可接纳性82.4.1A*算法的条件82.4.2定理192.4.3定理2112.4.4一致性（或单调）条件122.4.5定理3132.5估计函数的选取153.实验环境和数据基础163.1软件环境163.2硬件环境163.3实验数据164．关键技术174.1启发式函数：174.2数据
7、预处理174.2.1读取数据184.2.2数据检查194.3邻接表构建拓扑195．算法实现215.1实现流程图215.2Dijkstra和A*算法的实现216．结论与展望266.1结论266.2展望267致谢278.参考文献281.序论1.1研究目的和意义随着计算机的普及以及地理信息科学的发展，地理信息系统(GocmetyrnIofmratinoSysetm，GIS)因其强大的功能得到日益广泛和深入的应用。网络分析作为GIS最主要的功能之一，在电子导航、交通旅游、城市规划以及电力、通讯等各种管网、管线的布局设
8、计中发挥了重要的作用，而网络分析中最基本、最关键的问题是最短路径问题[1]。在众多的路径搜索算法中,Dijkstra算法提供了从图的一个节点到另一个节点的最短路径。经过一次Dijkstra算法计算,可以得到从起点到图内被其搜索到的所有节点的最短路径,其时间复杂度为o(n^2)(其中n为图的节点数)。但是在实际应用中,所关心的是某两个特定节点之间的最短路径而非起点到其他点的情况,且在大规模网络中Dij
