一种快速求解最短路径巡游问题的涟漪扩散算法

针对最短路径巡游问题（SPTP），提出了基于涟漪扩散算法（RSA）特征的SPTP分解方法。RSA通过模拟水面上涟漪传播的现象，在SPTP子问题间建立联系，相较于其他基于问题分解的算法减少了计算冗余度。进一步改进RSA，使其在维持时间复杂度不变的情况下求解多起点—多终点SPTP。在多种拓扑结构的网络中进行对比实验，结果表明，RSA在保证最优性的同时运算效率最高。RSA对于多起点—多终点SPTP的高效求解，可为多种现实问题快速提供解决方案，具有很高的应用价值。

Efficient ripple-spreading algorithm for shortest path tour problem

For the shortest path tour problem(SPTP), this paper proposed the specific decomposition method for the ripple-spreading algorithm(RSA) to solve the SPTP. The RSA simulated ripple propagation patterns on the water surface and established connections among subproblems, which reduced computational redundancy compared to other decomposition methods. This paper adapted the RSA to make it solve the SPTP with multiple sources and destinations while maintaining time complexity. Comparative experiments on various network topologies show that the RSA ensures optimality and outperforms other algorithms in computational efficiency. The efficiency of the RSA when solving the SPTP with multiple sources and destinations makes it can provide solutions to real-world problems efficiently and demonstrates its application values.