摘要
针对k最短路径问题(k-SPP)的高效求解需求,提出了一种基于涟漪扩散算法(RSA)的改进方法。首先,对原始RSA进行优化,限制每个节点产生的涟漪数量以提高计算效率,形成近似涟漪扩散算法(ARSA)。其次,提出一种终端策略H T,通过对节点分层并设置不同的涟漪上限,以权衡最优性和计算效率。同时,利用模糊推理系统(FIS)根据网络特征动态设置终端策略H T,提高算法适用性。仿真实验结果表明,在网格网络、随机网络、小世界网络及无标度网络中,终端策略H T能有效提升ARSA的性能,而模糊推理系统则实现了终端策略的快速设置。现实网络的实验验证了改进算法在求解k-SPP上的高效性和可靠性,为复杂网络环境中的路径规划提供了新的解决思路。
This paper proposed an improved algorithm to enhance the efficiency and adaptability of solving the k-shortest path problem(k-SPP)in complex network environments.The algorithm optimized the original ripple spreading algorithm(RSA)by limiting the number of ripples generated by each node,which increased computational efficiency and formed the approximate ripple spreading algorithm(ARSA).It introduced a terminal strategy H T,by layering nodes and setting different ripple limits to balance optimality and computational efficiency.It further enhanced the strategy’s adaptability by utilizing a fuzzy inference system(FIS),which dynamically adjusted the H T strategy based on network characteristics.Simulation experiments conducted on grid,random,small-world,and scale-free networks show that the H T strategy significantly improves ARSA’s performance,while the FIS enables rapid configuration of the H T strategy.Experimental results indicate that the proposed algorithm achieves high efficiency and reliability in solving k-SPP,providing a novel approach to path planning in complex network environments.
作者
王瑞祥
张盈斐
李航
胡小兵
Wang Ruixiang;Zhang Yingfei;Li Hang;Hu Xiaobing(Sino-European Institute of Aviation Engineering,Civil Aviation University of China,Tianjin 300300,China;College of Safety Science&Engineering,Civil Aviation University of China,Tianjin 300300,China)
出处
《计算机应用研究》
北大核心
2025年第6期1762-1770,共9页
Application Research of Computers
基金
国家重点研发计划项目课题(2023YFB4302901)
天津市自然科学基金多元投入青年项目(23JCQNJC00230)
中央高校基本科研业务费专项资金资助项目(3122023034)。
关键词
k最短路径问题
近似涟漪扩散算法
终端策略
模糊推理系统
路径规划
k-shortest paths problem
approximate ripple spreading algorithm
terminal strategy
fuzzy inference system
path planning
