共查询到20条相似文献,搜索用时 78 毫秒
1.
汽车导航系统中最短路径是一定特殊性的搜索问题,不能简单套用图论中的最短路径问题的算法.在此运用Dijkstra算法的原理,利用逐步求证的推理方法,同时考虑进行最短路径计算所需的信息的完备性和教据的维护问题,分析其在汽车导航系统中的应用,并给出算法的改进策略. 相似文献
2.
3.
本文讨论了矢量地图下的最短路径问题,就矢量地图下最短路径寻优算法的实现进行了深入的研究,并应用于具体的城市道路环境中进行检验,取得了较好的结果. 相似文献
4.
5.
最短路径问题是图论中的一个典范问题,它被应用于众多领域.最短路径问题可以分成两类:单源最短路、所有顶点对间的最短路径.在研究图中最短路径问题上,Dijkstra算法是其中最为经典的算法之一,本文主要介绍所有顶点对间的最短路径问题,提出了一种更高效的新的所有顶点对间的并行算法.最后利用多线程技术对给出的并行算法进行了实现. 相似文献
6.
公路交通管理中,最短路径是进行车辆路径优化的基础.论文在简单分析了一些经典的最短路径算法和这些最短路径算法单独应用于车辆路径优化存在的局限性的基础上,提出了一种改进A*算法的方法[1~2],并用它来解决城市间道路网中实时最短路径问题,并以实例加以阐述. 相似文献
7.
研究交通道路中的最短路径优化问题,由于城市道路拥塞严重,在导航过程中,为了尽快达到日的地,必须选择最短路径进行行驶.传统搜索算法计算复杂度高,寻优效率低,不利于实际优化.为解决最短路径优化问题,提出了一种蚁群算法的GIS中的最短路径优化方法.将路径的起点当成蚁群的巢,终点当成蚁群要寻找的食物,蚂蚁通过信息法指导搜索方向,并通过蚂蚁之间的相互协作达到终点.仿真结果表明,提出的优化方法降低了计算复杂度,更快地找到最短路径,提高了找到最短路径的平均正确率,为解决GIS中的最短路径优化问题提供了一种新的有效途径. 相似文献
8.
针对点的可见性计算这一计算几何中的基础问题,提出一种支持任意查询点的可见多边形快速计算的基于多边形Voronoi图的点可见性算法.以与Voronoi骨架路径对应的Voronoi通道概念,以及相应的局部最短路径概念为基础,按照深度优先策略对Voronoi图进行遍历,在计算Voronoi骨架路径的同时计算局部最短路径,并基于局部最短路径计算所遍历的多边形边的可见部分.该算法可以处理“带洞”多边形,而且只对多边形进行局部访问;对于“带洞”多边形,由于该算法的数据结构比较简单、剖分空间合理且易于实现,因此仅需O(n)空间和O(nlgn)预处理时间.最后给出了在三维室内虚拟场景设计与漫游系统中的应用实例,结果表明文中算法是实际可行,且运行时间与点的可见多边形的边数和多边形的边数均呈线性关系. 相似文献
9.
附有条件的最短路径算法 总被引:1,自引:0,他引:1
厍向阳 《计算机应用与软件》2009,26(5)
分析目前最短路径算法特点和存在问题,并讨论附有条件的最短路径问题.以邻接矩阵为数据存储结构,在迪杰斯特拉(Dijkstra)最短路径算法的基础上,提出了附有条件的最短路径算法.最后,通过实例进行算法测试和比较.算法测试表明:附有条件的最短路径算法是完全可行和有效的. 相似文献
10.
从分析城市道路网地理相关性特征入手,研究利用道路网的空间特性信息来解决道路网中两点间的最短路径问题.通过建立体现道路网空间特性的数据模型,根据两点间直线距离最短的原理,提出一种道路网两点间最短路径的算法,利用VC 进行了算法实现和最短路径的可视化显示.实验结果证明:利用空间特性信息可以有效地减少最短路径的搜索花费,同时算法的实现和最短路径的可视化不须依赖地理信息系统平台,具有较好的可移植性和实用性. 相似文献
11.
一种新的Kth最短路径搜索算法 总被引:1,自引:0,他引:1
借助于“背离”路径的概念,论文在2nd最短路径搜索算法的基础上提出了一种新的Kth最短路径搜索算法,并将其应用至实际环境中。通过K-1次2nd最短路径搜索算法的迭代,该算法可以求出网络中任意两个给定节点之间的Kth最短路径,2nd最短路径搜索算法在计算上具有简单性,因而也同样具有简洁、快速的特点。 相似文献
12.
K(≤3)条渐次短路径搜索算法的研究 总被引:2,自引:0,他引:2
Dijkstra算法是经典的最短路径搜索算法。该文在Dijkstra算法的基础上,提出了在单限制多权值的条件下k(≤3)条渐次短路径的搜索算法。算法的实例表明,该算法切实有效。 相似文献
13.
目前针对“k(≤3)条渐次最短路径的问题”国际上尚无一种有效的解决方案,本文基于最短路径算法及背离路径的定义提出了一种递归计算方法,能够有效地解决某些实际问题中k条渐次最短路径的计算。对于算法中的环路问题,文中介绍了相应的方法予以消除。算法的复杂度分析及仿真实验表明本算法具有较好的性能。 相似文献
14.
15.
16.
17.
最优路径规划是道路交通导航系统中很重要的一个功能。将路径规划问题转化为以加权路径网的以路径长度与通行时间的线性组合为目标函数的优化问题,并提出一种改进的蚁群算法应用于该问题,使规划的路径更加符合各种要求。仿真结果表明,该算法能在较短时间内根据不同需求规划出较优的路径,是行之有效的方法。 相似文献
18.
19.
针对三维飞行器在动态环境下使用三维A*算法进行局部仿真时,环境信息未知,存在冗余点和拐点,导致收敛时间长、路径节点扩展代价大、易陷入局部最优问题,提出一种基于全局与局部相结合的动态三维A*寻路算法。此算法首先改进评价函数的权值系数动态分配,减小路径冗余点和拐点,从而降低算法耗时,缩短路径长度;其次改进路径生成策略,有效提高算法效率,避免陷入局部最优,进一步缩短路径长度,从而实现飞行器在三维动态环境中的路径规划。将改进后的算法进行仿真对比,仿真结果表明,改进后的算法路径更加合理,算法耗时和路径长度更短。 相似文献
20.
Floyd算法是求解网络中任意两点之间最短路的高效算法,文章给出了在不含负回路的网络中Floyd加速算法及优化方法,并构造了求解最短路径的序号矩阵。算法分析和计算实例表明,优化后的Floyd加速算法迭代速度快,计算量大大减少,路径寻找简单、直观。 相似文献