国内外最短路径算法的发展研究现状概况
对于一座大中型城市，地理节点数目可能达到几万个到几十万个，计算单源路径的时间开销将是非常巨大的。蚁群算法是由意大利学者从蚂蚁群体觅食行为得到启发，提出的一种模拟蚂蚁行为的模拟进化算法。这种算法具有分布计算、信息正反馈和启发式搜索的特征，算法具有模拟生物界群体觅食的能力，并且能够在实际的路径搜索过程中对外界的影响做出动态的响应，因而在交通最优路径选择中具有极大的可能性和适应性。但是使用传统蚁群算法求最短路径问题却存在搜索速度慢，易于陷入局部最优解等缺陷[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]。
上一篇：铝电解电容参数问题的研究现状
下一篇：小波变换的水下图像去噪研究现状