西电数模大作业.doc

《西电数模大作业.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、.word格式,关于中国南海岛礁巡航路线方案的探讨姓名：刘发强学号：14020199044,专业.专注..word格式,2016年11月8日摘要南海岛礁巡航路线方案的确定实质上是一个求取平面有障碍区域两点之间最短路径问题和TSP问题的混合。针对前者，本文借助ESPO算法的思想,专业.专注..word格式,，将外国非法侵占岛礁所确定的12海里敏感区域抽象为正多边形，在对所有顶点及起始点之间任一条路径的合法性判定（借助计算几何中点、线段、多边形的位置关系）之后，利用Dijkstra算法生成障碍密集区（南沙群岛）我方任意两岛礁之间的最短路径，后对我方

2、全体（西沙、南沙、中沙）岛礁利用Floyd算法生成最短路径完全图的邻接矩阵，为后续处理奠定基础。针对后者，利用自适应的蚁群算法求取最优解，经检验效果较好。同时借助openCV提供的图像处理和画图函数对算法的运行和结果进行了可视化呈现，易于理解调试。理论上，本文的解决方案对于这类问题有很广泛的适用性。关键词：TSP问题；ESPO算法；Dijkstra算法；Floyd算法；openCV；蚁群算法；算法可视化,专业.专注..word格式,绪论随着中国海权意识的逐步觉醒和军事力量的日益强大以及美国重返亚太战略的实施，南海态势在多方的博弈下波谲云诡，不安

3、定不稳定性极大。为了维护我国的主权和领土完整，对我国实际控制的岛礁进行周期性的补给和巡航势在必行。因此，在周围情况极其复杂的南海确定一个最优的巡航路径非常关键。本文主要借助ESPO算法和蚁群算法对我国南海实际控制的包括西沙、中沙、部分南沙在内的23个岛礁进行了路径规划，比较圆满的解决了上述问题，且具有良好的可扩展性和适用性。本文的基本假设：1、地球表面近似为球面，在经线上，每纬度约111千米，在纬线上，每经度约为111*cos千米，其中为纬度。由于所考查区域（纬度从东经111°到东经117°，北纬8°到北纬18°）面积相对较小且在低纬度，故近似

4、为平面即每经度111千米。利用百度地图的测距工具和坐标拾取系统得出的结果与对平面上两点欧几里得距离相比最大相对误差低于1%，这对于本问题的解决足够准确。2、岛礁抽象为其几何中心处一点。3、,专业.专注..word格式,本文考察西沙群岛、中沙群岛的所有岛礁和南沙群岛的7个岛礁。由于中沙群岛大部分在中部呈一紧凑环装分布，为了简化且不失准确性，将大环礁抽象为环北一点和环南一点。1、本文所规划的路径除不可避免之外不进入外国侵占岛礁所形成的12海里敏感区域，由于东门礁、南薰礁距离鸿庥岛和九章群礁过近，在此两处将12海里放宽为6海里。2、由于部分岛礁之间平

5、面欧几里得距离远大于其面积尺度，故在无障碍区即西沙、中沙我方岛礁的最短距离可以由平面欧几里得距离代替。并且最优解中，可以预见路径穿越岛礁的可能性极小，再次印证上述假定的合理性。3、在构造最短路径完全图的过程中，对于非南沙与非南沙之间、非南沙和南沙之间其距离认定为其平面欧几里得距离，南沙群岛各岛礁距离利用ESPO算法生成，由于南沙距离非南沙相对于其尺度很大，故近似比较准确。,专业.专注..word格式,方案形成过程南海岛礁经纬度采集和部分岛礁之间的测距借助百度地图及其提供的坐标拾取系统和测距工具，获取了我方23个岛礁、他方18个岛礁的经纬度信息和

6、用于连通南沙我方部分岛礁（障碍外部）与中南暗沙、大环礁、中建岛、盘石屿等岛礁的距离。并利用MATLAB计算了我方非南沙各岛礁之间的欧氏距离，从而生成了一部分最短路径完全图。由于表格较大，不在此呈现，详见表格。图1南海部分岛礁,专业.专注..word格式,南沙群岛有障碍区域我方岛礁最短路径的形成,专业.专注..word格式,由假设知，各敏感区域是由以外国侵占岛礁几何中心为圆心半径为12海里的区域，为凸集。若可行区域的边界是光滑曲面。则最短路径必由下列弧组成，它们或者是空间中的自然最短曲线，或者是可行区域的边界弧。而且，组成最短路径的各段弧在连接点

7、处必定相切。上述定理由J.W.Craggs在1973年证明。由于光滑曲线在计算机中不便于存储和处理，本文将敏感区域近似为其内接正多边形（本文中最终使用以12边形近似的数据），并基于上述定理近似推断在障碍区两点之间的最短路径必有以下线段组成，他们或是障碍多边形的边，或是障碍多边形各顶点及起始点之间的合法线段组成，其中合法线段为不与任何障碍多边形相交或在其外部的线段。因此，在上述分析的支持下，试图用计算机解决这个平面简单凸多边形障碍区域最短路径问题首先要解决如何判断平面上点、线段与多边形的位置关系。这是一个基本的计算几何问题，对于线段和多边形位置关

8、系的判定，首先要解决线段与线段之间、点与多边形之间的位置关系判定方法。对于点与多边形，可以利用射线法，即由该点为端点任意引一条射线，若射线与多边形各边