一種基于終端策略的近似漣漪擴(kuò)散算法

打開文本圖片集

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）是圖論中的經(jīng)典問題，其目標(biāo)是在給定的有向圖中尋找從起點(diǎn)到終點(diǎn)的k 條最短路徑。（剩余15451字）