基于深度优先反向搜索算法确定有效路径集合

基于最短路径中任意路段因发生交通事件而失效时的替代路径搜索,合理界定了有效路径的阻抗值范围。参考深度优先算法和有效路径Dail算法离终点越来越近的思想,提出了一种从终点出发,反向搜索前置节点的多条有效路径搜索算法。算例结果表明:该算法能自动识别与路网结构相关的有效路径阻抗值范围,且能快速找到阻抗范围内的有效路径集合。

用独立通路法确定矿井通风网络的极值流

确定矿井通风网络极值流的常用算法有Ford-Fulkerson法、Edmonds-Karp法和Dinic法。所谓独立通路就是采用深度优先搜索法在找通路的过程中,后面的通路至少要含有一条前面的通路所不含有的分支。独立通路法确定网络的极值流,就是利用找独立通路的思想来找增广路,找增广路时每次至少有一个分支达到饱和。从网络的源点开始进行寻边,找分支的可增广量为最大的出边,将该出边的末节点作为新的寻边始节点,继续找可增广量最大的出边,该搜索过程一直到所寻找的分支的末节点为网络的汇点为止,一条增广路即一条通路确定完毕,将该通路中分支的最小增广量作为通路的增广量对通路的各分支进行增广。增广后至少有一条分支达到饱和,删除饱和分支,用导出的网络继续找新的增广路并增广。

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

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

储罐探伤爬壁机器人全遍历路径规划方法

储罐探伤爬壁机器人全遍历路径规划要求机器人高效遍历储罐外壁全部无障碍物区域。结合邻接矩阵、路径选择函数,提出一种单元分解算法并应用于爬壁机器人路径规划中。首先,将爬壁机器人的工作环境简化为二维平面,并通过分析漏检面积确定机器人遍历基本路径;接着,建立栅格环境,对每个栅格赋予xi值以表示其栅格状态;其次,采用矩形分解法将工作环境划分为若干子区域,通过图的深度优先搜索算法和邻接矩阵确定各子区域的衔接顺序;最后,在子区域的遍历和切换过程中,引入方向函数yi来判断爬壁机器人是否陷入死区,结合xi值提出路径选择函数fi以引导爬壁机器人快速逃离死区。在虚拟环境中进行了仿真实验,仿真结果表明,该方法不仅能引导爬壁机器人以高覆盖率和低重复率遍历工作区域,而且能快速地逃离死区。全遍历路径规划的实现拓展了爬壁机器人在检测储罐罐壁中的应用。

基于深度优先的一种网络最大流求解法

网络最大流问题在工程和科学领域应用广泛,许多线性规划的实际问题都可转化为网络最大流的模型来求解,开辟了图论应用的新途径。为了解决现有的求解网络最大流算法存在的步骤繁复、计算量大、由于增广链选取的顺序不当而无法得到理想的最大流等问题,文中在原有算法的基础上作了一些改进,应用图的深度优先搜索原理,提出一种新的求解最大流问题的算法。该算法可以简单快速地找到增广链,提高了算法效率和可控性,易于实现,且避免了标号过程,只需要在一个图上即可完成,整个运算过程直观性强,计算方便。

基于农田环境的农业机器人群协同作业策略

