共查询到20条相似文献,搜索用时 15 毫秒
1.
针对最短路径算法处理大规模数据集低效的问题,提出了基于图形处理器(Graphics Processing Unit,GPU)加速的全源对最短路径并行算法.首先通过优化矩阵乘法算法实现了在工作组内和组间进行并行运算数据,然后减少了非规则行造成的工作项分支,最后降低了工作项对邻接矩阵计算条带存储资源的访问延时.实验结果表明,与基于AMD Ryzen5 1600X CPU的串行算法、基于开放多处理(Open Multi-Processing, OpenMP)并行算法和基于统一计算设备架构(Compute Unified Device Architecture, CUDA)并行算法相比,最短路径并行算法在开放式计算语言(Open Computing Language, OpenCL)架构下NVIDIA GeForce GTX 1 070计算平台上分别获得了196.35、36.76和2.25倍的加速比,验证了提出的并行优化方法的有效性和性能可移植性. 相似文献
2.
3.
D算法(Dijkstra,狄杰斯特拉算法)是典型的单源最短路径算法,用于计算一个节点到其它所有节点的最短路径。从存储结构角度,提出一种优化D算法的最短路径方法,利用基于COMArcEngine技术加以实现。 相似文献
4.
最短路径是GIS领域的主要问题之一,本文从静态最短路径算法和动态最短路径算法两个方面对GIS中最短路径理论和实现算法进行了分析和研究,比较了各自特点及适用条件,初步探讨了Dijkstra,A*,D*等典型的寻路算法. 相似文献
5.
最短路径算法是计算机科学与地理信息科学领域的研究热点。本文对常用的最短路径标号算法进行了分析,并讨论了优化算法的方法。 相似文献
6.
在寻找由结点和路径组成的图或实际应用中两结点之间的最短路径。要解决的内容的形式包括:确定起点和终点的最短路径问题就是在已知起始结点的情况下开始求最短路径的问题,并寻求得到最终结点的关于最短路径的问题。研究的目的在于通过二维数组的结构优势,为研究最短路径问题探讨了一些可以解决的办法。利用二维数组的数据结构优势,通过原始的直接和间接距离得出的数据组成的二维数组,其在C++的基础上做出空间分析,不仅计算出了最短路径,还找出了该最短路径下所经过的路径结点。通过该平台,可以有效的设计算法程序,实现计算,用于解决最短路径问题。 相似文献
7.
最短路径问题是在给定的网络图中寻找出一条从起始点到目标点之间的最短路径。蚁群算法是一种用于求解优化问题的新型模拟进化算法,该算法在许多相当困难的优化问题的求解中体现了极强的寻优能力和较好的性质。提出了一种利用蚁群算法来解决网络最短路径问题的新方法,并用Matlab语言编程进行算法的实现和仿真。结果表明,蚁群算法在寻求网络最短路方面的应用是可行的。 相似文献
8.
针对已有的路由保护方案没有很好权衡路由保护算法的故障保护率和路径拉伸度之间的关系,该文提出了一种基于段路由(SR)体系结构的快速重路由算法IPFRRBSR。IPFRRBSR为每个源-目的对计算两条路径,其中一条是最短路径,另外一条是利用段标签构造的备份路径。当网络没有故障时利用最短路径转发报文,当网络出现故障时利用备份路径转发报文。最短路径和备份路径(除去源和目的)没有公共节点,因此二者几乎不会同时发生故障。实验结果表明:该算法不仅可以应对网络中任意的单节点故障情形,并且具有较小的路径拉伸度。 相似文献
9.
10.
路网车流径路优化调整中的最短径路算法 总被引:1,自引:0,他引:1
目前铁路车流径路基本上都是按照路网的最短路径来安排的,首先一般都采用Dijkstra算法计算最短路径,然后参考相应区段的能力限制,对车流进行分配,对车流量超过能力的区段重新进行车流调整,这时需要重新计算新条件下两点间最短路径,一般仍采用Dijkstra算法重新计算两点最短路径,这大大地浪费了前期的计算最短路径的信息,增加了计算工作量,本文采用A*算法作为一种启发式算法,可以克服这一缺陷。 相似文献
11.
为了实现无人驾驶拖拉机在直线作业时的实时避障路径规划功能,提出一种在改进最短切线法的基础上用五次多项式函数规划路径的避障路径规划算法。针对最短切线法规划的路径曲率不连续、难跟踪控制的问题,首先采用改进最短切线法求相关坐标点,然后基于求得的坐标点用五次多项式函数求解路径,最后得到由两段五次多项式函数曲线和直线组成的曲率连续的避障路径。对避障路径规划算法进行仿真,结果表明,该算法生成路径长度短、实时性好、安全性高。基于常州东风无人驾驶拖拉机的运动学模型设计一种模型预测控制器,在Simulink与CarSim联合仿真平台上对无人驾驶拖拉机的避障路径规划及跟踪控制进行联合仿真,结果表明:与改进最短切线法相比,基于五次多项式函数的路径规划算法规划的路径跟踪控制精度更高,更易于跟踪控制。 相似文献
12.
程远 《重庆文理学院学报(自然科学版)》2011,30(5):80-82
对《基于Kruskal算法的最短路径算法研究》一文中提出的方法进行探讨,通过构造实例论证了Kruskal算法并不能直接用于求解有向带权图的单源最短路径问题,并综合性地对基于最小生成树算法求解图的单源最短路径问题进行分析,通过构造实例最终得出最小生成树算法不适用于求解图的单源最短路径问题的结论. 相似文献
13.
程远 《渝西学院学报(自然科学版)》2011,(5):80-82,87
对《基于Kruskal算法的最短路径算法研究》一文中提出的方法进行探讨,通过构造实例论证了Kruskal算法并不能直接用于求解有向带权图的单源最短路径问题,并综合性地对基于最小生成树算法求解图的单源最短路径问题进行分析,通过构造实例最终得出最小生成树算法不适用于求解图的单源最短路径问题的结论. 相似文献
14.
《辽宁大学学报(自然科学版)》2017,(4)
最短路径问题一直是计算机等学科的热点研究问题,常应用于社交网、交通网等诸多领域.图规模爆炸式的增长导致传统单机环境下的存储、查询已无法满足大规模图的处理需求.提出一种基于Spark-Graph X平台的大规模图最短路径查询方法(LSGSP-SG):首先利用经典算法对大规模图进行分割并标记,将割点的信息记录在文本文件中,然后利用大数据平台Spark的Graph X框架进行迭代式分布计算并进行各个计算机节点的消息通信及同步,最后返回最短路径查询结果. 相似文献
15.
16.
在单一网络功能下节点间最短路径的研究基础上,提出基于多功能网的最短路径查询问题,给出一种基于贪心策略的查询算法来查询节点间在不同网络功能下的最短路径.利用多功能网对山东半岛城市群进行建模,分别查询城市群网络实现经济和信息两种不同功能时城市间的最短路径,并计算分析.研究结果表明,查询节点间在不同网络功能下的最短路径对于挖... 相似文献
17.
18.
导游电子化是旅游产业的发展趋势,最短路径搜索是电子导游系统的关键技术之一.经典的Dijkstra算法须花费大量时间用于计算最短路径以外的结点,从而影响了算法的速度.在分析景区结点分布特点和移动设备特性的基础上,对Dijkstra算法进行了优化,优化算法基于对景区结点进行区域划分,缩小了考虑结点的范围,在搜索时仅对相关区域内的结点进行处理,从而提高了算法的速度,最后对优化算法进行了正确性证明和性能分析. 相似文献
19.
Dijkstra算法是计算有向图中一个节点到其余各个节点最短路径的著名多项式时间算法,在交通规划、地理信息系统等方面有重要的应用。本文改进Dijkstra算法用于计算带有动态速度和代价约束的有向图中节点之间的最短路径,即有向图的节点之间除了静态的距离外,还有动态的速度和代价,例如城市交通中的高峰与非高峰时段影响速度/时间,收费与非收费路段影响代价;时间和代价在最短路径中由一个比例因子控制,通过调节该比例因子可计算节点间的最短时间/距离和最少代价的路径。该改进的算法被证明是可靠的,实验结果也表明了该算法的有效性。 相似文献
20.
基于启发式策略的最短路径算法 总被引:6,自引:0,他引:6
在讨论经典Dijkstra算法和启发式策略算法(A^*,矩形算法等)的基础上,提出一种基于Dijkstra算法的动态方向限制搜索算法用于求解道路网络中两节点之间最短路径.该算法结合人类的搜索思路和动态灵活的处理方式,对最短路径算法的搜索策略进行改进,动态改变搜索限制区域,减少计算时间.该算法不仅可以单独提高计算最短路径的效率,而且与其他算法结合起来还可取得更好的效果.实际结果证明动态方向限制搜索算法比经典Dijkstra算法减少近50%的搜索节点数和搜索时间. 相似文献