首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到19条相似文献，搜索用时 292 毫秒
1.
王华 《测绘工程》2014,(6):31-32
最短路径是现代物流配送研究中热点问题之一,在分析传统启发式搜索算法的基础上,针对算法在路径优化中存在的不足,提出基于二叉树优化启发式搜索算法（A＊）实现所需结点之间最短路径查询,在引入已知的全局信息条件下选择下一个被检查的结点,并根据用户给出的起始顶点与目标顶点以及搜索的角度查找最短路径,从而搜索可能性较大的结点,提高搜索过程的效率.实验表明,基于二叉树的A＊比A＊效率提高11％～26％.  相似文献   

2.
在最短路径操作算法的基础上 ,给出了最短路径操作不确定性的算法及流程图。实例演算了不确定性的传播模型。研究结果表明 ,最短路径操作结果的绝对不确定性 :(1)与最短路径操作经过的点数成正向关系 ,更进一步 ,最短路径的几何路径曲率越大 ,最短路径操作带来的不确定性越大。 (2 )与最短路径经过的各相邻顶点间的距离长短没有直接关系 ;(3)与经过的各顶点的误差成正向关系。GIS中进行最短路径操作时减小操作结果不确定性的方法是 :(1)提高最短路径经过顶点的点位精度 ;(2 )减少最短路径经过顶点数目  相似文献   

3.
在最短路径操作算法的基础上 ,给出了最短路径操作不确定性的算法及流程图。实例演算了不确定性的传播模型。研究结果表明 ,最短路径操作结果的绝对不确定性 :(1)与最短路径操作经过的点数成正向关系 ,更进一步 ,最短路径的几何路径曲率越大 ,最短路径操作带来的不确定性越大。 (2 )与最短路径经过的各相邻顶点间的距离长短没有直接关系 ;(3)与经过的各顶点的误差成正向关系。GIS中进行最短路径操作时减小操作结果不确定性的方法是 :(1)提高最短路径经过顶点的点位精度 ;(2 )减少最短路径经过顶点数目  相似文献   

4.
文章针对Dijkstra和Floyd算法特点及在智能运输中的特点,将两种算法结合起来,形成求解物流配送中两点间最短路径的优化算法-混合算法.该方法用Floyd计算多对顶点之间的最短路径,在路径中少数顶点之间的邻接关系发生变化时,利用Dijkstra计算这些顶点之间的最短路径,加上其余部分路径就得到该图中各对顶点之间的新的最短路径,在约束条件下最终求出各点间最短路径.实验证明,混合算法比Dijkstra及Floyd效率提高11％-20％.本文研究结果可对物流配送中最短路径的选择有所帮助.  相似文献   

5.
GIS中最短路径算法的改进实现   总被引：14，自引：1，他引：13  
针对GIS中网络拓扑图的一般特点和对网络分析实时性的要求,以Dijkstra最短路径算法为理论基础,采用快速排序和插入排序相结合的方式,使用地址排序的方法,改进原有最短路径算法中对最小权值的顶点的搜索策略,提出一种高效的实用的Di-jkstra最短路径算法的实现方法.  相似文献   

6.
最短路径求解是导航系统的核心问题。以Dijkstra算法为基础,研究一种求次优路径的方法。通过对路线权值删除的方法和对路线权值赋值的方法,改变路线图上各路段的权值,重复多次调用Dijkstra算法求得起始点到目标顶点的k条最短路径和k次优路径。算法在C#环境中实现,以某校园道路数据为实验。实验表明,通过结合删边方法和赋值方法,可以提供满足多种不同需求的次优路径。  相似文献   

7.
快速Dijkstra最短路径优化算法的实现   总被引：12，自引：1，他引：12  
在分析已有Dijkstra算法的基础上,提出快速Dijkstra最短路径优化算法.该算法是将提高时间效率放在第一位,以十字链表结构记录顶点(Vertex)和边(Edge)为基础,采用顶点分区和记录绝对地址来优化Dijkstra算法的方法.  相似文献   

8.
针对传统最短路径算法存在的一个不足,即算法的时间复杂度与顶点数目的平方成正比,当顶点数目增加时,其运算速度会显著降低,该文提出了一种改进的双向A~*算法,其主要思想为利用中间列表双向搜索目标,在搜索的方向上将之前算法中的"目标点"变为"目标面"。实验数据表明,相比较传统的A~*和Dijkstra算法,该文提出的双向A~*算法在搜索速度上更快,特别是当顶点数目较多时,该算法仍旧能保持较快的计算速度。  相似文献   

9.
最短路径问题作为GIS分析中的一个主要内容而被广泛深入地进行研究。本文在设计一种网络数据结构的基础上, 通过一种基于节点与弧段标号的最短优先路径搜索策略, 设计并实现了一种结构简单、便于理解并且高效的最短路径求解算法。  相似文献   

10.
单源最短路径算法的图示教学设计与实践   总被引：1，自引：1，他引：0  
单源最短路径是GIS网络分析的一个重点内容,对GIS、空间信息技术等相关专业的学生来讲,由于经典的最短路径算法(Dijkstra)描述较抽象,让学生掌握单源最短路径算法的本质思想较难。提出用图示教学法来教授GIS中单源最短路径算法的基本原理和思路,详细介绍了图示表示的过程,可以为最短路径算法及其应用的教学过程提供参考。  相似文献   

11.
基于＂邻接点＂概念,研究了最短路径的快速计算方法,并利用VB语言编写了计算所需的核心模块,最终实现了从一个节点到另一个节点的所有最短路径的快速查询和显示。  相似文献   