为合理分配农业机器人群协同作业中各机器人的工作量与工作区域,提高机器人群协同作业的整体效能与工作效率,该研究提出一种复杂环境下异质农业机器人群的任务分配及全区域覆盖策略。在考虑农业机器人异质性的基础上,以机器人团队整体效能最优为目标进行任务分配并确定各机器人的工作量。根据农场实际工作环境建立一级分区的概念,在栅格化环境建模与障碍物膨胀处理的基础上,在一级分区内部建立二级分区的栅格分区和分区合并规则,简化农田中的复杂工作环境;将遗传算法与混合粒子群算法相结合改进遗传算法交叉操作,建立遗传算法染色体种群多样性的概念,并综合考虑遗传算法染色体适应度值的差异以及种群多样性阶段设置自适应交叉变异概率,继而利用改进的遗传算法解决深度优先搜索算法在一级分区与二级分区间的遍历顺序问题;设置深度优先搜索算法在二级分区内的路径搜索规则,并在栅格图内遍历的同时根据各机器人的工作量分配其工作区域,设置机器人在其工作区域中的遍历规则,实现机器人群对农田的全区域覆盖。仿真试验结果表明,改进的遗传算法所得到的遍历各分区的路径长度与收敛迭代次数较传统遗传算法分别减少了2.8%与69.5%,较模拟退火算法分别减少了9.3%与19.0%;包含3、5、7、9和11个障碍物的5幅环境地图中,机器人群遍历工作区域的总面积重复率分别为6.3%、8.9%、16.7%、21.7%和23.4%。在4种面积相等的异形农田中设置相同数量的障碍物进行验证试验,结果表明,机器人群总遍历面积重复率分别为16.7%、13.1%、11.9%和6.7%。机器人群协同作业场地试验结果表明,4个试验机器人均可在规定的时间要求(25 min)内完成各自工作量,遍历面积重复率分别为5.77%、4.14%、6.75%和4.85%。研究结果可为复杂环境下农业机器人群协同作业策略提供理论支撑。

面向高速综合检测列车的应答器关键数据检测方法

应答器作为CTCS-2/3级列控系统的关键基础设备,其用户报文数据必须与现场列控数据准确对应。目前主要依靠人工及车载设备动态试验核对,工作量大且无法保证报文信息的准确性。为此提出了一种面向高速综合检测列车的应答器关键数据检测方法。首先通过KMP模式匹配算法实现现场列控数据的自动导入;其次利用深度路径搜索算法对应答器关键数据进行搜索,并和应答器用户信息进行对比,给出对比结果和报警日志;最后通过在海南西环线进行现场试验,验证可靠性,为高速铁路应答器报文检测研究及工程实践提供了有效的技术支持。

基于深度优先遍历算法-回溯算法的公交网络限时免费换乘优化模型求解

基于青岛市"限时免费换乘"政策理念,建立费用与时间、换乘次数的关系模型,采用深度优先遍历与回溯相结合的算法,寻找限定时间内最短时间与超限时条件下最低费用路径,给出起讫点间的最优路径方案。结合车站智能诱导发布平台对算法进行验证。运行结果表明,DFS-回溯算法在数据规模较大的情况下,比蚁群等全局搜索算法效率高,可既快又准地找到最优路线;基于该算法的最佳路径模型方案,可准确的为乘客提供最大选择便利性,实现公共交通资源利用最大化。

基于启发式搜索算法的无人机航迹快速规划

基于无人机导航系统的自身特点,无人机在导航过程中会出现无法精确定位的情况,从而产生定位误差。如果不能及时校正随时间累积的定位误差,会使无人机无法到达预定目的地,从而导致飞行任务失败。为避免这种情况的发生,研究了考虑定位误差的无人机航迹快速规划问题。以航迹距离最短为目标,考虑定位误差校正约束与航迹约束,建立混合整数规划模型。根据深度优先搜索算法与回溯算法的特点,设计启发式深度优先搜索+回溯算法来求解问题,并在此算法基础上加入模拟退火机制对解的质量进行优化。以某飞行区域的数据为例进行仿真实验,结果表明启发式深度优先搜索+回溯算法可以快速有效地求解考虑定位误差的无人机航迹规划问题。

四种最短路径算法实例分析

通过理论分析,结合实际应用,在GIS节点数很大的数字地形图中,从完备性、最优性、时间复杂度、空间复杂度几种性能问题实例分析,较系统地总结出深度优先搜索(DFS)、广度优先搜索(BFS)、双向广度优先搜索(DBFS)、A★算法四种算法代价及优缺点.

基于三维时空地图和运动分解的多机器人路径规划算法

