基于转向限制和延误的双向启发式最短路径算法

提出了基于节点的交通网络拓扑关系模型,描述交通网络的物理连通性以及逻辑连通性;根据对偶图的思想,定义搜索节点结构,处理交叉口转向限制和延误;改进传统的Dijkstra算法,提出了基于搜索节点的双向启发式A*算法,使用二叉堆优先级队列存储扩展节点,RB-tree存储标记节点。实验表明,本算法在效率和结果两方面都能满足车辆导航系统路径规划的要求。     

车载导航系统中顾及道路转向限制的弧段Dijkstra算法

路径规划作为组成车载导航系统的核心模块,其效率对整个系统有着至关重要的影响,传统路径规划常用的Dijkstra算法是根据道路“有向图”中的节点进行计算,相关的交通属性附加在道路节点上,事实上,道路转向限制不仅与节点（交叉口）有关,而且与相连的2条道路弧段有关,若要用节点表达道路转向限制,需要把2条弧段间的转向关系转换为相邻的3个节点之间的关系。这种转换增大存储空间和转换时间的开销,还增加了搜索的复杂度。为了解决这一问题,提出将原来附属于节点上的转向关系转移到相应的弧段上,用节点-弧段关系表达网络的连通性,用弧段-弧段转向关系表达交叉路口的转向限制,在此基础上,提出了一种顾及导航转向限制的弧段Dijkstra算法,试验表明,该算法能够有效地进行顾及道路转向限制的路径规划。     

交通限制条件下的最短路径算法分析与优化

通过对交通网络本身的特点及要求的分析与研究，介绍了一些适合道路网的经典最短路算法和数据存贮模式，探讨了在交通网络路线优化过程中需要特别处理的几个问题，如路口延误、禁行状态等，并在理论上给出了相应的解决方案。最后给出了一个路径搜索的实例。     

车辆导航系统中最短路径计算的数据模型

在自主车辆导航系统中如何实现符合现实状况的大范围的最短路径查询，对道路等级、道路通行条件、转弯规制等限制进行抽象，建立了模拟现实道路网络的交通仿真模型：对于大数据量交通网(全国范围)的路径计算，提出按道路等级分层建立拓扑网和分区域建立区域小型拓扑网的解决方案。     

交通限制条件下的最短路径算法分析与优化

通过对交通网络本身的特点及要求的分析与研究,介绍了一些适合道路网的经典最短路算法和数据存贮模式,探讨了在交通网络路线优化过程中需要特别处理的几个问题,如路口延误、禁行状态等,并在理论上给出了相应的解决方案.最后给出了一个路径搜索的实例.     

顾及转向延误的时间依赖A*最短路径算法

现有的动态路径规划算法通常只考虑当前时刻交通信息,而忽略了路段行程时间依赖于进入该路段的时刻这一现实。而且,转向延误的存在使得传统的基于节点标号的最短路径算法不再有效。本文建立了基于路段的时间依赖网络模型,将转向延误时间引入到FIFO（先进先出）条件的定义中,并给出了满足FIFO条件的路段到达时间和转向延误时间计算式。以此模型为基础,并通过将时间因子引入到启发式评价函数中,发展了基于路段标号的时间依赖A*最短路径算法。实验表明,所提出的算法能预测并回避即将发生的交通拥堵,有效节省用户的出行时间。而其平均计算时间仅比传统算法增加了10%左右。此外,由于不再需要进行频繁的路径重优化,该算法能大幅提高路径规划的整体效率。     

顾及复杂路口交通规则的最短路径算法

基于真实道路的通行状况,分析了一些通常最短路径计算中难以处理的复杂交通路口状况,提出了相应的解决方案。     

一种基于最短优先的最短路径算法的实现

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

最短路径问题的一种改进算法

最短路径分析是ＧＩＳ最基本的网络分析功能。迪杰斯特拉算法是目前公认的较好的最短路径算法。文中从节约存储空间、提高运算速度出发, 在该算法的基础上, 采用点弧联合结构表达图, 提出节点的最大邻接深度概念及相邻节点低值传递方法, 实现最短路径的自动判断与提取, 并给出算法的实现方法。     

