2023年西电数模大作业.pdf

关于中国南海岛礁巡航路线方案的探讨姓名：刘发强学号:2 0 2 3年1 1月8日摘要南海岛礁巡航路线方案的拟定实质上是一个求取平面有障碍区域两点之间最短途径问题和TSP问题的混合针对前者，本文借助ESPO算法的思想, 将外国非法侵占岛礁所拟定的1 2海里敏感区域抽象为正多边形, 在对所有顶点及起始点之间任一条途径的合法性鉴定（ 借助计算几何中点、线段、多边形的位置关系）之后，运 用D i J k s tra算法生成障碍密集区（ 南沙群岛）我方任意两岛礁之间的最短途径，后对我方全体（ 西沙、南沙、 中沙） 岛礁运用Floyd算法生成最短途径完全图的邻接矩阵, 为后续解决奠定基础针对后者, 运用自适应的蚁群算法求取最优解, 经检查效果较好同时借助openCV提供的图像解决和画图函数对算法的运营和结果进行了可视化呈现， 易于理解调试 理论上,本文的解决方案对于这类问题有很广泛的合用性关键词:TSP问题；ESP0算法；D ijk s t r a算法;Floyd算法；openCV;蚁群算法; 算法可视化绪论随着中国海权意识的逐步觉醒和军事力量的日益强大以及美国重返亚太战略的实行， 南海态势在多方的博弈下波瑞云诡，不安定不稳定性极大。

为了维护我国的主权和领土完整，对我国实际控制的岛礁进行周期性的补给和巡航势在必行因此，在周边情况极其复杂的南海拟定一个最优的巡航途径非常关键本文重要借助E SPO算法和蚁群算法对我国南海实际控制的涉及西沙、中沙、部分南沙在内的23个岛礁进行了途径规划，比较圆满的解决了上述问题，且具有良好的可扩展性和合用性本文的基本假设：1、地球表面近似为球面，在经线上，每纬度约111千米， 在纬线上， 每经度约为11 1 *cos千米,其中由于所考察区域（ 纬度从东经1 1 1 °到东经1 1 7° , 北纬8 °到北纬18° ） 面积相对较小且在低纬度，故近似为平面即每经度1 1 1千米 运用百度地图的测距工具和坐标拾取系统得出的结果与对平面上两点欧几里得距离相比最大相对误差低于1% ,这对于本问题的解决足够准确2、岛礁抽象为其几何中心处一点3、本文考察西沙群岛、中沙群岛的所有岛礁和南沙群岛的7个岛礁由于中沙群岛大部分在中部呈一紧凑环装分布，为了简化且不失准确性， 将大环礁抽象为环北一点和环南一点4、本文所规划的途径除不可避免之外不进入外国侵占岛礁所形成的12海里敏感区域，由于东门礁、南薰礁距离鸿麻岛和九章群礁过近，在此两处将1 2 海里放宽为6 海里。

5、由于部分岛礁之间平面欧几里得距离远大于其面积尺度， 故在无障碍区即西沙、中沙我方岛礁的最短距离可以由平面欧几里得距离代替并且最优解中， 可以预见途径穿越岛礁的也许性极小，再次印证上述假定的合理性6、在构造最短途径完全图的过程中， 对于非南沙与非南沙之间、非南沙和南沙之间其距离认定为其平面欧几里得距离， 南沙群岛各岛礁距离运用E SP O 算法生成， 由于南沙距离非南沙相对于其尺度很大， 故近似比较准确方案形成过程南海岛礁经纬度采集和部分岛礁之间的测距借助百度地图及其提供的坐标拾取系统和测距工具，获取了我方2 3 个岛礁、他 方 18个岛礁的经纬度信息和用于连通南沙我方部分岛礁（ 障碍外部）与中南暗沙、大环礁、中建岛、盘石屿等岛礁的距离并 运 用 MATLAB计算了我方非南沙各岛礁之间的欧氏距离，从而生成了一部分最短途径完全图由于表格较大，不在此呈现，详见表格图 错 误 !未定义书签 南海部分岛礁南沙群岛有障碍区域我方岛礁最短途径的形成由假设知, 各敏感区域是由以外国侵占岛礁几何中心为圆心半径为1 2海里的区域，为凸集若可行区域的边界是光滑曲面则最短途径必由下列弧组成，它们或者是空间中的自然最短曲线，或者是可行区域的边界弧。

