43
软件开发与应用
Software Development And Application
电子技术与软件工程
Electronic Technology & Software Engineering
（2）监控日志设计。系统利用权限机制和不可篡改机制对所有用户登录号、用户名、所操作的设备、操作内容、操作时间、登录和退出系统的时间以及本地监控通信、远程通信、硬件、软件运行等故障情况的详细信息、自动发生故障报警时间和故障处理响应时间、排除时间等信息以监控日志的形式记录在后台数据库的日志表中，以备事后查询。
（3）系统数据备份及恢复。系统利用双机热备份机制对监控系统中所管控的设备及其环境的信息进行异机异盘备份，以防突发故障或误操作导致数据丢失时，能自动恢复到上一次正常断点位置，保证系统的稳定性和安全性。
（4）数据加密。系统采用md5算法对所有传输数据进行加密，并利用鉴权机制对第三方系统的数据进行鉴权和过滤，排除第三方系统数据的影响，保证系统数据的安全性和可靠性。3 结论
（1）首次基于传感网络和TCP/IP 设计了的地铁票务机房环境监控系统的三层体系架构。
（2）利用系统工程思想和传感网络技术，为实现地铁票务机房环境监控系统提供一种新的建模方法，进一步规范了机房环境监控业务流程。
（3）首次利用UML 的用例图和软件工程思想构建了地铁票务机房环境监控系统的逻辑结构模型。
（4）通过以冗余设计采用不同的路径、不同实现方法的模块或系统作为备份，方便出现故障时进行替换，以维持系统的正常运行，保证了系统的可靠性。
（5）与其它类似系统相比，具有高可用性，自动实现负载均衡，运行稳定，预警及时、方式多样、效果更好。
参考文献
[1]慕家骁，王志中，黄建华等.机房环境引起通信电源故障的案
例分析[J].广东通信技术,2020,40(6):72-76.
[2]祝视，欧阳荆.变电站通信机房动力环境集中实时监控典型故
障分析[J].湖南电力,2020,40(2):29-32.
[3]陈焰，王家军，涂静鑫等.浅析机房重要电子设备局部高温监
测报警的重要性[J].机电信息,2019,19(36):67-68.
[4]应辉志.一种核磁共振机房监测系统的设计与实现[J].中国
医疗设备,2020,35(8):105-107+118.
[5]陈川.通信机房视频监控系统的设计与应用[J].电子技术与
软件工程,2016,5(20):56.
[6]孙健琦，来金辉，周佳驰.基层电力企业信息机房动环监控与
运维管理[J].电子技术与软件工程,2019,8(04):238.
[7]阮家余.浅谈通信机房动力与环境监控系统的实现[J].信息
通信,2020,34(12):252-254.
[8]阎旭，张阳.民用航空无人值守机房动力与环境监控系统综述
[J].数码世界,2021,20(2):233-234.
[9]师远哲，李翠翠，任恒怡.雷达机房动力环境监控APP 端的设
计及应用[J].信息记录材料,2020,21(1):103-104.
[10]陶浩.高校数据中心机房设计与实践[J].信息与电脑(理论
版),2019,31(23):214-216.作者简介
黎明（1974-），女，广西壮族自治区梧州市人。注册安全工程师。研究方向为智能交通运输等。
胡滨（1981-）（通讯作者），男，广西壮族自治区贵港市人。高级工程师。研究方向为智能运维与决策等。
1 引言
最短路径算法广泛应用于机器人路径规划、大型游戏寻路、障碍物规避、无人机航迹规划及网络应用中，在实际生活生产中具有重要的作用。针对不同领域、不同条件下该问题的算法研究及设计改进也具
有十分重要的理论价值和现实意义。最短路径问题包含几种形式：第一种是某两个点之间，即确定好起点终点，求起点到终点之间的最短路径；第二种是一张图中，求任意两个点、即所有两点之间的最短距离；第三种是求某个指定点，到所有其余任意一点之间的最短距离。对于这几种问题，目前国内外有各种特定的的算法研究。
对于单源最短路径问题，即求出某个指定点到所有点之间的最短距离，1959年Dijkstra [1]在论文中提出相应的问题及解决算法。
基于A*算法的路径规划仿真平台的设计与实现
杨阳
（湖北职业技术学院  湖北省孝感市  432100）
1962年Floyd [2]在提出了采用动态规划的方法求多源点之间，即图中任意两个点之间最短路径的算法。鉴于Dijkstra 算法在带有负权边的图中不适用，Bellman-Ford 算法（Richard Bellman [3]和Lester Ford 分别提出）则能够更普遍地解决单源最短路径问题。这些算法都有不同的优势、算法复杂度与适用场景，在特定情况下，可以综合各自的优势，实现目标算法效率的提升。2 基础路径规划算法2.1 Floyd算法
Floyd （弗洛伊德）算法也称为插点法，它采用动态规划的方法寻多源点之间最短路径的解法。对于一张加权图，每条边上的权重可以是负值（避免负权回路），通过Floyd 算法可以计算出任
摘　要：本文在讨论分析Floyd 算法、Dijkstra 算法、Bellman-Ford 算法等算法原理的基础上，介绍了A*算法的设计实现，并构建基于A*算法的路径规划仿真平台。实验结果表明，该仿真平台可以实现不同地图规模下A*算法的仿真模拟，采用优先队列作为OPEN 表结构可以有更好的算法效率。
关键词：A*算法；路径规划；仿真平台
软件开发与应用
Software Development And Application
电子技术与软件工程Electronic Technology & Software Engineering
意两个点之间的最短路径。Floyd算法采用公式（1）[4]所示：
（1）在上式中，G为顶点之间的距离矩阵，s为起点，g为终点，i 表示中间点，n为顶点的个数。该表达式的含义是，计算出顶点s、i之间的距离G[s][i]与顶点i、g之间的距离G[i][g]，如果它们的和小于G[s][g]，则更新G[s][g]的值。按该方法循环遍历所有i的取值，发现其中G[s][g]的最小值，从而到起点s与
终点g之间的最短距离。为了描述该算法思想[5]，首先建立路径规划问题中各顶点距离值所对应的初始邻接矩阵A，并定义G(0)=A。
G(1)表示若只以顶点v1为中间点所生成的距离矩阵更新值，G(2)表示若只以顶点v1、v2为中间点所生成的距离矩阵更新值……以此类推，G(k)表示若只以顶点v1、v2、……vk为中间点所生成的距离矩阵更新值。当k=n时，便可求出G(n)的值，即可插入顶点v1、v2、……vn作为中间点生成最终的距离矩阵更新值，从而求出任意两个顶点之间的最短距离。
Floyd算法的伪代码可以表示为：
For k = 1：N
　For i = 1:N
  For j= 1:N
  　IF G(i,k)+ G(k,j) < G(i,j) Then
  　G(i,j) = G(i,k) + G(k,j)
