• 基于prim算法的网络最小生成树生成得到路径规划


    目录

    一、理论基础

    二、核心程序

    三、测试结果


    一、理论基础

           Prim算法是一种求解最小生成树问题的贪心算法。它的基本思想是,从某一个顶点开始,逐步增加边,每次选择当前生成树与外界顶点之间权值最小的边,直至所有的顶点都被包含在生成树内。

           在Prim算法中,我们首先任选一个顶点作为起始点,然后逐步添加边,使得新的边连接已在生成树中的顶点和未在生成树中的顶点,并且这条边的权值是当前所有这样的边中最小的。在每一步中,我们都需要更新已连接顶点的集合和未连接顶点的集合。

    Prim算法的具体步骤如下:

    1. 初始化:从图中选择一个顶点加入到最小生成树中。
    2. 重复以下步骤直到所有的顶点都加入到最小生成树中:
      a. 在所有连接已在生成树中的顶点和未在生成树中的顶点的边中,选择权值最小的边。如果有多个权值相同的边,可以选择任意一个。
      b. 将这条边的另一端点加入到最小生成树中。
    3. 结束后,已经生成的树就是图的最小生成树。

            Prim算法的时间复杂度是O(ElogE),其中E是边的数量。如果使用二叉堆作为优先队列,时间复杂度可以降低到O(ElogV),其中V是顶点的数量。

            Prim算法的核心思想是利用贪心的策略,逐步构造出最小生成树。由于每次选择的边是当前权值最小的,因此可以保证最终得到的生成树的权值是最小的。

            至于Prim算法在网络路径规划中的应用,它主要可以用于构建最小代价的网络拓扑结构。例如,在通信网络中,我们可以利用Prim算法构建一棵最小代价的生成树,使得任意两个节点之间的通信代价最小。在物联网中,我们可以利用Prim算法构建一棵最小能耗的生成树,使得所有设备在通信时的总能耗最小。

            Prim算法的核心公式是:对于任意一个在生成树中的顶点集合U和不在生成树中的顶点集合V,连接U和V的所有边的权值最小的那条边,其权值一定是最小生成树的一部分。这个公式的证明可以使用反证法:如果这条边的权值不是最小的,那么我们可以找到另一条权值更小的边来替换它,从而得到一个更小的生成树,这与我们的假设矛盾。因此,这条边的权值一定是最小生成树的一部分。

           普里姆算法(Prim算法),图论中的一种算法,可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中,不但包括了连通图里的所有顶点(英语:Vertex (graph theory)),且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克(英语:Vojtěch Jarník)发现;并在1957年由美国计算机科学家罗伯特·普里姆(英语:Robert C. Prim)独立发现;1959年,艾兹格·迪科斯彻再次发现了该算法。因此,在某些场合,普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆-亚尔尼克算法。

    1).输入:一个加权连通图,其中顶点集合为V,边集合为E;

    2).初始化:Vnew = {x},其中x为集合V中的任一节点(起始点),Enew = {},为空;

    3).重复下列操作,直到Vnew = V:

    a.在集合E中选取权值最小的边,其中u为集合Vnew中的元素,而v不在Vnew集合当中,并且v∈V(如果存在有多条满足前述条件即具有相同权值的边,则可任意选取其中之一);

    b.将v加入集合Vnew中,将边加入集合Enew中;

    4).输出:使用集合Vnew和Enew来描述所得到的最小生成树

    然后将这个整体算法流程图中各个核心步骤的过程进行介绍:

    1.根据节点权值进行排序和分类

          根据算法步骤,可以得到最终的各个节点的权值,权值越大,需要充电的节点数量则越大,然后在进行分类的时候,需要综合考虑各个区域的节点的权值,避免某一区域节点权值过大或者过小。这里,选择的是均匀划分方式,即每个MC,对应的节点数量相同,当然也可以其他划分方式,不同的方式得到不同的结果。

    2.计算节点权值和节点距离的加权矩阵

            这里考虑两个因素,一个是距离因素,即节点坐标因素,一个是通过前面几个步骤算法得到的节点权值因素,我们通过这两个因素进行计算最优路径规划。采用距离因素和节点权值因素。其中距离矩阵d,其计算方式为:

           然后节点权值则根据前面的几个步骤算法得到W,然后根据距离因素和节点权值因素,得到一个加权的矩阵,即: 

    二、核心程序

    1. .................................................
    2. %%
    3. %社团划分
    4. %社团划分
    5. %社团划分
    6. %社团划分
    7. V0_set = (0.9+0.1*rand)*ones(1,CNUM);
    8. K_set = (0.09+0.01*rand)*ones(1,CNUM);
    9. Eall = 0;
    10. for cij = 1:CNUM
    11. if cij == 1
    12. Eall0=0;
    13. else
    14. Eall0=Eall;
    15. end
    16. %初始速度
    17. V0 = V0_set(cij);%
    18. %变速度系数
    19. K = K_set(cij);%
    20. %总能量
    21. Ec = 100;
    22. %随机的剩余能量,每个节点不一样,剩余能量的计算,需要根据多个车辆进行计算
    23. ei = 10+10*rand(1,N);
    24. %算法一所得的社团表
    25. Cj1;
    26. %各个社团表的中心点
    27. Xc1;
    28. Yc1;
    29. %能量级数ε的近似能量
    30. pa = 8*rand(1,N);
    31. Cj = Cj1;
    32. Tl = 200;
    33. Ei = ei/CNUM;
    34. ind = 0;
    35. %不同车的位置
    36. Xmc = [];
    37. Ymc = [];
    38. theta = 45/180*pi;
    39. %初始最优路径
    40. Nl= length(Xc1);
    41. a = 0.6;
    42. t0= 10;
    43. tf= 0.001;
    44. xx= Xc1;
    45. yy= Yc1;
    46. figure(2);
    47. for j = 1:length(C)
    48. tmp = C{j,1};
    49. X0 = Xo(tmp);
    50. Y0 = Yo(tmp);
    51. plot(X0,Y0,colors{j});
    52. hold on
    53. Xc(j)= mean(X0);
    54. Yc(j)= mean(Y0);
    55. for i = 1:length(tmp)
    56. dist(i) = sqrt((Xc(j)-X0(i))^2 + (Yc(j)-Y0(i))^2);
    57. end
    58. plot2(Xc(j),Yc(j),max(dist));
    59. hold on
    60. end
    61. plot(Xc,Yc,'rs','LineWidth',2,'MarkerEdgeColor','b','MarkerFaceColor','y','MarkerSize',10)
    62. hold on
    63. xx1 = [xx,xx(1)];
    64. yy1 = [yy,yy(1)];
    65. for i=1:Nl
    66. for j=1:Nl
    67. if i==j
    68. continue;
    69. end
    70. d(i,j)=sqrt((xx(i)-xx(j)).^2+(yy(i)-yy(j)).^2);
    71. end
    72. end
    73. gen=1;
    74. while gen<=5
    75. gen
    76. [f,T]=func_trp(a,d,t0,tf);
    77. opfs(gen) = f;
    78. paths(gen,:) = T;
    79. gen = gen+1;
    80. end
    81. for i=1:Nl
    82. xx2(i)=xx(T(i));
    83. yy2(i)=yy(T(i));
    84. end
    85. xx2(Nl+1)=xx(1);
    86. yy2(Nl+1)=yy(1);
    87. hold on
    88. plot(xx2,yy2);
    89. title('社团划分前的初始路径规划');
    90. %线路进行插值获得不同时刻MC的位置
    91. dall = 0;
    92. %模拟变速度
    93. for i = 1:length(xx2)-1;
    94. Va = V0 + K*randn;
    95. dall = sqrt((xx2(i)-xx2(i+1))^2 + (yy2(i)-yy2(i+1))^2);
    96. SCALE(i) = dall/Va;
    97. end
    98. %插值,用来模拟路径点坐标
    99. Xlp0=[];
    100. Ylp0=[];
    101. for i = 1:length(xx2)-1;
    102. Xlp0=[Xlp0,[xx2(i):(xx2(i+1)-xx2(i))/SCALE(i):xx2(i+1)]];
    103. Ylp0=[Ylp0,[yy2(i):(yy2(i+1)-yy2(i))/SCALE(i):yy2(i+1)]];
    104. end
    105. tk = 0.1;
    106. Tt = tk:tk:length(Xlp0)*tk;
    107. Esave = zeros(length(Tt),N);
    108. Cj2 = zeros(length(Tt),length(C));
    109. %根据路径进行mc移动,然后进行社团划分
    110. %根据路径进行mc移动,然后进行社团划分
    111. for t = Tt
    112. ind = ind+1;
    113. rng(ind);
    114. %mc移动
    115. Xmc(ind) = Xlp0(ind);
    116. Ymc(ind) = Ylp0(ind);
    117. %根据mc位置,对路过的社团进行充电
    118. ischarge = zeros(1,length(Cj));
    119. for j=1:length(Cj)%依次计算每个社团
    120. tmp = C{j,1};
    121. X0s = Xo(tmp);%社团中各个点的坐标
    122. Y0s = Yo(tmp);
    123. %计算社团的中心点,覆盖范围
    124. Xc = mean(X0s);
    125. Yc = mean(Y0s);
    126. for j2 = 1:length(tmp)
    127. dr(j2) = sqrt((Xc - X0s(j2))^2 + (Yc - Y0s(j2))^2);
    128. end
    129. Rr = max(dr);
    130. Rl = sqrt((Xc - Xmc(ind))^2 + (Yc - Ymc(ind))^2);
    131. if Rl <= Rr%进入某个社团
    132. ischarge(j) = 1;
    133. else
    134. ischarge(j) = 0;
    135. end
    136. end
    137. for j=1:length(ischarge)
    138. if ischarge(j) == 1%进行充电
    139. tmp = C{j,1};
    140. X0s = Xo(tmp);%社团中各个点的坐标
    141. Y0s = Yo(tmp);
    142. Xc = mean(X0s);
    143. Yc = mean(Y0s);
    144. for j2 = 1:length(tmp)
    145. if t == 1
    146. Ei(tmp(j2)) = ei(tmp(j2))/CNUM;
    147. else
    148. %计算距离
    149. dst = sqrt((X0s(j2)-Xc)^2 + (Y0s(j2)-Yc)^2);
    150. lvel= floor(dst/100)+1;
    151. Ei(tmp(j2)) = Ei(tmp(j2)) + pa(tmp(j2))*(1+0.5)^(-lvel)*tk;
    152. if Ei(tmp(j2)) >= Ec/CNUM
    153. Ei(tmp(j2)) = Ec/CNUM;
    154. end
    155. %容量限制
    156. if Ei(tmp(j2)) >= Ecap
    157. Ei(tmp(j2)) = Ecap;
    158. end
    159. end
    160. end
    161. else%不充电
    162. for j2 = 1:length(tmp)
    163. Ei(tmp(j2)) = Ei(tmp(j2));
    164. end
    165. end
    166. end
    167. %PN分类
    168. Xpc=[];
    169. Ypc=[];
    170. for j=1:length(C)
    171. tmp = C{j,1};
    172. X0s = Xo(tmp);%社团中各个点的坐标
    173. Y0s = Yo(tmp);
    174. %计算社团总能量
    175. Eall = Eall0 + sum(Ei(tmp));
    176. if Eall/(Ec*length(tmp)) >= 0.9
    177. Cj2(ind,j) = 1;%P
    178. %P型社团的中心
    179. Xpc=[Xpc,mean(X0s)];
    180. Ypc=[Ypc,mean(Y0s)];
    181. else
    182. Cj2(ind,j) = 0;%N
    183. end
    184. end
    185. Esave(ind,:) = Ei;
    186. %将P型社团的中心视为其停留点参与算法四的路线制定
    187. Xp{ind} = [Xpc];
    188. Yp{ind} = [Ypc];
    189. end
    190. %获得最终划分结果
    191. Cpn0 = sum(Cj2);
    192. Cpn = zeros(size(Cpn0));
    193. inx = find(Cpn0>0);
    194. Cpn(inx) = 1;
    195. Cpn
    196. %显示划分结果
    197. figure(3);
    198. for j = 1:length(Cj)
    199. tmp = Cj{j,1};
    200. X0 = Xo(tmp);
    201. Y0 = Yo(tmp);
    202. plot(X0,Y0,colors{j});
    203. hold on
    204. Xc(j)= mean(X0);
    205. Yc(j)= mean(Y0);
    206. for i = 1:length(tmp)
    207. dist(i) = sqrt((Xc(j)-X0(i))^2 + (Yc(j)-Y0(i))^2);
    208. end
    209. if Cpn(j) == 1
    210. plot3(Xc(j),Yc(j),max(dist));
    211. else
    212. plot4(Xc(j),Yc(j),max(dist));
    213. end
    214. hold on
    215. end
    216. plot(Xc,Yc,'rs','LineWidth',2,'MarkerEdgeColor','b','MarkerFaceColor','y','MarkerSize',10)
    217. title('社团划分结果(Red:P;Black:N),Yellow:P&N中心点');
    218. Xmc_set{cij} = Xmc;
    219. Ymc_set{cij} = Ymc;
    220. Esave_set{cij} = Esave;
    221. end
    222. Cpn_set = Cpn;
    223. ..............................................

    三、测试结果

    A26-08 

  • 相关阅读:
    浅谈前端开发模式和url的hash模式以及html5的history模式
    令人抓马的Airtest报错:int object is not iterable
    包装类详解(装箱(包)、拆箱(包)、Integer类型缓存)
    Elasticsearch 部署学习
    【鸿蒙开发】第十七章 Web组件(一)
    wpf prism左侧抽屉式菜单
    【数模/评价模型】层次分析
    前端开发面试-css篇
    python中的变量的定义和使用
    一名双非程序媛面试蚂蚁、美团、携程等大厂拿 offer 分享面试过程
  • 原文地址:https://blog.csdn.net/ccsss22/article/details/127781275