并且，组成最短途径的各段弧在连接点处必然相切上述定理由J.W. Craggs在1973年证明由于光滑曲线在计算机中不便于存储和解决， 本文将敏感区域近似为其内接正多边形 （ 本文中最终使用以12边形近似的数据），并基于上述定理近似推断在障碍区两点之间的最短途径必有以下线段组成，他们或是障碍多边形的边， 或是障碍多边形各顶点及起始点之间的合法线段组成, 其中合法线段为不与任何障碍多边形相交或在其外部的线段因此， 在上述分析的支持下, 试图用计算机解决这个平面简朴凸多边形障碍区域最短途径问题一方面要解决如何判断平面上点、线段与多边形的位置关系这是一个基本的计算几何问题，对于线段和多边形位置关系的鉴定，一方面要解决线段与线段之间、点与多边形之间的位置关系鉴定方法对于点与多边形，可以运用射线法， 即由该点为端点任意引一条射线, 若射线与多边形各边相交奇数次，则在内部，其 他 在 外 部 （ 在边上也认为在外部）；对于线段与线段之间，可运用正交变换（ 便于解决）将其中一条变换到X轴且一段与原点重合， 进而判断另一条线段与X轴的交点与第一条线段的关系, 若在其上则相交， 否则不想交（ 在本问题中如此判断合适） 。

所以对于线段与多边形， 若线段与多边形任一条边相交， 则线段与多边形相交，否则进而判断线段中点与多边形的位置关系（ 由于多边形凸， 在这种情况下，中点与多边形的位置关系和线段与多边形关系等价），若在外，则在外，反之易得上述算法可以鉴定某条边的合法性， 若不合法， 则距离为无穷大， 否则为欧氏距离在上述算法的支撑下，可以求得所有障碍多边形顶点及起始点互连而成的所有距离再借助D i j kstra算法生成我方7个岛礁的最短途径Di j k str a算法的思想是若从某 点A到连通图上其他点最短途径生成是递增顺序的的， 则到下一点X待生成的最短途径或者是A-一X,或者通过己生成最短途径的点下面是结果呈现, 数据在表格中给出图错误!不能识别的开关参数6边形近似图 5 永暑礁到东门礁三、测量中沙、西沙部分岛礁到南沙7 个岛礁的距离由于中沙、西沙基本被我方控制， 且距离南沙岛礁较远，因此，中沙、西沙到南沙部分岛礁的距离可以用欧氏距离代替, 下面分别测量了从中建岛、盘石屿、中南暗沙、中沙大环礁、黄岩岛到美济礁、渚碧礁、 永暑礁的距离, 用于连通整个赋值图 然后运用F l oyd算法生成最短途径完全图Dist[2 3 ][ 23]和途径中继前驱Pa t hl 2 3][23],其中, Dis t Ei] [j]为岛礁i 与岛礁j 的最短距离，它或是欧氏距离，或 是 ES P 0 算法生成的距离， 或是通过中继获得的最短距离。

Path[i]小表是从岛礁i 到岛礁j最短途径中的中级前驱，假如没有中继则为i借助Pa t h 矩阵可以在生成T S P 途径后提供具体途径信息裳江图错误! 未定义书签用于连通南沙与西沙、中沙的途径一、运用蚁群算法求解dist矩阵的最优TSP解蚁群算法是求解TSP问题的经典算法，是一种元启发式搜索算法， 借助群体智能来实现组合优化但是参数的选取并不容易， 算法陷入局部最优的也许性很大， 影响全局搜索能力 几个重要的参数涉及信息素重要限度指标a Ip h a、可见度（ 距离倒数） 重要限度指标bet a、信息素挥发因子d i sp e rs e fac t o r、蚂蚁数量antnum和蚂蚁圈最大信息素Q 其中alpha=0时，算法退化为贪心算法， b eta= 0 时， 算法退化为随机搜索在实验过程中实验了大量参数，发现蚂蚁数量过多越容易陷入局部最优最终选取 alpha=0. 8,b e ta= 2 , a n t n u m=34, d ispersefact o r= 0 . 5 , 并引入 dispe r sef a ct o r的陷入局部最优的自适应调节机制即di s p e r sefa c tor<=（ d is p e r sefactor * lim i t ）八0 .5 ,该迭代修正将最终使disperse facto r 趋 于 1 im it不至于修正过度，取 lim it为 0 .4。

