| 基于无向图Floyd加速模型的海图抽选方法研究 |
| |
| 引用本文： | 吕程,李改肖,彭认灿,董箭.基于无向图Floyd加速模型的海图抽选方法研究[J].海洋测绘,2018(5):41-45. |
| |
| 作者姓名： | 吕程 李改肖 彭认灿 董箭 |
| |
| 作者单位： | 海军大连舰艇学院 军事海洋与测绘系,辽宁 大连 116018;海军大连舰艇学院 军事海洋与测绘系,辽宁 大连 116018 ;海洋测绘工程军队重点实验室,辽宁 大连 116018 |
| |
| 基金项目： | 国家自然科学基金(41601498) |
| |
| 摘 要： | 为解决传统海图抽选存在的主观性高和抽选效率低的问题,尝试将图论中的Floyd算法应用到海图抽选问题中,通过在无向图多路径数据结构中对Floyd算法进行加速改进,提出了一种基于无向图Floyd加速模型的海图抽选方法。该方法通过对网络图及算法进行优化,实现了抽选海图航路覆盖范围的最大化和抽选海图数量的最小化,并将时间复杂度降至O(1/2(n)(n-1)~2);通过利用基于等价点数组的最短路径集算法,实现了同等海图数量前提下的不同海图选取方案。最后通过实验验证了上述模型在海图选取中的可行性和优越性。
|
| 关 键 词： | 海洋地理信息系统 航海保障 Floyd算法 最短路径集 海图抽选 |
Review of Charts Selection Approaches Based on Undirected Graph Floyd Acceleration Model |
| |
| Abstract: | 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 Complexity of the model is  .Besides,the shortest paths algorithm based on the equivalent points group is used 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. |
| |
| Keywords: | |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《海洋测绘》浏览原始摘要信息 |
| 点击此处可从《海洋测绘》下载免费的PDF全文 |
|
