Dijkstra最短路径分析算法的优化实现

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

改进Dijkstra算法的城市道路最短路径仿真研究

本文在分析Dijkstra算法基础上,考虑城市路网的特点及该算法在路径优化中的不足,提出一种基于双向搜索的Dijkstra改进算法,它可以减少路网节点的搜索范围和计算复杂度。仿真结果表明,改进算法在最短路径搜索中可使候选节点数减少15%～25%,当节点越多这种减少越明显,可提高搜索路径的实时性。     

改进Dijkstra算法的城市道路最短路径仿真研究

本文在分析Dijkstra算法基础上,考虑城市路网的特点及该算法在路径优化中的不足,提出一种基于双向搜索的Dijkstra改进算法,它可以减少路网节点的搜索范围和计算复杂度.仿真结果表明,改进算法在最短路径搜索中可使候选节点数减少15％～25％,当节点越多这种减少越明显,可提高搜索路径的实时性.     

动态水深环境下的无人艇路径规划

针对D* Lite算法存在路径转折点多、难以进行轨迹跟踪控制、没有顾及动态水深变化等不足,该文引入水深危险度,进行安全路径的选优,以提高所规划路径的安全性,并采用视线检查算法和懒惰更新改进D*Lite算法进行路径规划,提出了LT-D* Lite算法.该文采用电子海图水深叠加潮汐水位构建动态水深模型,同时建立水深危险度代价函数对最优安全节点进行选择,平衡路径的安全性.算法在拓展节点过程引入视线检查算法,将节点拓展方式从八邻域拓展为任意角度方式并使路径平滑,通过动态水深调整后的浅水区域进行路径调整.仿真实验表明,该文所提出的算法具有规划路径短且路径平滑的特点,同时可引导无人艇避开浅水深区域,显著降低路径危险度.     

一种多出口室内应急疏散路径规划算法北大核心CSCD

针对多源多汇多路径问题若分别以多个出口为源点,通过多次直接调用Dijkstra算法求解,节点会被多次重复扩展,导致算法搜索效率过低的问题,该文结合Dijkstra算法的执行原理和特点,提出了一种解决多出口室内应急疏散路径规划的新算法。首先通过引入一个连接所有出口节点的虚拟节点作为源点来改变原始网络结构,将多源多汇多路径规划问题转化为单源多汇多路径规划问题;然后以虚拟节点为源点,直接调用Dijkstra算法来搜索源点到各个汇点的最优路径。该算法有效避免了多次调用Dijkstra算法带来的重复搜索节点问题,提高路径搜索效率。实验结果表明,该算法运行时间随着路网总节点数的增加而增加,与出口数关系不大;当出口数越多时,该算法较之现有算法效率提升越明显,具有较高的实用性。     

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

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

面向OSM数据的多模式路径规划方法

阐述基于OSM数据进行多模式路径规划的方法,首先从OSM数据中提取所需的道路信息,构建合适的道路网络模型和存储模型,然后对出行者习惯采用的不同代价标准进行分析,最后针对多种交通模式,采用最短路径算法,求解出两连通节点之间的最优路径。     

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

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

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

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

基于Dijkstra算法改进的海量数据最优路径计算方法研究与实现

针对传统Dijkstra算法在应用中存在的不足,提出一种面向海量数据的基于传统Dijkstra算法的最优路径搜索方法,以避免大量无用节点参与计算,严重制约计算效率。通过对路网关系制表来表达节点与路段的关系,解决使用相邻矩阵计算量大的问题。此外,利用监测得到的实时速度进行加权,实现最短时间路径的计算。     

空天网格化星间通视及路由路径规划算法

通信、导航、遥感一体的天基信息服务系统的建设将对跨境实时通信、动目标全球跟踪、灾害快速响应等提供有力保障,同时也对高效的网络通信,特别是卫星路由规划算法提出了新的要求。为优化通信链路,进一步降低时延,充分利用网格空间关系直视、编码计算效率高的优势,提出了卫星星座空间互联网格化计算方法。基于GeoSOT-3D(geographic coordinate subdivision grid with one dimension integer coding on 2nTree-3D)模型,构建了空天网格索引大表,并提出了一套通过查询网格通视情况来进行卫星通视分析以及星间路由规划的算法。通过仿真90/15/2的Walker星座,构建空天网格索引大表,进行星间通视分析、星间效率规划的实验验证与效率对比,结果发现,网格通视分析效率较传统算法提升2.2倍;基于预先建立通视大表的通视分析效率较传统算法提升20.9倍;网格化星间路由规划效率在最短距离约束下提升近25倍;在最小跳数约束下则提升约20倍。因此,该算法具有可行性与高效性,能显著提升星间通视及空间链路规划的计算效率。此外,该算法能够用于紧急通信、灾害预警、海上救援等方面,为卫星互联网建设作出贡献。     