下面是最优解，为 3235.4 9 千米所有图片都在附件中给出□ X4 antColony 行) -Microsoft Visual Studio文件(F) 姻㈣醺( V )项目( P )生成( B )调试( D)国认(M) I M( T )测激S)分析( N)窗口 (W) »磔 动(Ctrl+Q P - i5 X! 1151195944 -E Application Insights • -IS antColony^ 8： [9052] antColony.exe •'生 即W： •不吧X■ 优 解 开 始 触I 干+ ■ & 泉 H ”一£西沙洲港涵流澳楣港银麻流玉琢障I , ■« 华阳礁永暑礁中南暗沙葭岩g 中i ! 环礁北中沙环礁南浪花礁2 2 0 8升二6 8 工米永兴岛西沙洲银砾滩湛海滩滨湄滩浪花礁玉琢礁甘泉量障渚碧礁美济礁中南暗沙黄岩岛中沙环礁北中沙环礁南东岛8 2 0 8^Hd」 2 4 . 6 8 年米永兴岛西沙洲银砾滩湛涵滩滨湄滩浪花礁玉琢礁甘泉不硅渚碧礁美济礁中南暗沙黄岩岛中沙环礁北中沙环礁南东岛8 2 0 . 8一^ H | | | ： ； 3 2 4 . 6 汗米永兴岛西沙洲银砾滩湛涵滩滨湄滩浪礴玉琢礁甘泉TZ —渚碧礁美济礁巾南暗沙黄岩岛中沙环礁北中沙环礁南东岛B g J S U ^"0 8 2 0 8一 升2 4 . 6 升米永兴岛西沙洲根礁滩湛涵滩滨湄滩浪花礁玉琢礁甘泉渚碧礁美济礁中南暗沙苗岩岛中沙环礁北中沙环礁南东岛MW，,—. 「 H匕 …” 。

在 - 告 人 二 心 粕 — 谑 二垓谯三, 「*二 谯 -: 上 …岸―星， 谑 , T华阳礁美济礁中南暗沙苗岩岛中沙环礁北中沙环礁南东岛- U— 制―， 览 难 夜 舞 送 —二块谯"3 " 谯毡 ' 二建4 苗若谯白堇惶L | I 谯 ：十以礁. X好礁华阳礁美济礁巾南暗沙黄岩岛由沙环礁北中沙环礁南东岛懒 也 8 2 0 . 8彼 段身游音输入法全：▼，Xby e x .*（Win32）己加戮 "C：\ Lny exe"（Win32）:已加载“D *ny exe-（Win32）:己加峨 “D:\Sa 4已退出， 返回值为0 （ O xO ） •c c已退出， 返回值为0（0x0）o6 4已退出， 返回值为0 9x0）西也MM国涌目器圆算国浦博酒»结论本文完满的解决了既定问题， 具有良好的合用性参考文献王万良人 工 智 能 及 其 应 用 （ 第三版）群智能算法及其应用B 1 og：线与多边形位置关系附录（ 源程序）一、Floyd 算法p a th =zero s ( 2 3 ,23);dist=z e ros( 2 3, 23);for i=l ： 2 3for j=l:2 3d i st( i ,j)=ori g ina 1 (i, j);if di s t(i,j)dist( i ,k) + di s t ( k j)di s t( i , j) = di s t( i ,k) + dist(k,j)；pa th (i,j) = p ath(k,j) ;e nden den dEn d二: E S P O 算法含Dijkstra算法、几何鉴定算法、可 视 化 ( 运营平台需要支持opencv)# in c 1 u d e# i n c 1 ude# d e fine pi 3.1415926# define i n fusing n ames p a c e std;cv： :M a t mapaa;c lass p o i n tpublic:o d ouble x, y;◎ string n ame;p o i n t ()° (° x = y = 0；。

｝a p oi n t(do u b 1 e x , doub 1 e y)( th is ->x = x; t his-> y = y;)0Vo i d s e t n a me(string n a me)(t h i s —> n ame = name;)｝ ；c las s Line｛p u b lie:叩oin t st a rt, e n d ；d ouble 1 e ngth ；® L ine() ｝Line (poin t s t art, po i n t e n d ) th i s->s t art = st a r t ;0th i s->e n d = e nd;length = s qrt (( s t a rt.x - e n d . x)* ( s tart, x - e n d ,x) + ( s t a r t. y* ( s t art.y - e nd. y )); v oid setle n g t h ()wl e n g th = sqrt((start. x - en d . x )* (st a rt. x- e nd. x) + (s t ar t .y -— e n d . y));°))；template c l a s s Po 1 yg o n / / w hose m e t h o d s a pp r o priate f or sample co n v(p u blic:i n t e d gen;叩 o in t vertax[e d g e num];4J n e ed g e[ e dge n u m];P o ly g on ()° (— end. y )e nd.y) *(start.yx polygons°)o v o id s etPol y gon(poi n t v er t ax[])oedgen = e d ge n um;of o r (int i = 0; i < e dgen u m; i + +)h is—>ver t ax [i] = vert a x [ i ] ;fb r (int i = 0； i < ed g e num; i++)(。

edge[ i ].st a rt = ver ta x [i];e dg e [i].en d = vert a x [ ( i + 1) % e d gen];o ed g e[i] .s e 11 en g th()；6 )0)int intersect (L i ne 1 inel, L i ne 1 i ne2)6 {oosubtra c t(line 1 .end, line 1 .start);g s u b tra c t(line2.e n d, line 1 .s t art); subtract (line2. s ta r t , line 1.star t ); s u bt r act ( 1 i n e 1. s t a rt, 1 i nel. s tart)； do u ble theta = -ar c t a n(linel. end. x , li ne 1 .end. y); rot a te(li n el.e n d, t h e t a ) ; rotat e (line2.start, t h e ta );r otate( 1 i n e2.en d , th e t a);gif (lin e 2.s t a r t .y*li n e 2. end. y < 0)00 |。

d oubl e x 0 = line2.s t art. x - 1 i ne2. start, y * (line 2 .e n d.x — 1 i ne2.star t .x) / (lin e 2. end.y - 1 i n e 2. s tart, y)； if ((xO -1 i n el.end. x )* x 0 < 0 )g r e t u r n 1 ； if(fabs(xO )< 0 .OOOOO1 || fab s (xO - lin e 1 . end.x) <0 . 000001)8 「e t ur n 2 ;} 吒 1 se if (fab s ( 1 ine2. s tar t . y *line2.e n d .y) < 0 . 0 00001) re t u m 3;oelse return 0 ;0 )p o in t i n t erm e d iate(point pl, po i n t p 2)( po i nt tern p ; t e mp.x = ( p 1. x + p 2 . x ) / 2；t e mp.y = (pl. y + p2.y) / 2 ;®retu r n t emp；)0bo o 1 in t er c onnect(Line lin e )(for (int i = 0 ; i < e dge n ; i++)00 {。

if (line. 1 e n gt h < 0 . 0000 1 )o or e tu r n fal s e;if ( i nte r s e c t(li n e, e d g e[i]) == 1)r e t u rn true；if (inside(interm e d i ate (line.star t , li n e .end)) == fal s e )oooretur n fal s e; e 1 sereturn tru e ；°}ebool i nsid e (point p)( i n t c nt = 0；i n 11 o c k = 0;po i nt au x i ； auxi.x = -500;o o a ux i .y = -3 0 0 ;gLi n e r ay (p, a u xi)；for (in ti = 0 ； i < edgen; i ++)L ine temp = e d ge[i]；“ nt va 1 u e = inte r s e c t(r a y, t emp);i f (fabs (tem p . 1 eng t h) < 0.00001)return f a I s e ;◎ “if (fabs((p.y - t e m p .s t art.y)*(temp. e n d .x - t e m p .st a rt.x ) - (t e m p. e nd.y —temp.start, y ) *(p.x - temp. s t a rt. x )) <= 0. 0 0 001)/ / on th edg e。

r e tur n f a Ise;if (va 1 ue == 1 ||va 1 u e==3) c nt++;e 1 se i f ( v al u e == 2 )(lock == 0)0 0 o| 空nt++;o 1 o ck =1;0 0 } ® e Ise eolock = 0 ;6 0 0 }dlo if ( e n t % 2 = = 1) oret u r n tr u e；“e 1 se ret u m f al s e；)M o ub 1 e arc t an(double x, d o u b le y )Ugif (x == 0 && y == 0) c o u t < < * ' e r r o rM « e ndl;e ls ei f (x > 0) r e tur n ata n (y / x );gels e i f (x == 0)00oo^if (y > 0) retu r n p i /2 ； « > e 1 s e if (y < 0)g return - p i/ 2；6 0 |。