12.
最短路径问题是地理信息系统的关键问题,传统Dijkstra算法在求解节点间最短路径时,对已标识节点以外的大量节点进行了计算,从而影响了算法的速度。因而对其算法进行优化是很有必要。本文在对传统Dijkstra算法分析的基础上,对其进行了优化,优化算法只对最短路径上节点的邻居做了处理,而不涉及其他节点,并利用Visual C++6.0开发平台编程进行了实验。实验表明,该算法是行之有效的。  相似文献   

13.
Human beings’ intellection is the characteristic of a distinct hierarchy and can be taken to construct a heuristic in the shortest path algorithms. It is detailed in this paper how to utilize the hierarchical reasoning on the basis of greedy and directional strategy to establish a spatial heuristic, so as to improve running efficiency and suitability of shortest path algorithm for traffic network. The authors divide urban traffic network into three hierarchies and set forward a new node hierarchy division rule to avoid the unreliable solution of shortest path. It is argued that the shortest path, no matter distance shortest or time shortest, is usually not the favorite of drivers in practice. Some factors difficult to expect or quantify influence the drivers’ choice greatly. It makes the drivers prefer choosing a less shortest, but more reliable or flexible path to travel on. The presented optimum path algorithm, in addition to the improvement of the running efficiency of shortest path algorithms up to several times, reduces the emergence of those factors, conforms to the intellection characteristic of human beings, and is more easily accepted by drivers. Moreover, it does not require the completeness of networks in the lowest hierachy and the applicability and fault tolerance of the algorithm have improved. The experiment result shows the advantages of the presented algorithm. The authors argued that the algorithm has great potential application for navigation systems of large-scale traffic networks.  相似文献   

14.
Human beings' intellection is the characteristic of a distinct hierarchy and can be taken to construct a heuristic in the shortest path algorithms.It is detailed in this paper how to utilize the hierarchical reasoning on the basis of greedy and directional strategy to establish a spatial heuristic,so as to improve running efficiency and suitability of shortest path algorithm for traffic network.The authors divide urban traffic network into three hierarchies and set forward a new node hierarchy division rule to avoid the unreliable solution of shortest path.It is argued that the shortest path,no matter distance shortest or time shortest,is usually not the favorite of drivers in practice.Some factors difficult to expect or quantify influence the drivers' choice greatly.It makes the drivers prefer choosing a less shortest,but more reliable or flexible path to travel on.The presented optimum path algorithm,in addition to the improvement of the running efficiency of shortest path algorithms up to several times,reduces the emergence of those factors,conforms to the intellection characteristic of human beings,and is more easily accepted by drivers.Moreover,it does not require the completeness of networks in the lowest hierarchy and the applicability and fault tolerance of the algorithm have improved.The experiment result shows the advantages of the presented algorithm.The authors argued that the algorithm has great potential application for navigation systems of large-scale traffic networks.  相似文献   

15.
Turn restrictions, such as ‘no left turn’ or ‘no U‐turn’, are commonly encountered in real road networks. These turn restrictions must be explicitly considered in the shortest path problem and ignoring them may lead to infeasible paths. In the present study, a hybrid link‐node Dijkstra's (HLND) algorithm is proposed to exactly solve the shortest path problem in road networks with turn restrictions. A new hybrid link–node labelling approach is devised by using a link–based labelling strategy at restricted nodes with turn restrictions, and a node‐based labelling strategy at unrestricted nodes without turn restrictions. Computational results for several real road networks show that the proposed HLND algorithm obtains the same optimal results as the link‐based Dijkstra's algorithm, while having a similar computational performance to the classical node‐based Dijkstra's algorithm.  相似文献   

16.
节点重要性对大规模道路网下最短路径的计算有着重要影响。本文提出了顾及节点重要性的最短路径估计方法,该方法基于Critic方法与复杂网络理论评价节点的重要性,结合限制策略实现网络划分,通过层次结构网络的构建,实现大规模道路网数据的有效化简和最短路径的快速有效计算。试验结果表明,该方法能够使中心节点均衡地分布于网络,更好地均衡划分后子网络的规模;随着限制参数的增大,网络规模逐渐降低,查询精度最高达到1.026,相比于单一指标和无限制参数的方法,本文方法显著降低了网络的规模,在最短路径的近似计算上保持了较高的准确性,为大规模复杂网络的近似分析提供分析思路。  相似文献   

17.
文中以阜新市为例较为详细地讨论在公交线路网络中的拓扑结构建模,及基于公交线路网的弧段与节点间地理相关性的拓扑特征;并以MapInfo为平台,运用MapBasic语言,采用经典的Dijkstra最短路径算法,实现对阜新公交站点查询、公交线路查询、两站点间的最优路径查询功能.  相似文献   

18.
高吉 《北京测绘》2009,(2):16-18
最短路径问题是地理网络分析中的重要问题之一，具有重要的应用价值。搜索最短路径的方法很多，在研究了各种方法后，本文提出了在ArcGIS矢量图中搜索最短路径的新方法。首先，提取经过ArcGIS简单处理的矢量图的信息，然后，借助Floyd算法，用MATLAB建模来提取节点间的最短路径，最后根据模型运算的结果在矢量图中绘出最短路径。试验证明，该方法操作简单，效果良好。  相似文献   

19.
最短路径算法:分类体系与研究进展   总被引：76，自引：3，他引：76  
陆锋 《测绘学报》2001,30(3):269-275
最短路径算法是计算机科学与地理信息科学等领域的研究热点。本文首先讨论了平面图的搜索策略，然后从问题类型、网络类型和实现方法3方面对最短路径算法进行了系统的分类，从理论上比较了近年来所提出的各具有较高效率的串行最短路径算法的时间复杂度，并对国内外一些相关研究进行了综合评述，结合城市交通网络的实验结果，作者对几种应用最为广泛的串行最短路径算法的运行效率进行了分析和评价，最后对最短路径算法在实时化和并行化方面的发展进行了讨论。  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号