针对当前多机器人路径规划策略中存在的路径耦合性高、总路径长、避碰等待时间长等缺点,以及由此导致的系统鲁棒性低、机器人利用率低等问题,提出了基于三维时空地图和运动分解的多机器人路径规划算法。首先,根据已有路径集和当前机器人的位置生成时间维度上的动态临时障碍物,将其与静态障碍物一并拓展为三维搜索空间;其次,在三维搜索空间内,将路径运动总时间拆分为运动时间、转向时间和原地停留时间这三个参数,并使用条件深度优先搜索策略计算出从起始节点到达目标节点的所有符合参数要求的路径集合;最后,遍历路径集合中的所有路径,对于每条路径,计算其实际总耗时。如果某一路径的实际总耗时和理论总耗时之间的差距小于规定的最大误差,则可认为该路径为最短路径,否则,继续遍历剩下的其余路径;而如果路径集合中所有路径的实际总耗时和理论总耗时之差全都大于最大误差,则需要动态调整参数,然后继续执行算法的初始步骤。实验结果表明,所提算法规划的路径具有总长短、运行时间少、系统无碰撞、鲁棒性高等优点,解决了多机器人系统完成持续随机任务的问题。

航线运输驾驶员转场训练网络优化设计

为了改进传统航线运输驾驶员转场训练网络设计方法的不足之处,以降低转场训练网络的设计总成本,构建了包含源发弧、始发弧、衔接弧和到达弧在内的转场训练路径衔接网络,并利用计算机深度遍历算法获取各类转场训练科目的可行训练路径集合,然后以训练基地选址和流经各转场训练路径上的航线驾驶员培训数量为决策变量,并综合考虑训练基地设置数量、航线运输驾驶员培训总人数和各训练基地转场训练容量等限制条件,以转场训练网络总成本最小为目标函数,构建转场训练网络优化设计数学模型。算例结果表明,与传统方法相比,该方法将转场训练网络总成本降低了9.18%;通过将空域及机场容量在-30%~30%之间波动,发现转场训练网络中训练基地数量发生变化,并使得网络设计总成本在1.12%^-10.67%之间波动。因此,该方法是可行且有效的,能够为飞行航校的转场训练网络设计提供指导。

有向非负权图中经过必经节点集最短路径算法

传统的Dijkstra算法只是针对起点和终点求解最短路径,而不能解决从起点出发,经过必经节点集,到达终点的无重复节点且无回路的最短路径问题。为此,在有向非负权图中,提出了Dijkstra算法和回溯法相结合的方法。对Dijkstra算法改进,并求解关键节点(起点,终点和必经节点)间的最短路径,进而从关键节点所构成的矩阵中采用回溯法得到目标路径。通过实际的算法实现,测试大量的有向非负权图数据,证实了算法的有效性和正确性。

用于游戏NPC路径规划的改进遗传算法

针对游戏非玩家控制(NPC)路径规划中传统遗传算法计算速度慢、正确率低等问题,设计了改进型遗传算法。提出了最佳种群规模估计方法,设计了基于精英主义思想的遗传算子。根据游戏地图的特点,引入了基于启发式深度优先搜索的变异操作。与传统遗传算法以及其他学者的改进算法进行了对比实验。实验结果表明:算法能够在保证正确率的前提下,提高计算速度,并且在多目标的环境下同样适用。

基于铁路客运运营条件信息的径路算法研究

为进一步提升铁路客运运营条件信息管理的智能化关联能力,在规范铁路客运运营条件信息的基础上,分析DFS,Dijkstra,A*等经典图论算法的径路搜索算法适应性,对比确定以DFS算法作为铁路客运运营条件径路搜索算法的基础,并从简化搜索节点、限定搜索区域、结合列车开行、控制递归深度等方面对DFS算法进行优化,该优化算法可以为不同站间径路的搜索需求提供全面、高效的站间合理径路查找工具,为票价计算提供支撑信息,对提升径路搜索效率,提高铁路客运运营条件信息的管理水平,促进路网基础信息管理与路网规模相适应有重要意义。

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

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

震后最优应急救援路径决策研究

通过考虑震后道路实际通行能力和通行时间,设计了多目标路径优化模型,引入深度搜索法的主要思想对遗传算法进行改进,再对模型进行求解。通过MATLAB模拟仿真验证了改进后的遗传算法所求解的最优应急救援路径,不仅迭代次数较少而且求解的最优值明显优于传统遗传算法,能够更好地满足对震后应急救援路径决策的需求。