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

Review of Charts Selection Approaches Based on Undirected Graph Floyd Acceleration Model

作　　者：吕程 李改肖 彭认灿[1,2] 董箭 LU Cheng;LI Gaixiao;PENG Rencan;DONG Jian(Department of Military Oceanography and Hydrography ＆ Cartography,Dalian Naval Academy,Dalian 116018,China;Key Laboratory of Hydrography and Cartography of PLA,Dalian 116018,China)

机构地区：[1]海军大连舰艇学院军事海洋与测绘系,辽宁大连116018 [2]海洋测绘工程军队重点实验室,辽宁大连116018

出　　处：《海洋测绘》2018年第5期41-45,共5页Hydrographic Surveying and Charting

基　　金：国家自然科学基金(41601498)

摘　　要：为解决传统海图抽选存在的主观性高和抽选效率低的问题,尝试将图论中的Floyd算法应用到海图抽选问题中,通过在无向图多路径数据结构中对Floyd算法进行加速改进,提出了一种基于无向图Floyd加速模型的海图抽选方法。该方法通过对网络图及算法进行优化,实现了抽选海图航路覆盖范围的最大化和抽选海图数量的最小化,并将时间复杂度降至O(1/2(n)(n-1)~2);通过利用基于等价点数组的最短路径集算法,实现了同等海图数量前提下的不同海图选取方案。最后通过实验验证了上述模型在海图选取中的可行性和优越性。In order to solve the problems in traditional charts selection such as subjectivity and inefficiency, the paper attempts to introduce the Floyd algorithm in Graph theory into the charts selection.By accelerating the Floyd algorithm in undirected graph which is multi-path data structure, a method based on undirected graph acceleration model is proposedtoselect the minimum number of charts that cover the route.The Time Complexityof the model is O（1/2（n）（n-1）2）.Besides, the shortest paths algorithm based on the equivalent points group isused to calculate all the shortest paths with the same origin and destination, which means that the different chart selection scheme of the same chart quantity. Finally, an example is given to demonstrate the feasibility and superiority of the model in charts selection.

关 键 词：海洋地理信息系统 航海保障 FLOYD算法 最短路径集 海图抽选 

分 类 号：P283[天文地球—地图制图学与地理信息工程]