oelse i f (y >= 0) return at a n(y / x) + p i;照1 s e if (y < 0 ) r e t u r n atan (y / x) - p i;)｝ ；v o i d rot a t e (poi n t &p 1 , d ouble the t a)(p o i nt temp = p 1 ;o p 1. x = temp, x cos(t h et a ) — tem p .y*si n (th e ta)；p ] .y = t e mp.y*cos(th e ta) + temp.x*s i n (t h e ta);)void s u btr a ct (po i nt& pl, point p2)(pl. x —= p2.x;叩1. y -= p 2 .y;)t emplateclas s enemypublic：opoint center;double r a d i us;i nt e dg e n;© s tr i ng n ame;p oin t v ert a x[edge n u m ] ;ov o i d s etenemy(point enemy,doubl e r a di u s ,s t r ing name)6 (t h i s・>ce n t e r = e nemy；^this->r a di u s = rad i us;this-> n am e = n a me;。

e d gen = edgen u m;gf o r ( i nt i = 0; i < edge n ; i ++)( overtax [i]. x = ce n ter. x + r adius*co s (2*pi / edgenum* i );v e rt a x[ i ].y = center.y + r a d i us*sin(2*pi / ed g e num * i ) ;6 )°le n emy()()v oi d s e t r a d i u s(double radiu s )(th i s->radi u s = r a dius;gfor (in t i = 0; i < edgen; i++)v ertax[i] .x = ce n ter. x + ra d i u s*cos(2 * p i / edge num * i ) ;g°ver t a x[ i ]. y = c enter.y + r a d i us*sin( 2 * p i / e d g e n um * i)；00 |)v oid d r awarea()( for (int i = 0; i < edgen; i + + )line( mapaa, c v::Point(v e rtax[i].x, v er t ax[i].y), cv： Toi n t ( v e r t ax[(i + 1) %edg e n].x, ver t a x [(i + 1) % edg e n ]. y) , cv： ： Scalar(O 5 2, 2 5, 6 5 ));°)｝ ；d o u b le e u c 1 i dea n _met r ic(p o i n t p 1, poi n t p2)(return sqrt( (pl. x — p2. x)*(pl.x・ p2. x) + (pl.y - p 2 . y )*(pl. y - p2. y ));)v oide s p o (enemy<12>*ene, int e n enum, point china[J,in t chinanum)(P olygon< 1 2> 大 p o ly = new P o lygo n < 1 2 >[ene n u m ];© f o r (int i = 0; i < e n e num； i++)°(p o 1 y[i].s e t Pol y gon(en e [i].verta x );。

e n e[i].draware a ( ) ;°)int ver t axnum = e n enum * ene[0]. e d ge n + c hi n a num;叩oi n t*v e rtax = new poin t [ver t ax n u m ]；f or (int i = 0 ; i < china n um; i ++)v e rtax [i] = china Li];ofo r ( i nt i = 0； i < enenum * e n e [0].edg e n; i ++)overtax [i + chi n an um] = ene[i /e n e [0]. e d gen ] . v ertax[i % en e [ 0 ]. ed gen];d o u b le * * d ist = new d oubl e * [v e rt a xnum]；o f or (i n t i = 0; i < ve r tax n um; i++)( d i st [i] = new do u b 1 e [ver t ax n um]；)fo r ( i n t i = 0; i < v er t axnum； sy s lem (“cls ” ) ， c o ut<< " 已完毕"

{° i f ( j == i)o o o d is t [i][ j ] = inf； oc o n t in u e；0 )»Line temp(ver t a x [i] , vertax[j]);gint 1 ock = 0;of o r (int t = 0; t < e n e num; t ++)0 { if (p o ly [t]. i n t e rco n nect (temp) ==t ru e )alock = 1;br e ak；00 j} i f (lo c k == 1 )® d i s t[i] [j] = d ist [j] [i] = i n f；w > e 1 s e {dist[i] [ j ] = d is t [j][i] = e u c li d e a n_metr i c ( v ertax[i], vertax))for (i n t cn c = 0; c n c < c h in a num; cnc+ + )wint *genera te d = n e w i n t[ v ertaxnum]；g fo r ( i n t i = 0； i < vertaxnum; i++)^generat e d[ i ] = 0;»in t * p re = ne w int[ver t axnum];doub 1 e *mindis t = ne w d o ub 1 e[vert a xnum ];8fo r (int i = 0; i < vertaxnum; i++)° {»gene r a t e d [i] = 0；。

if ( d ist[cnc] [i] < inf) p r e [ i ] = c nc;o o e 1 s e° ° pre[i] = ­ 1 ；g mindist[i] = dis t [cnc] f i ];00 }gmin d ist[cn c ] = 0；oofor ( i nt i = 0 ; i < v e rtaxnum; i + +)0 {“ do u ble min = inf;int t emp = - 1 ； « f or (int j = 0; j < ve r t axnum; j + + )6 {g i f ( g enerated[ j ] == 0 && mindi s t [ j ] < = min)0 min = mind i s t | j ] ;g »t e mp = j;0 00 j00 I g en e r ate d [ t e m p ] = 1;8fo r (int j = 0; j mindis t [temp] + dist [tem p][j])0 (。

8m i nd i s t [ j ] = mindis t [ t emp] + dist[ t emp][ j ] ；° «>pre[ j ] = t emp;06 |a a |00 }^for (int i = cnc+1; i < chinanum； i++)6//cv::Mat m a p pp = ma p aa.cl o ne();i n t pa t hn u m = 0 ;in t * p a th = new int[ver t ax n um];g co u t < < " 从 ”

dfor (int ij = 0; i j < p a th n um; ij++)0 0 0 { c i r c 1 e (ma p a a , cv:： Point ( (in t ) v e rt a x[ p ath[i j ]].x, ( i nt) v e rtax[pat h[ij]].y) , 5, cv:： Scalar(i*10, i , i 12))；g M in e(m a paa, cv::Po i nt (( i nt)vertax L p a t h [ i j]] . x, (int)verta x [p a th[i j ]].y), c v：：Point((i n t) v ertax[path [(ij + 1) % (pa t hnum + 1 )]]. x , (in t )ver t ax[pa t h [(i j + 1) %(p a th n um + 1)]] .y) , cv::Scal a r (i*l 0,45, 25 5 ));)皿 >ostr i n g s t ream os; oos« mi n d i st[ i ] / 800 * 3 9 7.7;^string str= o s . str ( ) ;g“/cv:： imshow("w a 111 u , m apaa);cv:: i mwrite( " 完整. b mp ” ， m 叩 a a ) ;/ / getchar() ;»))«)i n t main()(d ouble length = 3 9 4.8, width = 267. 7 , basel 0 ng = 112. 28» baselati =11.20, rad ius = 44.1 1 , map 1 = 80 0 , ma p h = 5 3 6 ；string o b stac 1 e [] = {" 中业岛" ， " 大现礁" ， " 小现礁" ， " 福禄 礁 " : 鸨麻岛" ，" 九章群礁" ，" 安达礁 " ， " 舶兰礁" ，" 三角礁" ， " 毕生礁" ， " 双黄沙洲" ， " 库归礁" ， " 仁爱 礁 " 仙 娥 礁 " ， " 马欢岛" ， " 五方礁" ，"火艾礁" ，" 蒙 自 礁 " };M oubleen elo n g [] = { 1 14.29,113.8 5,113. 99,113.62, 114.36, 114.43, 11 4.7 1 ,114.58,115 .34, 1 1 3 . 67,11 4 .4 2,1 1 4 .61, 1 15. 86, 11 5 .4 5 , 1 15.86, 1 15.72,1 1 4.90,114.78 ) ；讨 oubleene 1 a t i [j - { 1 1 .03, 1 0. 05, 9 .94, 10.1 8,10. 1 5,9.82,10.30,10.37, 10.18,8.94, 10.64, 10. 81,9.7, 9.3 5 , 1 0 .66,10.47, 1 0 .83,11. 09 };strin g china[] = {"赤瓜礁" ， " 美济礁" , " 永 暑 礁 " ， " 华 阳 礁 "，"南薰礁" ，" 渚碧礁二”东门 礁 " } :doubl e c nl 0 ng[] = { 1 1 4.28,1 1 5. 5 4, 11 2 . 9 6 , 1 12.8 3 ,114. 2 2 , 1 1 4.08,1 14.57 ) ;doub 1 e cnlati[] = { 9 . 6 8 ,9 . 86,9. 59,8.85, 1 0. 17, 1 0.88,9. 9 2 ) ;。

p oint* c hi n = n e w point [ 7 ];e n e my<12> ene a re a [ 1 8J;»ma p a a = cv::im r ead( " 南沙诸岛.p n g");» f o r (i n t i = 0; i < 1 8; i++)o e n e a rea [i].se t e n e my(po i nt( (enelong[i] - bas e lo n g) * 11 1 / 1 e ngt h *ma p 1, (b as e la t i — en e 1 at i [ i ]) 1 1 1 / wi d t h *maph), r adius,ob s ta c le [ i ])； ｝^enear e a[ 4 ].se t r adius (20);enea r e a [5]. se t r a d i us ( 2 0 ) ；o f or (in t i = 0; i < 7; i + +)6 (achin [i].x = (cnl o ng[i] - b a s elo n g) * 111 / 1 e n g th*m apl；。

c h in[i].y = (bas e la t i - cnl a t i[ i ]) * 11 1 / width*maph; c h i n [i], s e t n a me (ch i n a [i])；)o e s p o ( e near e a , 18, chin, 7);)三、蚁群算法含可视化# i n cl u d e #include# i nclu d e# includ e using nam e sp a ce st d ;# de fin e s ize 2 3in t Q = 1000;double Q0 = 100;# d e fine an t num 34do u bl e alph a = 0 . 8 ；do u ble beta = 2；# d e f in eci r 10 0 0 0d o u bl e dispersef a c tor = 0 . 5;#def i ne inf 0 .#define or i ginal 100c v ::Mat b a ck g ro u nd;double d i st [ s i ze][ s i ze];dou b le pherom o n e [ s ize] [si z e ];int pr e [size] [si z e ] ；st r in g island [] = { " 永兴岛“ ， “ 西沙洲“ ， " 银砾滩「 东岛” ，“ 甘泉岛“ ， “ 滨湄滩“ ， “ 湛涵滩“ ， “ 玉琢 礁 二 " 华光礁“ ， “ 盘石屿“ ， “ 中建岛“ ， “ 浪 花 礁 “ 黄岩岛“ ， ” 中沙环礁北“ ， ” 中沙环礁南“中南暗沙” ， ” 永暑礁、 " 华阳礁" ， “ 赤瓜礁“ ， “ 美济礁“ ， “ 东门礁“ ，“ 南 薰 礁 渚 碧 礁 ” } ；dou b le Ion g i t ude[] = { 112.35, 1 1 2 . 25, 112. 2 4,112.73, 111.68, 1 1 2. 4 7,112. 56,112.03,111. 7 1, 1 I 1 .79, 111.2,1 1 2 .52, 1 1 7.76,1 1 4 . 7 1,11 4 .06,11 5 .4 4 , 1 1 2 .96, 1 12.83,1 1 4.28, 1 1 5. 54 , 11 4.57,114. 22,114.08 );d ouble 1 a t i tu d e[] = { 16.84, 1 6 .98, 1 6. 76,16.6 3, 16.5 1,16.3 3, 1 6.4, 1 6.33, 16. 2 2,16 .03,1 5.77, 1 6.03,1 5 .15,16, 0 7,15. 5 1, 1 3.9 4 ,9.5 9 , 8.8 5,9 .68,9. 8 6,9.92, 1 0. 1 7,10.88 );c las s point(public：doubl e x, y;st r i n g n am e ;叩oint ()()v oid set i nfor(st r i ng name, doubl e x , doub 1 e y )。

this-> n ame = name; t h is->x = x ;° this—> y = y;°)} ;point islan [siz e ];c las s Ant(p ubli c :doub 1 e possib i li t y[si z e ] ;«»int cur r ent p os;< » i n t t im e ;®dou b le path 1 ength;o i nt pa t h [size];A nt ()(°)v o id in i t()(gen r rentp o s = r a n d() % s ize;t i me = 0; p athlength = 0; p a th[O] = cu r r en t pos； f o r ( i nt i = 0 ; i < siz e ; i++)p o ssi b il i t y[i] = 0;)®bool haspassed(in t n extpos)6 (for (int i = 0; i < t i me; i+ + )® if ( n ex t p os == p a th[ i ] )g r e tu r n tr u e ;r e t u r n false;°)oint ne x tpo s ()。

{ d o uble p m = 0;of or (int i = 0; i < si z e; i++)® if ( h aspa s sed (i) == false) pm += p os s i b ilit y [i]=po w(phe r omone[ c urr e ntposj[ i ] , alpha)*pow(di s t [ c u r r entpos][i], —beta)； ®else possi b i 1 i t y [i] = 0;o int poss[ s ize];i n t sum = 0 ; f o r (in t i = 0; i < size; i++)° ( p ossib i 1 i ty Ei] /= p m;sum + =poss Li] = (int)( p o s s ibi 1 ity[i] *cir);00 }aim X；int ra nd numr a nd() % s um;o s um = 0 ;f or (int i = 0; i < s ize; i++)(8" u m += p oss[i];“ i f (r a n dnum < sum)。

re t ur n i ;°)An t i = 0; w h ile (ha s pa s s e d(i) = = tr u e)i++;r e tur n i ;)v o id move()(t ime++；in t next= n e x t pos ()；p a t h[tim e ] = n ext;pathl e ng t h += d i s t [curren t p o s ] [ n ext];curre n tpo s = n e xt；oif (t i me == size - 1)° (pathl e ng t h += d is t[next] [ p ath[ 0 ] ];t ime = 0;)obool has g one t hrough(int x, i n t y) for ( i n t i = 0 ； i < t i me; i + +)°( i f (path[i]== x&&path[ (i + l)% s i ze] == y)“ eturn tr u e ;Iretu r n f a Is e ;)｝ ；v o id getpath(int x, int y, int&n u m, i nt path[])(n um = 0;© int index = y;p ath[ 0 ] = y；d oUonum++;in d e x = pr e [x] [in d e x];p a th[ n um] = i nde x ;“ w h ile ( i n d ex!= x);for (i n t i = 0 ; i <= n u m/ 2； i++)的 n t tem p = p a t h [i];p ath [i] = path[num - i];。

叩ath[n u m - i] = t e mp；)c 1 ass antColony(public:oA n t antfantn u m];double o p timal;oin t x;i n t nO;◎ in t op a th [size];i nt cn t ;in t f l a g ；a n tColo n y ()°{)void init()°{wf 1 ag = 0；cn t == 0;^opt i m a 1 = inf; nO = 5;0Voi d f i ndoptimal()°{8d o ubl e mi n = optima 1 ；oofor ( i nt i = 0; i < a ntnum； i++)® ® if (ant[i]. pathl e n g t h < mi n )00 I o m i n = an t [ i ]. pa t h len g th； ® x = i; 6for ( i n t j = 0; j < s ize; j++) pp a t h [j] = ant [x]. p at h [ j ];o fl a g = 0;。

｝i f ( f a b s(mi n - optim a 1) < 0. 0 000 0 1)s f 1 ag++;o p t i mal = min；°)ovoid r un(int n )for ( i n t i = 0; i < n; i ++)°( rou n d (1000);es h ow ()；d r aw();0)0)avoid show() cou t < < optim a 1 < < “ 千 米 " " "® fo r (int i = 0; i < s iz e ; i ++) oc o ut << islan[o p ath[i] ].n a me << n "；c o u t << e n dl;cout « a 1 p ha « " " < < beta « ” “ « di s per s e f a c tor « endl;)void u p date()(^>fo r (int i = 0 ; i < size; i ++)g f or (int j = 0 ； j < s ize； j++)Ob { do u ble d e Ita = 0;fo r (i n t k = 0; k < a ntnum; k++)° {。

g if (a n t[k]. h a s g o n e th ro u gh (i, j) == t r ue) delta += Q / a n t Ek].pa t hie ngth; ^pheromone = phe r omone[i] [j] * disp e r s efactor + d e Ita；0 ))o v oi d u p date f a c tor()e n t = f la g / 1000;gif (c n t> nO + 1) d i s persefa c t o r = 0 .7* po w (dis p er s efa c t o r , 0. 5);®//Q = - Q 0 * (c n t - n O )；00 |®else(d i spersefactor = 0 .8 ；6 } }dvo i d r ound (in t t otal)f o r (i n t i = 0； i < total; i++)00 |f or (int j = 0; j < ant n u m ; j++)0 { e a n t [ j ]. i n it();^for (i n t k = 0; k < s i z e ; k++)0 o |^ant|jj.move();)。