Dijkstra最短路径算法优化策略

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

基于遗传BP神经网络模型的土地利用变化预测模型研究

针对已有的遗传BP神经网络土地利用变化预测模型存在BP神经网络隐层节点不易确定、创建过程烦琐等问题,本文利用输入层与隐藏层神经节点数量关系原理确定隐层节点,在Sheffield工具箱环境下进行遗传算法的编程,简化遗传BP神经网络土地利用变化预测模型的创建。结果表明,利用输入层和隐含层节点数量关系创建的遗传BP神经网络土地利用变化预测模型,可以实现土地利用变化的预测,而且在效率和精度上均优于传统BP神经网络模型,且操作简便。     

Transport Capacity Limit of Urban Street Networks

Network transport is an important aspect of geographical information science, transportation, complex networks, etc. Previous studies have shown that the transport capacity of street networks can be enhanced by improving routing algorithms. However, the upper throughput limit of street networks is unknown in detail. This article studies the transport process of networks and finds that any connected network has a maximum throughput depending on the topological and structural properties of the network. Based on this, the maximum throughput of street networks is obtained. Experiments show that when the street network remains unchanged, the maximum throughput of the street network is limited and is dependent on road capacity and average path length, regardless of adopted routing algorithms. Our findings suggest that the throughput of networks can be improved by increasing node capacity or decreasing average path length, but the maximum transport capacity of the network cannot be greater than the ratio of the sum of all the nodes' capacities to the average path length of the network, no matter what routing strategies are adopted. This study is expected to be a starting point for more sophisticated research in network transport, such as evaluating the inherent throughput of an urban street network.     

利用分区思路优化拓扑关系自动生成算法

空间数据拓扑关系的建立是GIS中研究的重要课题 ,它直接影响空间数据的空间关系的建立、空间数据的查询、空间数据网络分析等操作。作者在实际的软件设计过程中 ,在空间数据的自动求交、结点匹配等两部分中 ,通过分区思路减少了计算量 ,提高了空间数据拓扑关系自动建立算法的效率。     

自动搜索最小多边形算法的研究

多边形的自动搜索是ＧＩＳ空间分析的基本算法之一，同时也在地籍拆宗、导线网闭合环的闭合差计算等领域有着重要的作用。本文依据一般的图形数据结构，提出了一种结点标记的搜索算法，利用该算法可自动搜索出所有独立的最小多边形。     

应用局部拓扑修改提高GIS路径分析精度

针对现有路径分析算法中道路节点与路径分析的起点、终点不一致而导致的分析误差问题,提出了一种应用局部拓扑修改的方法实时将路径分析的起点和终点作为结点插入拓扑网的路径分析算法,并采用动态修改网格索引的方法提高了节点与链的检索速度。经实验比较,该算法在很大程度上减小了分析误差,提高了算法的实用性,而时间复杂度与Dijkstra算法相比控制在10-1s内。     

A spatially weighted degree model for network vulnerability analysis

Using degree distribution to assess network vulnerability represents a promising direction of network analysis.However,the traditional degree distribution model is inadequate for analyzing the vulnerability of spatial networks because it does not take into consideration the geographical aspects of spatial networks.This paper proposes a spatially weighted degree model in which both the functional class and the length of network links are considered to be important factors for determining the node degrees of spatial networks.A weight coefficient is used in this new model to account for the contribution of each factor to the node degree.The proposed model is compared with the traditional degree model and an accessibility-based vulnerability model in the vulnerabil-ity analysis of a highway network.Experiment results indicate that,although node degrees of spatial networks derived from the tra-ditional degree model follow a random distribution,node degrees determined by the spatially weighted model exhibit a scale-free distribution,which is a common characteristic of robust networks.Compared to the accessibility-based model,the proposed model has similar performance in identifying critical nodes but with higher computational efficiency and better ability to reveal the overall vulnerability of a spatial network.     

多尺度道路网的距离匹配算法研究

根据道路网折线的匹配特点,提出基于格网索引的折线——结点距离匹配算法,将复杂的折线与折线之间的几何相似度计算转换为求结点到折线距离的匹配方法,降低了计算复杂度,并通过建立格网索引来提高计算效率。在应用实例中,采用曲线拟合的最小二乘法确定算法的匹配容差和匹配成功率之间的关系,并通过与现有统计匹配算法比较,可知该算法效率高且匹配成功率较理想,能够满足多尺度道路网数据匹配的应用需求。     

GIS网络的TDN结构表示

分析了GIS网络的基本要素和网络关系，提出了完备表达网络的TDN数据结构，从时间和空间效率上进行了推演，并以试验验证了该结构的实用性。