一种基于终端策略的近似涟漪扩散算法

打开文本图片集

Approximate ripple spreading algorithm based on terminal strategy

Wang Ruixianga，Zhang Yingfeib，Li Hangʰ，Hu Xiaobingʰt （a.Sino-EuostoatonColfSfece&in，iltonUesitf 300300，China）

Abstract： This paper proposed an improved algorithm to enhance the efficiency and adaptability of solving the k -shortest path problem （ k -SPP） incomplex network environments.The algorithm optimized the original ripple spreading algorithm（RSA） bylimiting thenumberofripplesgeneratedbyeachnode，which increasedcomputational eficiencyandformed theapproximate ripple spreading algorithm（ARSA）. It introduced a terminal strategy HT ，by layering nodes and setting different ripple limits tobalanceoptimalityandcomputationaleficiency.Itfurtherenhanced thestrategy’sadaptabilitybyutilizingafuzzy inference system（FIS），which dynamically adjusted the HT strategy based on network characteristics. Simulation experiments conducted on grid，random，small-world，and scale-free networks show that the HT strategy significantly improves ARSA’s performance，while the FIS enables rapid configuration of the HT strategy. Experimental results indicate that the proposed algorithm achieves high eficiency and reliability in solving k -SPP， providing a novel approach to path planning in complex network environments.

Key words： k -shortest paths problem； approximate ripple spreading algorithm；terminal strategy； fuzzy inference system;path planning

0 引言

k 最短路径问题（kshortestpathsproblem， k -SPP）是图论中的经典问题，其目标是在给定的有向图中寻找从起点到终点的k 条最短路径。（剩余15451字）