资源描述：
《最短路径问题及其解法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、最短路径问题及其解法研究ComputerKnowledgeandTechnology电脑知识与技术软件设计开发本栏目责任编辑：谢媛媛第6卷第6期(2010年2月)最短路径问题及其解法研究周先曙（中国人民解放军75742部队，广东广州510515）摘要：最短路径问题是在给定的网络图中寻找出一条从起始点到目标点之间的最短路径。该文分别从动态规划、Dijkstra、A*算法、遗传算法这四种算法设计方法入手，概述了各种设计方法的原理，提出了求解最短路径的算法思想，并对算法进行分析，提出了改进方法。关键词：最短路径；动
2、态规划；Dijkstra算法；A*算法；遗传算法中图分类号：TP312文献标识码：A文章编号：1009-3044(2010)06-1403-03ShortestPathProblemanditsSolutionMethodsStudyZHOUXian-shu(People'sLiberationArmy75742Units,Guangzhou510515,China)Abstract:Shortestpathproblemistofindashortestpathfromthestartpointtothee
3、ndpointinagivennetgraph.Thispaperwillintro-ducefouralgorithmdesignmethods,whichareDynamicprogramming,Dijkstraalgorithm,A-staralgorithm,Geneticalgorithm,summarizetheirbasictenets,givethesolvingalgorithmthoughttotheshortestpathproblem,analysethealgorithmsandp
4、utforwardtheimprovingmethods.Keywords:shortestpath;dynamicprogramming;Dijkstraalgorithm;A-staralgorithm;geneticalgorithm最短路径问题是在给定的网络图中寻找出一条从起始点到目标点之间最短路径。最短路算法不仅在GIS的交通路线导航、路径分析领域应用广泛,在解决路径搜索相关的应用中也十分普遍,包括网络路由算法、机器人探路、人工智能、游戏设计等等。本文分别从动态规划、Dijkstra、A*算法、遗传
5、算法这四种算法设计方法入手，概述了各种设计方法的原理，提出了求解最短路径的算法思想，并对算法进行分析，提出了改进方法。1最短路径的搜索算法概要1.1动态规划算法动态规划算法的基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。动态规划算法使用于解最优化问题。通常可以按以下步骤设计动态规划算法：1）找出最优解的性质，并刻画其结构特征；2）递归地定义最优解；3）以自底向上的方式计算出最优解；4）根据计算最优值时得到的信息，构造最优解。步骤1）~3）是动态规划算法的基本步骤。
6、在只需要求最优值的情形，步骤4）可以省去。若需要求问题的最优解，则必须执行步骤4），此时，在步骤3）中计算最优解时，通常需记录更多的信息，以便在步骤4）中，根据所记录的信息，快速构造出最优解。1.2Dijkstra算法Dijkstra算法是Dijkstra提出的一个按路径长度递增的顺序逐步产生最短路径的算法。该算法的基本思想是：设置两个定点的集合T和S，集合S中存放已找到最短路径的定点，集合T中存放当前还未找到的最短路径的定点。初始状态时，集合S中只包含原点v0，然后不断从集合T中选取到定点v0路径长度最短的
7、顶点u加入集合S，集合S中每加入一个新的顶点u，都要修改定点v0到集合T中剩余顶点的最短路径长度值，集合T中个顶点新的最短路径长度值为原来的最短路径长度值与定点u的最短路径长度值加上u到该顶点的路径长度值中的较小值。次过程不断重复，直到集合T的顶点全部加入到集合S为止。1.3A*算法A*算法则是人工智能领域的一种图搜索策略,采用了启发式函数对搜索过程中产生的分支进行评估,以选择最佳的分支进行搜索。其更一般的引入了一个估价函数f(n),其定义为f(n)=g(n)+h(n)。其中g(n)为到达当前节点的耗费,而h
8、(n)表示对从当前节点到达目标节点的耗费的估计,要求评估函数满足h(n)<=h*(n)。其必须满足两个条件：1)h(n)必须小于等于实际的从当前节点到达目标节点的最小耗费h*。2)f(n)必须保持单调递增。1.4遗传算法遗传算法是一类借鉴生物界自然选择和自然遗传机制的随机化的搜索算法,由美国J.Holland教授提出,其主要特点是群体搜收稿日期：2010-01-04作者简介：周先曙（1984-），湖
