计算机应用研究

作者：马一鸣,胡小兵,周航,

单位：中国民航大学a.中欧航空工程师学院;b.安全科学与工程学院,天津300300；

关键词：最短路径巡游问题,涟漪扩散算法,问题分解,路径优化,多对多路径优化,

基金：天津市教委科研计划资助项目(2020KJ037)；；

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

来源：2022年第11期

《计算机应用研究》期刊编辑部

查看计算机应用研究杂志2022年第11期