一种基于分层图的改进SPFA算法

针对数据结构课程教学中顶点数受限的最短路径问题,提出一种基于图分层的改进SPFA算法——K_SPFA。借鉴图分层思想,将原图拓展为层数与顶点限制数相等的图层,将原图中的边拓展成图层间的边。利用2个同步循环的FIFO队列和贪心策略,对SPFA算法的数据存储结构和最短路径更新操作进行改进,从而实现原图中顶点数受限的最短路径寻找。实验结果表明,K_SPFA具有较低的平均时间复杂度。

SPFA算法的分析及改进

SPFA(Shortest Path Faster Algorithm)算法是一种对任意有向图求单源最短路径的算法。该算法实现简单,实际运行效果较好,在国内有着比较大的影响力。但遗憾的是,该算法一直缺少正确的理论分析。对该算法进行了分析,指出该算法在不存在源点可达负圈的有向图中,最坏情况运行时间为Θ(|V||E|);在存在源点可达负圈的有向图中,算法将无限运行下去。对此,给出了改进的SPFA算法,对于任意的有向图,该算法能够在O(|V||E|)内运行完毕。最后,从实际运行角度将SPFA算法与其它思想上同源的最短路径算法进行了一系列比较。

基于最短路径快速算法的船舶管路自动敷设方法

为解决船舶管路布置依靠专家经验且效率较低的问题,提出一种基于最短路径快速算法的船舶管路自动敷设方法。在该求解方法中,首先对布置空间进行网格化处理,根据管路布置的约束对网格状态进行设置,再将传统的最短路径快速算法扩展到三维网格空间,并将网格能量值引入距离松弛函数,将可以通过网格能量描述的布置约束考虑其中。在此基础上给出单管路和带分支管路的敷设方法,并针对船舶管路对弯头数目、成束敷设、折弯长度、支架设置和接口方向等约束的要求,给出基于最短路径快速算法的处理方法。通过两个布置实例验证了方法的有效性。

地铁乘务排班计划优化的最短路快速算法

乘务排班计划是城市轨道交通运营管理中的重要环节,为了解决目前乘务排班效率低下的问题,对乘务排班计划进行优化。在考虑便乘的情况下,以乘务排班计划总接续时间最小及总运营成本最小为目标建立地铁乘务排班计划编制的双目标优化模型。在满足相关约束条件的基础上,将乘务作业段按照早、白、夜班分成3组,以乘务作业段为顶点,乘务作业段之间的接续关系为弧构建早、白、夜班的网络图,并形成乘务作业段接续时间矩阵,将乘务排班转化为最短路问题。运用相关最短路算法进行求解,该算法采用动态优化逼近的方法,一条最短路径即为一个乘务任务。以成都地铁5号线为例进行乘务排班计划编制,对模型和算法进行测试。研究结果表明:在求得的乘务排班计划中,早班乘务任务个数为53个,任务时长为280 h 34 min 57 s;白班乘务任务个数为41个,任务时长为199 h 54 min 51 s;夜班乘务任务个数为49个,任务时长为215 h 25 min 37 s。总乘务任务个数为143个,总工作时长为695 h 55 min 25 s。与手工编制结果相比,降低了乘务排班计划的总成本及接续时间,提高了求解效率。

移动机器人最优路径规划方法

针对移动机器人路径规划效率低的问题,提出了一种基于改进的最短路径快速算法的移动机器人最优路径规划方法。该方法在障碍Voronoi图基础上根据规则将起始点与终点加入该图以得到无碰撞路径图,然后采用改进的最短路径快速算法搜索从起始点到终点的最优无碰撞路径。仿真结果表明,采用该改进算法后,移动机器人能够沿着最优无碰撞路径前进,快速达到终点。

用于铜矿矿区的手机室内导航最短路径算法研究

带有电子地图的导航软件已经成为人们身边不可或缺的工具,但是室内导航软件尚未普及。本文针对铜矿矿区室内地图范围小、结构简单、弧段少的特点,采用经典算法从可行性和计算时间进行对比,分析各种经典算法优劣,确定用于铜矿矿区的室内导航算法。