Improving path planning efficiency for underwater gravity-aided navigation based on a new depth sorting fast search algorithm

This study focuses on the improvement of path planning efficiency for underwater gravity-aided navigation.Firstly,a Depth Sorting Fast Search(DSFS)algorithm was proposed to improve the planning speed of the Quick Rapidly-exploring Random Trees*(Q-RRT*)algorithm.A cost inequality relationship between an ancestor and its descendants was derived,and the ancestors were filtered accordingly.Secondly,the underwater gravity-aided navigation path planning system was designed based on the DSFS algorithm,taking into account the fitness,safety,and asymptotic optimality of the routes,according to the gravity suitability distribution of the navigation space.Finally,experimental comparisons of the computing performance of the ChooseParent procedure,the Rewire procedure,and the combination of the two procedures for Q-RRT*and DSFS were conducted under the same planning environment and parameter conditions,respectively.The results showed that the computational efficiency of the DSFS algorithm was improved by about 1.2 times compared with the Q-RRT*algorithm while ensuring correct computational results.

基于DFS与蚁群算法的电弧增材复合路径规划算法优化

为提高电弧增材制造的成形效率,分析了目前路径规划算法的优缺点,提出了基于深度优先搜索(DFS)算法与蚁群算法相结合的复合路径规划优化方法。在zigzag扫描与轮廓偏置相结合的复合路径规划算法的基础上,采用多种不同扫描倾角的zigzag路径算法对多孔洞截面轮廓进行填充,并通过深度优先搜索算法进行zigzag扫描路径分区进行连接,以减少zigzag扫描路径的路径条数和起弧熄弧次数,然后采用蚁群算法搜索路径规划顺序和起弧熄弧点的优化组合,使填充路径的总空行程长度最小。仿真结果表明,DFS分区连接算法对不同扫描倾角的zigzag路径规划皆能起到良好连接作用,采用蚁群算法的电弧增材制造路径规划方法可以有效减少扫描空行程长度。

采用DFS策略的进路搜索算法研究

给出并描述计算机联锁软件中站场型数据结构的形式。介绍采用深度优先搜索策略进行进路搜索的算法并给出该算法所涉及的对象,同时详细阐述对进路搜索过程以及需要完成的任务。采用这种数据结构及算法有利于联锁程序的标准化和模块化,有利于提高系统的可靠性和安全性。

基于启发式NDFS的模型检测新算法

以带有多个可接受条件的广义Büchi自动机为研究对象,提出基于启发式NDFS的模型检测新算法.该算法结合on-the-fly算法与启发式NDFS算法,能较快地判断出广义Büchi自动机非空性,通过理论证明和实验验证了算法的正确性和可行性.与已有算法相比,在广义Büchi自动机非空的情况下,该算法减少了系统状态空间的搜索,提高了检测效率,且能形成相应反例,为缓解形式化验证中的状态空间爆炸问题提供了有效的解决途径,为安全苛求系统的安全性保障提供了有力支撑,丰富了基于模型的软件形式化开发方法.

基于DFS的工程图多层次图块信息提取

针对工程图信息提取过程中的图块多层次引用问题,利用深度优先搜索算法对引用图块信息进行提取。建立图块多层次引用关系,介绍节点深度定义、目标节点判定方法及引用图块搜索策略,设计多层次引用路径搜索算法,并开发应用程序模块,实现多层次引用图块的信息提取。应用结果表明,该方法的提取准确率较高。

基于DFS的图的双向连通性研究

提出了一个基于DFS的图双向连通性研究的简单算法,本算法具有容易理解、形式规范的特点,无论用于教学还是解决实际问题,都有较大的实用价值。

基于改进DFS的联锁仿真教学系统的设计与实现

针对联锁系统进路搜索效率低下的问题,分析了广度优先、A*等搜索算法的局限性,提出了一种带有约束条件的深度优先搜索(DFS)进路搜索算法,搭建站场型拓扑网络,动态创建二叉树模型,设计改进DFS进路搜索算法的程序流程。从教学角度提出软件设计方案,以Visual Studio 2010为平台进行软件开发,实现CTCS-3级列控系统中的联锁仿真教学系统,该系统不但具备良好的可操作性,还集成故障设置、通信数据包查询等功能。

基于MDFF与ISSA的滚动轴承故障声发射诊断

