基于无向图Floyd加速模型的海图抽选方法研究

作者：吕程; 李改肖; 彭认灿; 董箭

来源：海洋测绘, 2018, 38(05): 41-45.

• 海洋地理信息系统
• 航海保障
• Floyd算法
• 最短路径集
• 海图抽选

为解决传统海图抽选存在的主观性高和抽选效率低的问题,尝试将图论中的Floyd算法应用到海图抽选问题中,通过在无向图多路径数据结构中对Floyd算法进行加速改进,提出了一种基于无向图Floyd加速模型的海图抽选方法。该方法通过对网络图及算法进行优化,实现了抽选海图航路覆盖范围的最大化和抽选海图数量的最小化,并将时间复杂度降至O(1/2(n)(n-1)2);通过利用基于等价点数组的最短路径集算法,实现了同等海图数量前提下的不同海图选取方案。最后通过实验验证了上述模型在海图选取中的可行性和优越性。

• 单位
  中国人民解放军海军大连舰艇学院