update();up d at e factor()；fi n d o p t imal();° }° }0Vo i d dr a w () {“ nt i ndex[s i z e];^in t n u m = 0；ocv::Mat b a ck = b a c k gro u nd. c lo n e() ;8 f o r (in t i = 0 ; i < siz e ; i++) ge t path( o p ath[i], opath[(i + 1) % size], num, inde x )； f or ( i nt j = 0; j < num; j++)c v:： line(back, cv::Point(islan[in d ex[j + 1] ].x, isla n [ind e x [j + 1 ] ]. y), cv:： Point( i s 1 an [in d e x [j]].x, i slan[inde x (j]].y) , c v ::Scal a r (0, 0, 255));}gcv::im s h ow(u wal 1 ", b a ck)；。

cv:: waitK e y(100);°)) ；v o id in i t()(cout« ” 输入完全图权矩阵" « e ndl;® fo r (int i = 0 ; i < s i z e ; i + + )f o r ( i nt j = 0； j < siz e ; j++)° { ocin » d i s t[ i ]|j]； p h erom o ne [i][j] = original;00 }c o u t « ” 输入生成完全图节点前驱矩阵" < < en d 1;0f o r (int i = 0; i < s i z e ； i++)for (int j = 0； j < size; j + +)g c in » p r e[ i ] [j]; }cout« ” 最优解开始搜索” 《 en d 1；}v o i d drawi s po()(f o r (int i = 0 ； i < size; i++)6 ( c v： :circle (bac k g r o un d , cv:： P o i nt (islan [i]. x , i s lan[i] .y) , 5» cv::S c alar(125, 123,85))；0))i n t main ()(backgro u n d = cv::imread(Hb a ck.pngM);^dou b 1 e h i g h t =111 * 10, w i d th =111*7, maph = 5 5 0 , m a pw = 330, b as e 1 ong = 111., baselati = 1 8 ；o f or (int i = 0; i < s i ze; i++)。

i s lan[i] .setinfor(is 1 an d [i], (longitud e [i] — bas e lo n g )* 1 1 1 / high t a ph, (base 1 a t i - 1 a t itu d e [i]) * 111 / w i d t h * m a pw);init ();drawispo() ;^srand((unsi g n ed)(time(0)))；antColo n y a c;ac.init();ac. r un (10 0 );oge t ch a r();®get c har();}。