针对滚动轴承早期、复合故障难以准确诊断与智能诊断模型超参数确定严重依赖专家先验知识问题,提出一种基于多维深度特征融合(multi-dimensional depth feature fusion, MDFF)与改进麻雀搜索算法(improved sparrow search algorithm, ISSA)的滚动轴承故障声发射诊断方法。用一维卷积与线性瓶颈反向残差二维卷积神经网络构建多输入卷积神经网络(convolution neural network, CNN)结构的诊断模型,模型输入为滚动轴承声发射信号及其小波时频图,提出基于布伦纳梯度和信噪比的质量指标,在108种小波基中筛选出最佳时频图以提升输入数据质量。接着,采用特征金字塔网络将模型的一、二维低层与高层特征融合,建立深度融合的诊断模型。然后,将交叉混沌映射、自适应权重及融合的随机游走策略引入麻雀搜索算法中,以自适应获取MDFFCNN最优超参数。试验表明,对比近期多个主流智能诊断算法,所提方法可避免人工选择诊断模型超参数,对滚动轴承早期尤其复合故障具有更高的诊断精度和稳定性,模型诊断过程的智能化水平得到了进一步提高。

基于CDFG的SoC验证方法及其分割与搜索算法

随着芯片复杂度以及市场对集成电路上市时间要求的不断提高,对SoC设计方法和验证方法带来了巨大的挑战。控制数据流图可用于系统建模、软硬件功能划分、系统综合与验证等多个环节。该文针对SoC验证的需要,利用CDFG,研究了基于CDFG的验证体系,给出了CDFG的几种定义,讨论了CDFG的表示方法,提出了基于CDFG的验证流程,研究了基于DFS的生成树算法、CDFG的分割算法和CDFG的搜索算法,并以实例说明了这些算法在验证流程中的作用。

基于改进A^(*)算法的机器人全覆盖衔接路径规划

为解决A*算法在规划衔接路径时转角多、路径不平滑、深度优先搜索(DFS)算法规划衔接顺序的随机性和距离较大的问题,提出改进邻域扩展A*算法和经预处理的DFS算法结合的衔接路径规划方法。首先,对A*算法搜索范围扩展至24邻域,经二次数量优化后得到最终邻域搜索节点。其次,设计具有双层位置导向信息的评价函数,对DFS添加节点预处理的步骤。实验结果表明:所提改进A*算法在路径长度、搜索节点数量、规划时间上均优于传统A*算法,且与改进DFS算法结合所得衔接路径表现更优。

改进遗传-狼群对节点序寻优的贝叶斯网络结构算法

贝叶斯网络是数据挖掘领域的一种重要方法。针对贝叶斯网络结构学习算法寻优效率低和易陷入局部最优的问题,提出一种基于改进的混合遗传-狼群对节点序寻优的贝叶斯网络结构学习算法。该算法首先利用深度优先搜索对最大支撑树的节点进行拓扑排序;然后利用动态变异及最优交叉算子构建适用于节点序寻优的改进捕食行为,引入动态参数因子来增强算法局部寻优能力;最后与K2算法结合得到最优的贝叶斯网络结构。用3种不同大小的标准网络数据集中进行实验,结果表明,该算法收敛到较优值,寻优效率高于其它同类优化算法。

通信网络连通性分析方法比较研究

通信系统作为生命线系统的重要组成部分,在国民经济生活和震后抢险救灾中发挥着关键作用,但是其震后功能评估的研究才处于起步阶段。本文首先研究了通信网络的拓扑规则,并基于此给出了建立通信网络图模型的方法;然后,以抗震设防烈度为7度的两个不同规模城市为研究对象,以计算时间和收敛速度为指标,比较研究了Warshall算法、深度优先搜索算法和宽度优先搜索算法对通信网络连通性分析的适用性。分析结果表明:三种方法均能够准确评估通信网络各节点间的连通状态,但宽度优先搜索算法在计算耗时上优于另外两种算法,且网络越复杂以及模拟次数越多优势越明显,最适用于通信网络的连通性分析。

改进SSA-LSSVM模型在埋地管道点蚀深度预测中的应用

埋地管道点蚀深度受土壤环境、运输物质、管道材质等多种因素的影响,因此腐蚀数据存在不稳定性,会导致精确预测其点蚀深度存在较大难度,故提出RS结合MSSA-LSSVM预测模型。首先利用RS对腐蚀影响因素实现降维,提取关键影响因素;其次融合三步改进策略解决麻雀搜索算法已陷入局部最优等问题,利用时间复杂度分析对算法改进后性能进行验证;然后利用MSSA求解出LSSVM中核函数参数σ2和惩罚因子C的最优解,同时选取RBF核函数,使其预测性能达到最优,最终构建RS-MSSA-LSSVM的埋地管道点蚀深度预测模型。结果表明:优化后模型精度得到了极大的提升,且均优于其他模型,证明该模型鲁棒性较好。

铁路车站咽喉区道岔自动分组方法研究

