基于仿水流算法的最短路径问题求解

使用传统算法求解最短路径问题时,收敛速度慢,且求得的路径并不是所有行程的最短路径。为此文章提出一种求解最短路径问题的仿水流算法。该算法结合水流量局部更新和全局动态更新,能够动态调配水流量值,避免算法陷入停滞状态;局部搜索中,对于更优路径的水流使用2-opt方法进行搜索,以此提高收敛速度。仿真实验验证了该算法的有效性,与其他算法相比,仿水流算法收敛速度快,收敛精度高,鲁棒性好,所求的最短路径明显优于传统算法。

A Solution to the Shortest Path Problem Based on the Imitation Flow Algorithm

When the traditional algorithm is applied to solve the shortest path problem, the convergence rate is slow and the obtained path is not the shortest of all. To overcome this shortcoming, the authors of this paper propose a water flow algorithm to solve the shortest path problem. The algorithm, based on the local update of the water flow and the global dynamic update, can dynamically allocate the water flow value and avoid the hysteresis of the algorithm. In the local search, the 2-opt method is used for the optimum water path to improve the convergence rate. The simulation results show that the algorithm has the advantages of fast convergence speed, high convergence precision and good robustness, and the shortest path is superior to those obtained through the traditional algorithm.