-
最短路径问题一直是计算机科学、运筹学、地理信息科学等学科的一个研究热点。国内外大量专家学者对此问题进行了深入研究。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。他们在空间复杂度、时间复杂度、易实现性及应用范畴等方面各具特色。解决此最短路径问题最典型的算法是Dijkstra算法，该算法采用贪心策略，即每一步都选择与源节点构成局部路径距离最短的节点作为当前扩展节点来形成当前局部最短路径，进而得到全局的最短路径[3]。Dijkstra算法是已经证明的能得出单源路径的最优解，主要特点是以起始点为中心向外层扩展，直到扩展到终点为止。迪杰斯特拉算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构、运筹学等等。国内外大量专家对此问题进行过深入的研究。最短路径问题可分为单源最短路径问题及全源最短路径问题两种，其中单源最短路径问题更具有普遍意义，且可为全源最短路径问题提供良好的借鉴方案。单源最短路径问题的算法有很多种，从早期的奇遇限制条件的深度优化搜索算法、基于有向无环图的动态规划法、基于邻接矩阵的Dijkstra算法、到最大相关边缘法、最大相关点法、基于邻接表的Dijkstra算法 、A*算法、基于超图数据结构的深度优化椭圆算法等。而其中采用贪心策略的Dijkstra算法是目前已知得理论上最完美的算法，它要求在路径选择的每一步所选择的路径都是目前为止最好的，在局部最优而导致总体最优的假设下，寻求最佳路径不同的实现方法[10]。荷兰数学家E.W.Dijkstra（1959）提出的标号设定法（Label Setting Algorithms），是目前理论最完善，迄今为止应用最为广泛的飞负权值网络最短路径算法[12]。这是一种基于贪心策略的最短路径算法，他要求在路径选择中的每一步所选择的的路径都是目前最好的，在局部最优而导致总体最优的假设下，寻求最佳路径不同的实现方法，构成了Dijkstra算法的庞大的家族，与A*算法不同，为保证起点到当前节点的路径最优，Dijkstra算法要求对所有未访问过的节点进行搜索，包括反方向搜索。而针对网络中有可能存在的负权边的问题，采用不同启发式策略已在国内外有研究，即标号改正法可以解决存在负权边的网络最短路径问题，但它不能保证每次的循环都能发现一条最优路径，所以，由于交通网络中不存在负权边，所以交通网络最短路径算法常指标号设定法，也是改进了的Dijkstra算法。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN，CLOSE表的方式，这里均采用永久和临时标号的方式[13]。注意该算法要求图中不存在负权边。但它的效率是一个很大的问题。67353
- 上一篇：铝电解电容参数问题的研究现状
- 下一篇：小波变换的水下图像去噪研究现状
对于一座大中型城市，地理节点数目可能达到几万个到几十万个，计算单源路径的时间开销将是非常巨大的。蚁群算法是由意大利学者从蚂蚁群体觅食行为得到启发，提出的一种模拟蚂蚁行为的模拟进化算法。这种算法具有分布计算、信息正反馈和启发式搜索的特征，算法具有模拟生物界群体觅食的能力，并且能够在实际的路径搜索过程中对外界的影响做出动态的响应，因而在交通最优路径选择中具有极大的可能性和适应性。但是使用传统蚁群算法求最短路径问题却存在搜索速度慢，易于陷入局部最优解等缺陷[4]。对于基于抽象的网络图的最短路径问题的求解方法，由于其在交通、计算机网络、运筹等多门学科中的多种应用需求，多年以来得到了充分的关注并取得了大量研究成果。在这诸多的研究中，大都是基于网络图路径权值为常量的静态算法。网络路径权值随时间发生变化的动态最短路径查找算法随着计算机处理速度不断提高以及应用需求的不断增加，近年来得到了更加广泛的关注。最短路径问题是交通网络分析中的一个重要问题，也是一个研究热点。它是资源分配、路线设计及分析等优化问题的基础，具有重要理论意义和实际应用价值。有许多研究者曾对最短路径算法进行了大量的研究，并取得了很大的进展，提出了很多解决这类问题的方法。最短路径是人们长期研究的数据结构问题。二十世纪以来，随着人工智能技术的发展，主要利用各种智能优化算法，如Dijkstra 算法寻找最短路径。 目前最短路径问题的运用，仍有不少值得探讨的地方，而且人们还不能自觉地将最短路径问题运用与现实生活，没有最短，只有更短。在享受现有成果的同时，论文网我们还需要进一步的思考与探索。掌握图论最短路径的相关学习理论,能够了解经典Dijkstra 算法的思想，并且能熟练操作计算机并进行编程，找出最短路径。本算法实在基于 Dijkstra 算法的基础上求图中任意俩点间最短距离的算法。鉴于交通状况的随时性，如某一时刻拥挤，下一时刻却非常流畅的情况，讨论交通拥挤的情况下的最短路径问题。蚁群算法是由意大利学者Dorigo M等人于1991年从自然界蚂蚁群体觅食行为得到启发,提出的一种模拟蚂蚁行为的模拟进化算法人工蚁群算法,简称蚁群算法。这种算法具有分布计算、信息正反馈和启发式搜索的特征,算法具有模拟生物界群体觅食的能力,并且能够在实际的路径搜索过程中对外界的影响做出动态的响应,因而在交通最优路径选择中具有极大的可能性和适应性。然而使用传统蚁群算法求最短路径问题却存在搜索速度慢,易于陷入局部最优解等缺陷,为此本文针对交通网络最短路径问题的特点,在传统蚁群算法中引入搜索方向机制和搜索热区机制提高算法搜索性能。 对于基于抽象的网络图之中的最短的路径问题(shortestPath Problem，简称sPP) 的求解方法[5]，由于其在通信、交通、计算机网络、运筹、管理等多门学科中的多种应用需求，多年以来得到了充分的关注并取得了大量研究成果。在这诸多的研究中，大都是基于网络图路径权值为常量的静态算法。网络路径权值随时间发生变化的动态最短路径查找算法随着计算机处理速度不断提高以及应用需求的不断增加，近年来得到了更加广泛的关注。在网络图中两特定结点之间的最短路径：此问题也即源点-汇点最短路径问 题，最经典韵算法就是Dijkstra所提出的算法，此算法依照路径的长度依次产生 从起始结点到网络图中所有结点的最短路径[6]。自Dijkstra算法提出以后，又历经 了多人在具体实施方法上的改进，使其求解速度大幅提高。解决此问题其他常用 的算法包括Bellman，Ford，Moore等人分别提出的动态规划(Dynamic Programming)算法，也称为Bellman—ford算法，该算法解决网络中单源点最短 路径问题； Pape， Pallottino等人各自提出的增长图(Graph． Growth)算法； Glover 等人提出的结合以上各算法思想的域阀(Threshold)算法[15]。Hart．eta1提出了A* 启发式搜索算法。 对网络图中所有结点对之间的最短路径问题：解决较好的两个方法是Floyd 提出的一个算法一一Floyd算法，以及另一个被Dantzig提出的算法。两者的计算 复杂度相同，都是可以优先选择的算法。Dijkstra算法只能解决无负边权重的最短路径问题，在欧几米得网络(例如 交通路网)中，通过对Dijkstra算法使用下限函数的方法称为欧几米得试探法， 欧几米得试探法解决欧几米得图中的源点-汇点最短路径问题。欧几米得试探法 是A*算法的一个特例，Dijkstra算法是一种下限为O的A*。 在网络图中计算源点到汇点间依照路径长度产生的前k条最短路径：对此问 题最早的解决算法是Hofhnan，Pavley提出的，Dreyfus对此算法作了进一步的改进，另一个应用广泛的经典的解决此问题的算法是Shier提出的。 最近， Eppstein 提出的采用k个最短路径的隐式表达计算的最短路径算法性能有了比较显著的提 高。从Dijkstra算法到Hoffman，Pavley提出的算法都为基于顺序的算法。但 Chandy and Misra算法是一种计算k个最短路径问题的并行算法，其时间复杂度比顺序算法要小[12]。