基于Floyd算法的多重最短路问题的改进算法

路径分析是网络分析最基本的问题,其核心是对最短路径的求解。Floyd算法是一种求取最短路的经典算法。分析发现,两点间可能存在多条权重相同的最短路径,而这一点Floyd算法没有涉及。以无向联通图为研究对象,设计了基于Floyd求解多重等价最短路算法,并分析计算了一个实际算例。计算结果表明,基于Floyd的多重等价最短路算法可以有效解决多重等价最短路问题。

最短路问题的Floyd算法优化及分析

在传统Floyd算法的基础上,运用动态规划思想通过迭代求出最终的最短路矩阵,并在迭代过程中先筛掉不能使路径权值变小的部分中间节点不参与迭代,从而简化计算权值矩阵的运算步骤,缩短矩阵运算时间。分析结果显示本文算法明显提高了运算的效率,降低了算法的复杂度。

Floyd算法的改进与优化

介绍一个改进的Floyd算法。本文综合运用C++语言编程技术,设计并实现了求带权有向图中各个顶点之间最短路径的算法,反映了最短路径序列上前后两个顶点之间的先后关系。本算法从顶点出发,每次在求各顶点间最短路径的时候,都进行路径优化。改进后的Floyd算法,迭代速度快,计算量一定程度减少。

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

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

无向哈密顿图的自适应遗传算法

回溯搜索方法和路径扩展方法是判定无向哈密顿图的两种重要途径,其缺点是要么进行路径选择的回溯,从而造成指数阶时间开销,要么由于剪枝技术而遗漏正确答案.任何一个无向哈密顿圈总是可以分解成若干个原子圈,这些原子圈按照某种次序以单条公共边连通.根据这个特征,文中使用原子圈和基本圈作为染色体,设计成可拼接/可分解的遗传编码,提出一种新的自适应遗传算法,用于降低时间开销,保证正确判定.对一些实际案例的测试结果验证了该算法的有效性.

快速求取自由曲面上两点间的最短路径算法

利用求无向图中一定点到各项点间的最短通路算法──Ｄｉｊｋｓｔｒａ算法，并应用曲面片细分原理，提出了一种快速求取自由曲面上两定点间的最短路径值和路线的算法──快速ＦＳＰＦＦＳ算法。该算法广泛适用于凸凹自由曲面，具有广泛的实用价值，对计算机辅助几何设计的发展应用具有较重要的意义。

标记法求解网络和图的最短距离算法

采用深度优先搜索法,文章首次提出了在搜索过程中采用标记距离的算法,有效地求解复杂网络和图的最短距离问题。通过对网络最短距离问题运算效率的分析,表明该算法具有理想的运算效率。文章给出了一个具有现实应用价值和更具潜在应用价值的智能问题算法。

矿井通风设计的最短路线法

本文应用图论中的最短路线法理论分析研究了矿井通风设计问题.给出了求最短路线的两个算法——Dijkstra算法和Floyd算法.最后以该方法分析两个矿山通风系统实例,取得了分别节能19.89%和20.05%的显著效果.

基于Dijkstra算法的列车进路选择

在计算机联锁中,列车进路的算法设计是最关键的环节,它关系到列车的运行安全和车站通过能力的提高。Dijkstra算法能够计算出无向图中某个任意结点到其它所有结点之间的最短路径,给车站及咽喉区提高通过能力提供了可能性。如果把车站用无向图来表示,车站设备的占用状态信息融合到算法中,就可以很方便地实现利用计算机来选择列车的进路。

基于DNA计算的无向赋权图哈密顿路径问题

本文给出一种通过DNA序列编码来处理权值的方式,对无向赋权图哈密顿路径问题进行了描述。首先用寡核苷酸片段编码图中的顶点和边,然后将这些寡核苷酸片段放入缓冲溶液中,利用连接酶将它们连接起来,从而产生所有无向边不同的DNA链,最后利用PCR扩增、探针、电泳等生物手段寻找对应于只经过图的顶点一次的无向Hamilton路的DNA链,通过比较以及前面实验条件的控制最终找到最短的Hamilton路径。

混合智能算法在AGV全局路径规划中的应用研究

首先采用网络拓扑图法对AGV工作空间建模,将AGV路径规划问题即可转化为求解网络拓扑图的最短路径问题。然后用Floyd-Warshall算法求拓扑图的可行路径点;再用改进的自适应遗传算法来调整各个可行路径点,得到最优或近似最优的路径。MATLAB仿真结果表明本算法行之有效,可以较为准确地搜索到AGV的全局最优路径。

基于近似最近邻搜索的改进PRM算法

针对移动机器人工作环境范围复杂时,使用传统概率路线图(PRM)算法非常耗时的问题,提出一种改进的PRM算法。PRM算法最耗时的部分是构建无向路径图,构建无向路径图的关键是近邻搜索。通过使用近似最近邻搜索中的局部敏感哈希算法代替原先最近邻搜索算法,在不降低生成路线图质量的前提下,加快无向路线图的构建速度,减少PRM算法的运行时间。仿真结果表明,改进的PRM算法相较于传统的PRM算法在无向路径图建立时间上减少27.36%~33.27%,使PRM算法效率大大提高。

基于改进蚁群算法的AGV路径研究

针对传统蚁群算法在复杂仓储环境中路径规划时不具备自主避障并且陷入局部最优解从而得不到最优路径的问题进行研究。文章通过构造MAKLINK无向网络图和优化蚁群算法中的启发函数,引入动态光滑因子和全局信息因子,达到控制AGV路径的长度和光滑程度,并构造避障因子使AGV路径在达到全局最优路径的同时拥有避开障碍的能力。通过研究,提出的改进算法可以实现自主避障,并且在最大迭代次数、路径距离和光滑程度方面优于传统蚁群算法。

基于蚁群算法的三峡升船机船厢设备巡视点检路线规划

针对三峡升船机船厢结构复杂,设备巡视路线难以选择的问题,以升船机船厢巡视路线为研究对象,将设备巡视点检路线规划转换为TSP旅行商问题.通过巡视路线无向加权图及点位空间坐标,建立升船机设备巡视点检点位空间结构模型.结合蚁群算法在Matlab软件中分别计算出白班及中班的最佳巡视路线.实验结果表明,基于蚁群算法计算的最佳巡视路线符合三峡升船机设备巡视要求.

无向路图和块图上的混合控制

图G=(V,E)的一个混合控制集是一个满足如下条件的集合DV∪E:不在D中的每个点或每条边都相邻或关联于D中的至少一个点或一条边.确定图的最小基数的混合控制集的问题称为混合控制问题.本文研究混合控制问题的算法复杂性,证明了混合控制问题在无向路图上是NP-完全的,但在块图上有线性时间算法.无向路图和块图都是弦图的子类,又是树的母类.