一种具有必经点约束的非结构化环境路径规划方法

针对非结构化环境下具有必经点约束的路径规划问题,设计一种两阶段求解方法,并对每一阶段算法做出改进。第1阶段,对典型非结构化环境进行地图建模,针对A-Star算法存在的接触障碍物、路径曲折的问题,提出新的障碍物安全距离方法并设计折线优化策略平滑路径。第2阶段,详细阐述必经点问题的求解流程,建模为旅行商变体问题并将多种优化算法拓展至必经点场景。由于现有方法难以高效求解必经点问题,提出一种改进遗传粒子群(IGPSO)算法,包括分层随机初始化、改进交叉方式以及变异算子。最后进行对比实验验证,结果表明改进算法在最优解成功率、运行时间和迭代次数方面具备明显优势。

必经点最短路径问题模型及相应遗传算法研究

根据军事运输在路径寻优方面的特殊需求,将必经点最短路径问题分为三类,建立各类问题的数学模型。以分类保序最短路径为例,设计相应的改进遗传算法。该遗传算法构造了独特的适应度函数,使包含较多必经点的染色体能够优先被选择进入下一代种群。通过节点保序算子的引入,保证相关节点之间存在特定的先后次序,并提出一种新的引入必经点变异算子,提高算法的全局搜索能力,加快收敛速度。仿真结果验证了算法的有效性。

求解必经点k条最优路径问题的粒子群优化算法

提出了一种解决指定必经点k 条最优路径问题的粒子群优化算法。算法以k 条最优路径集合作为优化目标,将粒子种群划分为k 个子种群,通过各子种群的局部搜索和子种群间的相互协作,使种群在搜索过程中易于找到k 条最优路径。为了提高含有多必经节点的初始生成路径的多样性,设计了基于弹性拉伸原理的种群初始化方法。在随机生成的26 个节点65 条边,50 个节点262 条边和80 个节点410 条边的拓扑图中,分别选取不同的源节点和目的节点,以及必经节点对算法进行了测试。数值实验结果表明,提出的算法在求解网络规模比较大、必经点数比较多的无环k 条最优路径问题中具有比较好的性能。

过必经点集且具有额外硬约束的最短路径算法

求解过必经点集的最短路径问题已有多种算法,但其应用到在具有额外硬约束限定条件的场景时存在不足。针对此类问题,提出一种基于深度优先搜索发展的随机搜索算法,由使用者依据现场情况给出数学描述,建模抽象为无向带权图表示;依据路径规划要求定义相关变量,包括路径规划的起点、终点、必经点集以及额外硬约束条件,图信息和节点信息以邻接矩阵的形式保存;搜索过程中对路径的可行性加入额外硬约束条件进行实时判定,最终获得最短路径解。实验仿真和实测结果表明,该算法能有效规避额外硬约束条件下的中间路径,生成合理的最短路径,改善相关问题的可求解性。

引入必经点约束的路径规划算法研究

针对传统A*算法存在搜索范围广、运行效率低的问题,提出了一种引入必经点约束的路径规划算法。该算法结合障碍物分布特点,通过寻找最短路径必经点,实现对A*搜索方向的约束,再对最短路径段进行拼接得到最短路径。最后,在100×100网格地图中进行对比实验,结果表明,引入必经点约束的改进算法比传统A*算法的结点访问量大幅降低,运行效率得到显著提高。

必经点约束型最短路径问题的研究

为了解决网络路由中带有必经点约束的网络拓扑中最优路径的问题,提出了采用改进的蚁群算法和Dijkstra算法对最优路径进行规划。首先,针对含有必经点约束的问题,在信息素初始化时增加在必经点上的信息素。其次,为了能够更好地找到最优解,采用了狼群分配算法进行信息素更新,提高了收敛速度,并且采用了Dijkstra算法对蚂蚁找到的最优路径进行二次优化。最后,分别用不同节点和必经点规模的网络进行实验,并与基本的蚁群算法进行了比较,证明了改进蚁群算法的正确性和高效性。

基于Dijkstra算法过必经点的最短路径设计

为改善传统诱导系统只涉及无必经点的单条最短路径的实现、使出行者的选择受到一定限制的局限性,设计了一种过必经点的最短路径,可方便人们的出行。通过建立路网节点属性数据库保存相关节点信息,并将路网信息数据导入到数据库,完善路网结构信息,再通过嵌入Dijkstra算法查找出过K个必经点的N条最短路径,最后将相关的路径信息显示在界面上。以26节点数据集模拟道路情况,实验结果表明该算法可以保证理论上的过K(小于5)个必经点的前N(小于5)条最短路径的实现,有效扩充了最短路径的数量,满足用户选择需求。

一种必经点最短路径求解算法

针对必经点无环路径求解问题,提出了一种基于A*算法的启发式路径搜索算法。算法通过在路径搜索过程中,在每个节点存储当前搜索路径的相关信息,从而有效提高了路径的搜索效率。最后描述了一个具体的算法实例以验证算法的正确性。

过必经点的最短无环路径算法