容易看出，Floyd算法时间复杂度是O(N3)，空间复杂度是O(N2)，存在复杂度较高、路径规划时间较长的问题。
2.2 Dijkstra算法
Dijkstra(迪杰斯特拉)算法是基于贪心算法[6]的设计思想，是一种典型的单源最短路径算法，既可以计算一个点到剩余所有点之间的最短距离，也可以用来获得某两个点之间的最短路径。在该算法中，首先将某个顶点V0作为根节点，然后将整个顶点集合分成两个部分，即已计算出到V0的最短距离的顶点的集合V（初始时只有V0）和剩余点集U，U中每个顶点都保存着与V0的最短距离值。在每次迭代中，在U中寻离V0距离最短的顶点加入到V中，并更新U中剩余顶点距离V0的最短距离值（因为V中加入了新的顶点）。直到U集合为空。Dijkstra算法的伪代码可以表示为：Array<T> V, U; Int N；//顶点个数
While(!U.Empty){
　T vertex = FindMinDis[U]；
数据结构与算法论文
　V.Add(vertex);U.Remove(vertex);
　UpdateDis[U];
}
在一般实现下，Dijkstra算法时间复杂度是O(N2)，在优化实现的情况下，算法时间复杂度可达到O(ElogV)，其中，E为边的条数，V为顶点的个数。
2.3 Bellman-Ford算法
Bellman-Ford(贝尔曼-福特)算法是一种求解单源最短路径的算法，相比于Dijkstra算法，它的优点在于能够处理负权边的情况。该算法最多进行|V-1|次“松弛”[7]操作，从而得到从源点到|V-1|个顶点的最短路径。在每次松弛操作中，根据每条边的权值更新源点到顶点的距离值（源点到各顶点的初始化距离是∞）。在所有指定松弛操作结束后，如果增加一次遍历还能产生更新值，则说明存在负权环。该算法的时间复杂度是O(VE)，其中，V代表顶点数，E代表边数，该算法存在改进优化的空间。
2.4 A*算法
A*算法是一种启发式寻路算法。该算法在选择最短路径的下一个顶点时会计算起点到待检测点的距离加上待检测点到终点的估计距离之和作为判断依据，用公式表示为F=G+H。其中，F表示起始点到目标点的距离函数，G表示起始点到待检测点的真实代价值，H是待检测点到目标点的估计代价值。当H=0时，该算法退化成Dijkstra算法[8]。根据A*算法的核心原理，它在Dijkstra算法的基础上，增加了对待检测点的启发式评估，从而筛选了待检测点，加快了生成最短路径的效率。
3 A*算法的设计与实现
3.1 OPEN表和CLOSE表
和Dijkstra算法类似，A*算法也把整个顶点集合分成两个部分，已完成点集（CLOSE表）和待检测点集（OPEN表）。从起点开始，将起点设置为当前点，不断将周围可达点加入到OPEN表中。根据A*算法的基准公式F=G+H，选择这些可达点中F值最小的点作为新的当前点，旧的当前点被加入到CLOSE表中。CLOSE表中的顶
点表示不再需要被关注的点。在算法运行过程当中，可达点加入到
OPEN表后，需要基于当前点更新其
F值，更新成功则设置当前点
图1：A*算法结果图
（1）10*10 线性查表
（3）20*20 线性查表
（2）10*10优先队列
（4）20*20优先队列
44
45
软件开发与应用
Software Development And Application
电子技术与软件工程
Electronic Technology & Software Engineering
作为它的前驱顶点。算法在终点加入到OPEN 表时结束。最后，从终点沿着前驱回溯可以到最短路径。  3.2 启发式函数
A*算法中，每个顶点F 值的计算包括两个部分：G 表示起点到待检测点之间的距离，由于待检测点是当前点的相邻顶点或可达顶点，这个值可以直接计算出来；H 表示待检测点到终点的估计值，也称为启发式函数，该值的计算需要考虑障碍物、移动方向（能否走对角线）、搜索区域的划分等实际场景问题，以及距离计算公式的选择。对于一个棋盘方格区域，距离计算公式可以采用曼哈顿距离，即将水平位移和垂直位移加和作为距离结果。同样，也可以采用对角线距离、欧式距离等。
A*算法的优化主要集中在OPEN 表的设计结构和启发式函数的选择。一般情况下，可以使用顺序查表、优先队列等作为OPEN 表的数据结构；启发式函数则可以选择曼哈顿距离、对角线距离、欧式距离等计算公式。3.3 A*算法实现
如图1所示，在方阵地图中，红方块表示起点，紫方块表示终点，黑方块表示障碍物，绿方块表示路径。在本A*算法路径检测中，会判断周围8个位置是否可以通行，如果某位置没有障碍物，将作为候选路径选择。障碍物采用随机算法生成。
如果采用线性查表作为OPEN 表结构，A*算法每次都需要遍历整个线性查表，寻其中F 值最小的顶点作为新的当前点，继而将该当前点的有效相邻顶点加入到OPEN 表中；并更新这些新加入顶点的F 值，以便下次搜索；
如果采用优先队列作为OPEN 表结构，根据优先队列的性质，具有最高优先级的顶点先出队列，这样避
免了线性查表中全表搜
素的时间消耗，加快了算法的运行速度。
图1展示了地图大小分别为10*10和20*20，OPEN 表结构分别为线性查表和优先队列情况下的运行效果图。
分析图2关于A*算法在不同实现方式下运行时间的统计结果可得：随着地图规模的不断增大，运行时间呈递增趋势；在同规模地图大小的情况下，Open 表结构采用优先队列的运行时间更短。如表1所示。4 结论（Conclusion）
路径规划算法是计算机应用技术实践于机器人寻径和避障、大型游戏寻路、网络路由等场景中的重要算法。本文讨论分析了
Floyd 算法、Dijkstra 算法、Bellman-Ford 算法的基本定义、原理、算法复杂度，详细介绍了A*算法的设计与实现，并构建路径规划仿真平台对A*算法进行验证。实验结果表明：算法运行时间同地图规模及OPEN 表结构相关。随着地图规模的不断增大，运行时间呈递增趋势；在同规模地图大小的情况下，OPEN 表结构采用优先队列的运行速度更快。参考文献
[1]DIJKSTRA E W. A Note on Two Problems in Connexion with
Graphs[J].Numerische Mathematik,1959:269-271.
[2]FLOYD, R W. Algorithm 97, Shortest Path Algorithms[J].
Communications of the ACM, 1962, 5(6):345.
[3]BELLMAN, R. On a routing problem[J]. Quarterly of
Applied Mathematics, 1958, 16(1):87-90.
[4]王靖东.基于优化Floyd 算法的室内机器人路径规划研究[D].
西北农林科技大学,2015.
[5]王荣，江东，韩惠.基于Floyd 方法的最短路径算法优化算法
[J].甘肃科学学报,2012,24(004):110-114.
[6]吴海峰.最短路径算法——Dijkstra 及Floyd 算法[J].中国
新通信,2019,21(02):37-38.
[7]宫恩超，李鲁.基于Bellman-Ford 算法的动态最优路径算
法设计[J].测绘通报,2011(8):26-28.
[8]王维，裴东，冯璋.改进A*算法的移动机器人最短路径规划
[J].计算机应用
,2018,38(05):1523-1526.
作者简介
杨阳（1985-），男，硕士学位。实验师。研究方向为编译技术、机器学习。
表1：A*算法运行时间
Open 表结构地图大小
线性查表(毫秒)
优先队列(毫秒)
10*104320*206250*5074100*100
13
6
图2：A*算法运行时间图

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。