最短路径方法解析

《最短路径方法解析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、求最短路的方法探讨摘要：探讨的不同类型的最短路径的算法，并给出了相应的算法以及一些算法的时间复杂度，从而看不同算法之间的优点和缺点以及各自适用的领域。关键词：图论；盲目搜索；蚁群算法1引言最短路算法不仅在GISd交通路线导航、路径分析领域应用广泛，在解决路径搜索相关的应用中也十分普遍，包括网络路由算法、机器人探路、人工智能、游戏设计等等。在搜索问题中，主要的工作是找到正确的搜索策略。一般搜索策略可以通过下面4个准则来评价。完备性：如果存在一个解答，该策略是否保证能够找到？时间复杂性：需要多长时间可以找到？空间复杂度：执行搜

2、索需要多少存储空间？最优性：如果存在不同的几个解答，该是否可以发现最高质量的解答？最短路径问题目前主要有4类算法：①基于图论的算法，如迪克斯屈拉(Dijkstra)、弗洛伊德(Floyd)及其改进算法等；②基于优化理论的数学规划算法；③基于传统人工智能的搜索算法，如盲目搜索，启发式及其改进算法等；④基于现代计算智能的搜索算法，如人工神经网络、遗传算法、免疫算法和蚁群算法等。迪杰斯特拉算法其实也是一种启发式搜索算法，效率高于盲目搜索算法，而启发式及其改进算法效率取决于启发性知识的优劣，基于图论算法和数学规划算法理论严密，能获

3、得最优解，但适应性差，③和④算法适应性好，但理论不够严密，获得次优解的可能性大。2基本概念最短路径设有向图，其中为图G的点集合，为图G边的集合，边，为边的起点，为边的终点。为图G中边E所对应的权重集合。路径和路径权设，其中是中的一个点边交错序列，并且对于，均有，则称P为从到的一条路径。路径P的权为：（1）最短路径在所有从到的路径P中，权最小的路径，即满足（2）式的路径称为从到的的最短路径，的权称为从到的的最短路径距离，如（2）式所示：（2）3基于图论的算法：1．迪克斯屈拉算法ProcedureDijkstra(G:所有权都

4、为正数的加权连通简单图){G带有顶点和权，若不是G中的边，则}Fori:=1ton{初始化标记，a的标记为0，其余结点标记为，S是空集}WhileBeginu：=不属于S的最小的顶点S：=For所有不属于S的顶点vIfThen{这样就给S中添加带最小标记的顶点并且更新不在S中的顶点的标记}End{从a到z的最短路的长度}2弗洛伊德(Floyd)算法：已知n阶加权简单图G，设是图G的边权矩阵，即（若G是有向图，则），若结点i到结点j无边相连，则取。然后，依次计算出矩阵及S。其中…………其中，表示从结点i到j经k边的路（在有向

5、图中即为有向路）中的长度最短者，而为结点i到j的所有路（若是有向图，即为有向路）中的长度最短者。不难看出，Floyd算法的时间复杂度为3Warshall算法已知n阶加权简单图G，设是图G的边权矩阵。（1）输入D；（2）；（3）；（4）；（5），若，转（4）；（6），若，转（3）；否则停止。该算法是对i,j,k进行循环，故它的时间复杂度为，即对矩阵D进行k次修改。4基于优化理论的数学规划算法：实际的结构优化设计问题一般是有约束的非线性规划问题，然而，对于非线性规划问题，至今还没有找到一个普遍有效的统一算法，对同一个设计问题的

6、计算效率，往往因为采用不同的算法而有明显的差别。因此，结构设计人员应该多掌握几种算法。常用的有：拉格朗日乘子法和罚函数法及解决无约束优化问题的变尺度法和黄金分割法（0.618法）。5基于传统人工智能的搜索算法：盲目搜索盲目搜索又叫做无信息搜索，一般只适用于求解比较简单的问题。广度优先搜索和深度优先搜索，属于盲目搜索方法。深度优先搜索深度优先搜索总是扩展搜索树的当前边缘中最深的结点，当那些结点扩展完之后，它们被边缘中去掉，然后搜索算法“向上回到”下一个还未扩展后继结点的稍浅的结点。算法如下：ProcedureDepthFir

7、stSearchBegin(1)把初始结点压入栈，并设置栈顶指针；(2)While栈不空doBegin弹出栈顶元素；If栈顶元素=goat,更新源节点到目结点的最短路径；Else以任意次序把栈顶元素的子女压入栈中；EndWhileEed广度优先搜索广度优先搜索是一个简单的搜索策略，首先扩展根节点，接着扩展根结点的所有后继，然后再扩展它们的后继，依此类推。一般来讲，在下一层的任何结点扩展之前搜索树上本层尝试的所有结点都已经扩展过。算法如下：ProcedureDepthFirstSearchBegin(1)把初始结点放入队列；

8、(2)While队列不空doBegin取得队列最前面的元素为current；Ifcurrent=goat,成功返回并结束；ElseIfcurrent有子女，把它的子女以任意次序添加到队列尾部；EndWhileEed双向广度搜索所谓双向广度搜索指的是搜索沿两个方向同时进行，正向搜索：从初始结点向目标结点方