通过启发式算法解决在带权有向图中从某一源点经过指定的必经点集到达目标终点且节点不重复的最短无环路径问题。随着复杂网络优化问题的不断凸显,对网络分析算法的性能要求也日渐升高。经过必经点的最短无环路径问题的复杂度不亚于旅行商问题(TSP),但并没有获得广泛的关注。近些年来出现了一种高效的整数线性规划公式(ILP)来解决此类问题,这种ILP算法适用于有节点不相交约束的最短路径问题,但是实验表明在大型复杂网络中这种算法的时间开销过高。因此有了本论文的三种启发式算法,大量的实验表明这些算法在大多数情况下都能在可接受的时间范围内找出合理解,这些解与最优解的误差都在可接受的范围内,后续的CPU开销数据也表明此类启发式算法的资源消耗远小于整数线性规划(ILP)算法。

求必经结点算法的分析

本文指出，当给定流图Ｇ＝（Ｖ，Ｅ）的深度优先扩展树１时，求必经结点的Ｐｕｒｄｏｍ和Ｍｏｏｒｅ算法２中的循环次数恰为μ＋１，这里μ是图Ｇ的等待指数；并且可将２中算法的时间和空间各节省１／２。

城市交通中结点约束的动态最短路径查询算法

城市交通中道路拥堵情况多变,在车辆行进过程中两点间最短路径会发生改变。文章提出基于Dijkstra的动态更新算法,同时考虑必经结点对算法的影响,计算复杂度大大降低。文中给出了算法的理论依据,处理过程及最终效果图。

结点有拥塞的动态最短路径问题的算法研究

最短路径问题在交通运输领域以及网络路由选择方向都有着重要的应用.本文在有必经结点且所经结点无序的最短路径算法的基础上,研究结点有拥塞且拥塞程度是动态变化的最短路径问题.对于这种情况的研究,在交通运输领域的高速公路以及局域网络上的路由选择都有着重要的应用.文中对结点的权值,即拥塞程度的预测采用了Kalman滤波方法,并用改进了的Dijkstra算法求解结点间的最短路径.相关实验结果及分析表明,该方案可以有效地解决结点有拥塞且拥塞动态变化的最短路径问题.

基于遗传算法的军事运输路径优化

在建立军事运输路径优化模型的基础上,设计了求解最小广义权路径的遗传算法;针对军事运输中的必经点和节点保序问题,构造了特殊的染色体编码规则和交叉、变异的处理方法;提出通过对初始种群染色体的预处理来提高算法的性能.最后,进行了算法的比较实验和结果分析,以验证算法的可行性和有效性.

定向越野团队赛技战术问题研究

定向越野团队赛的主要特征是团队协作,与个人比赛项目相比需要更高、更全面的技战术能力。在团队赛中,队员之间必须明确分工,相互信任、相互协作,才能取得好的成绩。在团队赛起点准备阶段准备工作必须充分细致,起点、场地和终点,不同阶段有不同的技战术要求。

过程内控制依赖的计算

对于广泛的软件维护和测试任务而言,控制依赖信息是很有用的。软件工程中控制依赖通常用来确定一条程序语句语义的变化是否影响其它程序语句的执行。控制依赖是在图论的后必经概念的基础上定义的,控制依赖关系的标准表示是控制依赖图(CDG)。论文着重介绍了一种计算过程内控制依赖的算法,并分析了该算法的时间和空间复杂度。

改进遗传算法在强边界路径规划中的应用

根据陆军武器系统对地图行军导航的特殊需求,提出了一种基于改进遗传算法的强边界路径规划算法。对强边界路径规划问题进行了分类,建立了强边界路径优化问题的数学模型,以分类必经点保序路径最优问题为例,从染色体的编码、种群的初始化和遗传算子等方面,加入了必经点保序的条件,设计了改进遗传算法,仿真结果证明了算法的有效性。

城市燃气高压管道巡检系统建设与实践

阐述管道巡检必经点和事件的概念、区别、分类,结合规范、地方政府和公司管理规定梳理了必经点标准化巡检内容;按照管道完整性管理业务管理理念,通过应用实践,建立了城市燃气高压管道巡检系统,打通了巡检系统和管道完整性管理系统之间相关数据传送渠道;介绍巡检系统主要业务功能模块,分析巡检系统技术实现,使巡检管理趋向规范化,保障管道安全运行。

一种改进的计算控制依赖的算法

控制依赖是分析程序和程序并行化的基础。针对现有的计算控制依赖方法的不足,提出了一种改进的算法。该改进算法通过引入函数调用和返回引起的控制转移来计算函数间的控制依赖关系。最后通过实例验证了该改进算法比原算法更能准确地计算程序的控制依赖关系,比传统的内联方法更易于理解。

决战丛林 砥砺“侦察奇兵”

按图行进、牵引横越、崖壁攀登、野外生存……日前,第80集团军某旅在胶东半岛某山区,组织侦察分队开展三天两夜的野外侦察演练,在复杂恶劣天候条件下,全面锤炼侦察兵战场生存能力。演练开始,侦察小组在大雨中依据导调组给定的必经点坐标,自行规划行军路线。夜幕降临,经过峭壁、雷阵及宽河的考验,侦察兵个个早已精疲力尽。

流图可归约性判定的一个实用算法

本文得到了流图Ｇ可归约性判定的一个实用的充要条件．并给出了一个可归约性判定算法，该算法同时计算出Ｇ中各结点的必经结点集．对于不可归约流图，还可指出Ｇ中的所有向后边（ｒｅｔｒｅａｔｉｎｇｅｄｇｅｓ）。对于实际实用，其时间复杂性优于通用的计算必经结点集的算法．