咽喉区道岔分组不仅是运用利用率计算法查定铁路车站咽喉通过能力的必要步骤,还是车站进路选择、股道运用等行车技术作业的关键环节。为解决当前自动分组方法不能有效解决复杂咽喉区非水平方向布置道岔的分组问题,将咽喉区道岔分组问题抽象为有向图中点的归属问题,构建咽喉有向图模型和道岔分组有向图模型,设计二阶段法对模型求解。第一阶段识别平行进路,目标是基于咽喉有向图运用DFS算法识别并生成平行进路对全集;第二阶段为判断道岔归属,目标是基于进路判断法及道岔坐标设计初分、调整、检验等计算步骤判断道岔归属并生成道岔组。以某个布置复杂的技术站咽喉为例,对本文所提出方法进行检验,结果表明该方法能够快速准确地实现咽喉道岔自动分组,有利于铁路数字化设计和智能化生产管理。

基于图数据库和图算法的转供电方案在配电网智能操作票系统的研究和应用

在智能操作票系统的研发中,调电操作票的设计需要对配网故障或者检修的停电范围及线路转供路径进行评估,考虑到电网超大规模的实际因素,常规的关系型数据库难以支撑电网的实时划分和转供电方案的决策。为解决这个问题,通过结合Dijkstra、深/广度优先搜索等图论算法,提出了一种基于图数据库的大规模电网故障影响区域划分和转供电决策方案,实现了调电过程中的最优路径规划,并将其应用在调电操作票的设计当中,实现开票快、准的设计要求。该方案除了应用在操作票系统当中,还可以应用到其他场景中,如电网因故障或检修需要调电时,可以直接给出最优调电方案供调控员使用,能够节省电网调度的经济成本,降低电力传输过程中的电能损耗,避免人为因素导致的电力调度决策失误问题,与目前我国电力行业的“碳中和”目标相符合。为超大规模电网转供电方案的自动规划和选择提供了一种可行的参考案例。

基于航班环的机组排班优化

机组排班计划是航空公司运营管理计划的重要组成部分,因其NP-hard特性常面临组合爆炸而难以求解。针对这一问题,提出一种基于航班环的优化模型。在第一阶段考虑执勤时空衔接约束与执勤始发终到约束,构建了航班间的航班环模型;在第二阶段设计了结合改进的深度优先搜索算法(depth-first search,DFS)以及贪心算法完成对模型的求解。此外,提出了列生成算法下受限主问题模型(restricted master problem model,RMP),并运用该模型完成实验验证算例的求解。

基于深度优先的铁路站场图遍历算法研究

对车站站场图的遍历大多是通过将站场中各个设备的连接方式转换成站场拓扑模型,并将车站设备抽象分为图中节点存储。这样进路的搜索问题就转换成了在图中搜索路径的问题。本文以计算机图论为基础,建立基于铁路站场结构的拓扑模型,结合站场实际情况与图的深度优先搜索算法思路,提出一种基于邻接矩阵的连续遍历站场的算法,提高了遍历效率。

保护通信专网路由自动规划平台

电网的继电保护业务需要满足“双通道三路由”,其中第三条路由是承载在保护通信专网上的迂回路由,根据传输网的网络拓扑进行规划。在通信运维检修工作中,路由规划一般采取人工规划方式,这不但耗时费力、工作效率低下,而且容易出现纰漏。针对此问题,设计实现一个保护通信专网路由自动规划平台,用来取代人为规划路由。平台是在VBA窗体中编写代码实现的可视化界面,算法采用的是基于DFS算法改进提出的路由规划方法。通过人为规划与平台规划的结果对比,得证平台的规划结果准确可用,也是最优的迂回路由方案。文章提出的保护通信专网路由自动规划平台,实现了220kV线路保护通道路由的智能化调度,对智能电网工作有一定的推动作用,可继续优化推广于通信运维检修工作中。

基于深度优先搜索算法的电力系统生成树的实现方法

电力系统仿真验证往往希望通过拓扑结构图直观地分析网络的潮流分布以及动态特性。然而电力系统机电暂态过程仿真软件如BPA、PSS/E和PSASP都不能自动地根据电力系统的电气联系合理地布置网络中的元件,而需要人为地调整各元件的位置来形成一个直观的电气接线图。这种人为手动调整,不仅给仿真增加了工作量,更有可能带来更多的人为误差。为此,文中提出了基于图论的深度优先搜索(depth first searching,DFS)算法,依据电力系统的电气拓扑结构形成电力系统生成树的实现方法。用文中方法生成的IEEE9节点算例系统的可视化界面验证了该算法的有效性和准确性。