西电数模大作业.doc

--------------------------校验:_____________-----------------------日期:_____________西电数模大作业关于中国南海岛礁巡航路线方案的探讨姓名:刘发强学号:140201990442016年11月8日摘要南海岛礁巡航路线方案的确定实质上是一个求取平面有障碍区域两点之间最短路径问题和TSP问题的混合。针对前者,本文借助ESPO算法的思想,将外国非法侵占岛礁所确定的12海里敏感区域抽象为正多边形,在对所有顶点及起始点之间任一条路径的合法性判定(借助计算几何中点、线段、多边形的位置关系)之后,利用Dijkstra算法生成障碍密集区(南沙群岛)我方任意两岛礁之间的最短路径,后对我方全体(西沙、南沙、中沙)岛礁利用Floyd算法生成最短路径完全图的邻接矩阵,为后续处理奠定基础。针对后者,利用自适应的蚁群算法求取最优解,经检验效果较好。同时借助openCV提供的图像处理和画图函数对算法的运行和结果进行了可视化呈现,易于理解调试。理论上,本文的解决方案对于这类问题有很广泛的适用性。关键词:TSP问题;ESPO算法;Dijkstra算法;Floyd算法;openCV;蚁群算法;算法可视化绪论随着中国海权意识的逐步觉醒和军事力量的日益强大以及美国重返亚太战略的实施,南海态势在多方的博弈下波谲云诡,不安定不稳定性极大。为了维护我国的主权和领土完整,对我国实际控制的岛礁进行周期性的补给和巡航势在必行。因此,在周围情况极其复杂的南海确定一个最优的巡航路径非常关键。本文主要借助ESPO算法和蚁群算法对我国南海实际控制的包括西沙、中沙、部分南沙在内的23个岛礁进行了路径规划,比较圆满的解决了上述问题,且具有良好的可扩展性和适用性。本文的基本假设:地球表面近似为球面,在经线上,每纬度约111千米,在纬线上,每经度约为111*cos千米,其中为纬度。由于所考查区域(纬度从东经111°到东经117°,北纬8°到北纬18°)面积相对较小且在低纬度,故近似为平面即每经度111千米。利用百度地图的测距工具和坐标拾取系统得出的结果与对平面上两点欧几里得距离相比最大相对误差低于1%,这对于本问题的解决足够准确。岛礁抽象为其几何中心处一点。本文考察西沙群岛、中沙群岛的所有岛礁和南沙群岛的7个岛礁。由于中沙群岛大部分在中部呈一紧凑环装分布,为了简化且不失准确性,将大环礁抽象为环北一点和环南一点。本文所规划的路径除不可避免之外不进入外国侵占岛礁所形成的12海里敏感区域,由于东门礁、南薰礁距离鸿庥岛和九章群礁过近,在此两处将12海里放宽为6海里。由于部分岛礁之间平面欧几里得距离远大于其面积尺度,故在无障碍区即西沙、中沙我方岛礁的最短距离可以由平面欧几里得距离代替。并且最优解中,可以预见路径穿越岛礁的可能性极小,再次印证上述假定的合理性。在构造最短路径完全图的过程中,对于非南沙与非南沙之间、非南沙和南沙之间其距离认定为其平面欧几里得距离,南沙群岛各岛礁距离利用ESPO算法生成,由于南沙距离非南沙相对于其尺度很大,故近似比较准确。方案形成过程南海岛礁经纬度采集和部分岛礁之间的测距借助百度地图及其提供的坐标拾取系统和测距工具,获取了我方23个岛礁、他方18个岛礁的经纬度信息和用于连通南沙我方部分岛礁(障碍外部)与中南暗沙、大环礁、中建岛、盘石屿等岛礁的距离。并利用MATLAB计算了我方非南沙各岛礁之间的欧氏距离,从而生成了一部分最短路径完全图。由于表格较大,不在此呈现,详见表格。图1南海部分岛礁南沙群岛有障碍区域我方岛礁最短路径的形成图26边形近似图312边形近似图4南沙所有最短路径图5永暑礁到东门礁三、测量中沙、西沙部分岛礁到南沙7个岛礁的距离由于中沙、西沙基本被我方控制,且距离南沙岛礁较远,因此,中沙、西沙到南沙部分岛礁的距离可以用欧氏距离代替,下面分别测量了从中建岛、盘石屿、中南暗沙、中沙大环礁、黄岩岛到美济礁、渚碧礁、永暑礁的距离,用于连通整个赋值图。然后利用Floyd算法生成最短路径完全图Dist[23][23]和路径中继前驱Path[23][23],其中,Dist[i][j]为岛礁i与岛礁j的最短距离,它或是欧氏距离,或是ESPO算法生成的距离,或是经过中继获得的最短距离。Path[i][j]表是从岛礁i到岛礁j最短路径中的中级前驱,如果没有中继则为i。借助Path矩阵可以在生成TSP路径后提供详细路径信息。图5用于连通南沙与西沙、中沙的路径利用蚁群算法求解dist矩阵的最优TSP解结论本文完满的解决了既定问题,具有良好的适用性。