Dijkstra最短路径算法优化策略

从分析经典Dijkstra最短路径算法出发,找出影响其效率的关键步骤:存储空间和时间效率,并结合当前已有的各种优化算法,总结出Dijkstra最短路径算法的优化策略:相关边优化策略、相关邻接结点优化策略、结点分类优化策略、权值排序优化策略、结点排序优化策略和单链结点剔除优化策略。最后,以实例运算表明优化策略是有效的,既节约了存储空间又提高了时间效率。     

最短路径算法用于城市公交出行路径最优化

介绍了经典Dijk st ra算法的主要思想快速实现方法，指出了公交网络不同于一般的道路网络的特点，给出了选择公交出行路径的算法思想。     

网络最短路径的地图代数栅格算法

在阐述网络分析和最短路径算法的现状的基础上,以地图代数为理论支撑,介绍了地图代数对于网络元素的表达,探讨另外一种途径的网络最短路径分析—基于栅格数据的最短路径分析,重点讨论了基于地图代数的网络数据模型、栅格路径距离计算方法,在此基础上论述了求取最短路径的栅格方法的具体过程。最后,通过算例证明栅格途径的网络分析有其独特的优势。     

GIS中最短路径算法的改进实现

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

Dijkstra最短路径算法的一种高效率实现

在已存在的一些最短路径算法测试总结的基础上,根据ＧＩＳ中网络计算的实际情况,从网络结构的拓扑表示以及Ｄｉｊｓｔｒａ算法中快速搜索技术的实现入手, 一种Ｄｉｊｋｓｔｒａ最短路径算不的高效率实现方法。     

VC环境下最短路径算法的实现

设计了一种方便查找及显示最短路径的数据结构,对仅研究计算一条最短路径的Dijkstra算法加以了改进,并在VC下实现一个顶点到另一个顶点的所有最短路径的查找。     

GIS城市道路最短路径算法研究

本文紧密结合城市公交的特点,利用改进Dijkstra算法开发出一个针对城市道路系统的最短路径自动搜索信息系统,该系统通过在ArcGIS环境下建立空间数据库和属性数据库,在VB环境下利用改进Dijsktra算法对McObjecta控件进行二次开发而设计完成,能在0.20s完成500多个交叉口的计算并找出其最短路径,是一种...     

Dijkstra 最短路径算法的一种高效率实现

在已存在的一些最短路径算法测试总结的基础上,根据ＧＩＳ中网络计算的实际情况,从网络结构的拓扑表示以及Ｄｉｊｋｓｔｒａ 算法中快速搜索技术的实现入手,提出了一种Ｄｉｊｋｓｔｒａ 最短路径算法的高效率实现方法。     

基于正六边形格网的最短路径算法

本文在分析了现有算法的一些不足之处的基础上,结合正六边形的特点及水流扩散思想,提出了基于正六边形格网的最短路径分析算法。该算法在最短路径搜索过程中,对同一正六边形格网而言,它至起点的累计代价值,不需要进行数据比较和修正。与经典的Dijikstra算法相比,该算法大大节约了搜索的时间。     

GIS网络分析中最短路径的实现

本文提出了一种基于矢量角度的最短路径搜索算法,设计出一种类似于面向对象的数据存储结构来存储网络图中的节点及弧段对象,在最短路径的搜索上引入矢量夹角标量值作为搜索因子,充分利用了网络图中各点元素和线元素间的拓扑关系,提高了搜索的趋势性,同时还考虑了各弧段的长度值(或权值),较好的将网络图中对象的空间信息和属性信息相结合。     

最简单路径寻找方法研究

许多认知研究表明,路径指令的复杂性和形式在人类导航中和路径的长度一样重要。在很多情形下,我们所需要的不是到达目的地的最短路径,而是一条最简单路径,也就是容易描述、理解、记忆或者执行路线的导航指令。大多数自动导航系统都依赖于计算最短路径问题的解,而不是找到最简单路径。本文在分析人们对道路转向的认知研究基础上,采用了适合道路转向的路段-链数据模型,并从权重函数选择、算法具体实现和算法分析三个方面具体论述了最简单路径算法的主要思想和具体实施。