一种基于Dijkstra的物流配送路径优化算法设计

在物流配送过程中,物流配送路径的选择是决定快递时效的关键因素。针对传统Dijkstra算法在大规模数据求解过程中效率低、耗时长的问题,文中对其进行了深入的改进和优化。在算法运行过程中,通过使用多标号模型对遍历过程进行了优化。同时,在运算过程中采用并行求解的模式来提升模型处理速度。实验测试结果表明,文中设计的路径优化算法相比传统Dijkstra算法,大规模数据的求解时间缩减了50%以上,算法并行加速比在大规模数据求解时达到了1.75倍,证明了所提算法的并行求解效率较高,具有良好的工程应用价值。

Petri网结合Dijkstra算法的并行测试任务调度方法研究

针对测试系统中的并行任务调度方法复杂且难以优化的问题,提出并实现了一种利用Petri网并结合Dijkstra算法的并行测试任务调度方法,从而减少了搜索算法的复杂度。该方法通过对Petri网可达数分析工具的充分利用,省去了传统方法在得到任务调度结果过程中的一些步骤。首先建立测试系统的Petri网模型并生成其可达树;然后对可达树模型进行加工和改进,添加状态节点间的联接关系;进而在加工、改进后的可达树模型基础上应用Dijkstra算法得到并行测试任务最佳的任务调度策略。针对一个工程实例应用任务调度方法进行了仿真实验与分析,仿真实验结果证明了该方法的有效性和正确性。

基于Dijkstra算法柔性作业车间调度的研究

对柔性车间单目标调度问题进行了分析,以产品为研究对象,以最大完工时间最小为目标,考虑并行机、加工等待时间对其进行了数学描述和建模。提出了工件加工顺序的决策方法,并改进了Dijkstra算法对其进行求解,通过实验验证了该算法的正确性和有效性,通过与其它文献的比较验证了该算法的优越性。

Dijkstra算法的并行实现

文章研究了一种多核架构下基于OpenMP的Dijkstra并行算法,以Dijkstra算法为基础设计并行程序。对传统Dijkstra算法进行分析,明确优化方向,再利用OpenMP开发工具对并行程序进行优化调试。结果表明,文中算法易于操作,并充分利用了多核处理器并行计算的优势,提高了算法的运行效率,验证了算法的优越性。

基于并行计算的快速Dijkstra算法研究

通过分析经典Dijkstra算法的思想和执行流程,对多标号的Dijkstra算法给出新证明,以此作为理论依据对Dijkstra算法进行了多标号的串行与并行优化。对于正则树,给出了经典Dijkstra算法、串行多标号Dijkstra算法和并行多标号Dijkstra算法的时间复杂度排序。针对优化算法的特点,设计出四种实验,采用运行时间和并行加速比作为优化指标,考核三种算法的效率。仿真实验表明:对顶点数大于6000的稠密图和稀疏图(正则树),多标号并行算法优于串行算法,且优化效果明显;对于正则树,优化效果分别与深度、出度成正相关。

大规模网络渗透测试路径规划方法研究

路径规划是渗透测试过程中非常重要的步骤。面对完全信息条件下的大规模网络渗透测试,传统的规划方法存在路径规划耗时长、规划的路径执行效果不好的问题。针对该问题提出一种在并行条件下基于漏洞利用程序评分的规划方法。该方法基于Metasploit框架对现有的漏洞利用程序建立量化评分模型,并以漏洞利用程序评分为标准,建立网络连接关系图,利用并行化的最短路径算法进行路径规划。对比实验结果表明该方法能够更加快速有效地实现大规模网络的渗透测试路径规划。

基于点割集的并行最短路径算法

在研究和分析了Dijkstra算法的基础上,在Dijkstra算法中通过引入点割集和割点的思想来改进Dijkstra算法,该方法首先利用点割集或割点把原问题分解成多个子图,然后对每个子图并行求最短路径,最后通过点割集或割点求出整个原问题的最短路径,从而降低算法的时间复杂度,提高算法的效率.

可扩展路由器中SPT并行计算的实现

随着互联网的飞速发展,集群结构的下一代核心路由器已经成为研究的重点.在可扩展路由器中(clus- ter router),并行路由算法是关键问题之一.对于广泛部署的OSPF协议,最短路径树(SPT)的并行计算是其并行化的核心难点.本文提出了一种计算最短路径树的算法-分区Dijkstra算法(D-D),分析了算法性能,并通过模拟实验验证了算法的性能.

改进的最短路径算法在多点路由上的应用

Dijkstra算法是目前公认的较好的最短路径算法。由于多点路由问题最终归结为最短路径问题,因此将算法改进后应用于多点路由问题。提出的改进主要有以下3点:(1)改变选路策略,基于蚁群算法实现Dijkstra算法的选路操作,使选路更加灵活。(2)结合网络模型的特点,减少了对两顶点之间最短路径以外的大量顶点的计算,提高了算法的速度。(3)考虑到网络路由问题中的阻塞问题,对阻塞顶点进行标识,防止算法选择无用顶点。模拟实验结果表明改进算法较之Dijkstra算法在运算速度上有明显提高。

利用多线程技术实现最短路径的并行算法

最短路径问题是图论中的一个典范问题,它被应用于众多领域。最短路径问题可以分成两类:单源最短路﹑所有顶点对间的最短路径。在研究图中最短路径问题上,Dijkstra算法是其中最为经典的算法之一,本文主要介绍所有顶点对间的最短路径问题,提出了一种更高效的新的所有顶点对间的并行算法。最后利用多线程技术对给出的并行算法进行了实现。

基于D5000系统的黑启动并行恢复策略

研究了变电站无人值守相关问题下,发电机的并行恢复策略。先针对现阶段电网运行状况建立了变电站无人值守情况下线路的启动时限模型,得到了线路启动的时间成本期望。再建立了发电机有功出力和进相运行能力关于时间的函数。然后定义了电源中心的概念,并以之为依据求取了机组启动的距离成本。考虑机组启动的多种限制因素,调用迪克拉斯算法,计算考虑时间成本和距离成本的机组最优启动序列,通过并行校验确定机组启动顺序。最后应用IEEE39节点算例对所提出方法进行了分析验证,结果表明可明显提高机组恢复效率。

基于Java多线程实现所有顶点间最短路径的并行算法

提出了利用Java多线程来实现并行计算的构想,并以所有顶点对间的最短路径问题为例,对此构想进行了理论分析,最后通过实验证明了此构想的正确性．文中还依据Dijkstra算法的实现原理提出了一种新的所有顶点对间的并行算法,并且利用Java多线程技术对给出的并行算法进行了实现．

铁路通信网路径选择性能优化及仿真分析

提出了铁路通信运营支撑系统(RCBSS)的体系结构,讨论了 Dijkstra 算法在其电路路径自动搜索上的应用,在此基础上提出了基于动态权值、具有平衡网络负载功能的路径搜索优化方案,并利用存储过程、动态链表初始化、四叉堆排序以及双向并行搜索算法,有效地提高了其搜索速度,合理地分配了网络负载,使网络性能得以优化。最后,通过仿真性能分析证实了这一方案的优越性。

MapReduce下的Dijkstra并行算法研究

文章对求解单源最短路径的Dijkstra经典实现算法进行了基于MapReduce编程模型的并行化设计,通过分析MapReduce中的Map过程和Reduce过程,解析该算法的设计思想和执行流程,最后在Hadoop云平台下设计实验,测试并验证了该并行算法的正确性和高效性.