网络超点模型数据结构设计与路径分析算法

传统网络图模型无法满足交通网络表达的需求,结点-连接模型与伪二重图等模型可以通过增加结点或孤段的数量来表达部分交通限制信息,但会导致查询代价的增加.网络超点模型通过结点的限制矩阵,表达交通网络中的交通限制信息,可以较好地解决了这一问题.论文针对超点模型及所表达的交通限制信息对最短路径算法加以改进,设计了基于超点模型的数据结构,并编程实现基于超点模型的最短路径查询方法.     

顾及步行习惯的室内导航网络及其生成算法

室内导航网络是实现室内路径规划和导航的基础。针对现有室内导航网络存在拓扑连通结构不合理、生成路径几何形态不自然等问题,本文依据人类长期以来形成的“抄近路”习性及“避碰”安全需求,提出了一种符合人行走习惯的室内导航网络及其自动生成算法。该导航网络将室内可通行空间划分为普通房间和走廊,普通房间内网络映射为房间结点与门结点的直线连接;形状复杂的走廊空间则依据空间尺度和凹凸性被细分为狭窄走廊空间和开阔走廊空间,狭窄走廊空间以中轴线作为路线,开阔走廊空间则将门结点和通道口结点连接形成完全图;最后将房门结点连接到走廊路线,形成完整室内导航网络。试验结果表明:该模型及其生成算法能够依据室内空间尺度对复杂通行空间进行合理分区,生成与空间特征一致的导航网络结构,使得规划生成的最短路径形态更符合人们的行走习惯。     

公交线路中最优路线的查询算法设计

在一个公共交通网络中寻找两个结点间的一条最佳路径,使之换车次数最少。利用GIS地理分析的特性,设计了合乎乘客心理的最优路线查询算法。本算法是基于广度优先搜索提出公交路线最短路径选择的算法。该算法对图的搜索方法提出了一个新的思路,经模拟试验,算法简单合理,运算速度快,容易在计算机上实现。     

基于道路网络分析的Voronoi面域图构建算法

提出一种基于网络分析的Voronoi面域图和加权Voronoi面域图构建算法。鉴于道路网络在城市中心地、公共设施引力传导与功能覆盖上的重要作用,采用网络最短路径距离分析和最短路径时间分析构建的Voronoi面域图可以模拟出中心功能的辐射影响范围空间划分的实际情形,进而为空间分析和空间优化提供有力支持。算法过程主要包括:设施邻近道路结点检索和分界结点计算;基于网络最短路径分析Dijkstra算法和分界结点计算的网络Voronoi划分;基于空间离散化、邻近道路分析的空间Voronoi划分及其矢量化处理算法。计算实验结果表明本文提出算法可靠和高效,能够模拟出具有预期精度和形态复杂的网络Voronoi面域图形。     

基于水流扩展思想的网络空间Voronoi图生成

Voronoi图是地理空间设施分布特征提取的重要几何模型,基于不同的空间距离概念可建立不同的Voronoi图。本研究顾及城市网络空间中设施点的服务功能及相互联系发生于网络路径距离而非传统的欧式距离的事实,针对网络空间Voronoi图模型,建立一种网络空间Voronoi图生成的栅格扩展算法。首先对图结构的边目标剖分为细小的线性单元,称作网络空间的栅格化,引入水流扩展思想,将事件点发生源视为“水源”,以栅格单元长度为扩展步长,让水流方向沿着网络上的可通行路径同时向外蔓延,直至与其他水流相遇或者到达边的尽头。该算法可方便地加入网络图结构中的多种约束,如街道边的单向行驶、结点的限制性连接等实际空间限制条件。通过大规模实际数据的“数字城市”POI点服务范围的试验表明该算法的效率高。     

汽车自导航系统中加入道路转向限制的最短路径算法

最短路径问题是交通网络分析中的一个重要问题，也是交通地理信息系统中的一个研究热点。国内外大量专家学者对此问题进行过深入研究。最短路径问题可分为单源最短路径问题及全源最短路径问题两种。其中，单源最短路径问题更具有普遍意义。单源最短路径问题的算法有很多种，代表性的有基于邻接矩阵的Dijkstra算法、最大相关边法、最大相关点法，基于邻接表的Dijkstra算法、A*算法等等；纵观该方向的研究状况，人们对最短路径分析的分类及其实现算法和应用研究较多，而对交通中的限制条件研究较少。     

利用组合技术的迪杰斯特拉算法改进探讨

最短路径分析是物流配送最基本的网络分析,等价于图论中的结点间求解最短路径的问题。本文在研究迪杰斯特拉算法基础上,基于组合技术对该算法进行改进。首先利用图的节点——弧段联合结构;其次搜索方法改为双向搜索;最后对扫描点按其所在边的权值进行排列。实验表明改进算法运行效率较高。     

Dijkstra最短路径算法优化策略

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

基于CNGI的政府地理信息系统建设与应用技术研究

介绍了我国首个基于CNGI的地理信息系统移植和建设情况,针对CNGI与IPv6的技术特点开展了新的地理信息应用技术研究,并以政府地理信息系统“地学之窗”为基础开发了GIS应用示范系统,为下一代网络环境下地理信息系统技术开发和应用建设奠定了一系列技术基础。     

组件与服务耦合的地学模型集成方法与实现

传统的空间信息处理建模工具,如ArcGIS ModelBuilder,聚焦于地理空间信息处理算子的组合建模。“模型网”的提出对已有的空间信息处理建模工具提出了新的挑战,一方面,现有的空间信息处理建模工具需要能够支持网络环境,支持空间信息服务的即插即用;另一方面,服务需要与复杂地学模型耦合,支持基于时间步长的地学模型运行。针对组件与服务并存的现状以及异构模型和算法兼容性差等问题,提出了组件与服务耦合的地学模型集成方法;并从“模型即服务”和模型集成需求出发,提出了基于WebSocket协议发布地学模型的新方法,实现了基于时间步长的地学模型在线共享。采用科学工作流技术实现了遵循国际开放地理空间信息联盟（Open Geospatial Consortium,OGC）标准的空间信息服务、基于WebSocket协议的地学模型服务、遵循OpenMI开放建模接口规范的模型组件集成,具有逻辑一致、物理分隔、执行可控等特点。利用该方法将传统的空间信息处理建模工具拓展为地学模型集成工具,并应用于具体案例中,验证了方法的可行性。     

最短路径算法的改进及其实现方法

最短路径分析是 GIS最基本的网络分析功能。Dijkstra算法是目前公认的较好的最短路径算法。文中从节约存储空间 ,提高运算速度出发 ,在 Dijkstra算法基础上 ,对相关边算法进行改进 ,提出邻接结点算法 ,并给出算法的面向对象的实现方法     

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

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

面向大规模道路网的最短路径近似算法

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

基于栅格数据的最优路径算法分析与设计

最优路径分析是GIS中基本空间分析之一,迄今为止,国内外出现不少关于最短路径/最优路径算法的研究,但其数据模型主要以矢量数据模型或网络模型为主,而建立在栅格数据模型上的最优路径算法的相关研究较少。基于栅格的最优路径算法是一些专业应用模型的基础,如道路通达度模型、城市引力模型、洪水演进过程模型等,其算法设计非常重要。本文在前人的研究基础上,提出一种用于计算栅格最优路径的算法,对其计算过程进行了详细的分析与描述,并根据实验结果总结了其优点和缺点。     

A fast algorithm for finding K shortest paths using generalized spur path reuse technique

The problem of finding the K shortest paths (KSPs) between a pair of nodes in a road network is an important network optimization problem with broad applications. Yen's algorithm is a classical algorithm for exactly solving the KSP problem. However, it requires numerous shortest path searches, which can be computationally intensive for real large networks. This study proposes a fast algorithm by introducing a generalized spur path reuse technique. Using this technique, shortest paths calculated during the KSP finding process are stored. Accordingly, many shortest path searches can be avoided by reusing these stored paths. The results of computational experiments on several large‐scale road networks show that the introduced generalized spur path reuse technique can avoid more than 98% of shortest path searches in the KSP finding process. The proposed algorithm speeds up Yen's algorithm by up to 98.7 times in experimental networks.     

GNSS大网双差模型并行快速解算方法

针对GNSS大网数据采用双差模型解算时存在时效性差的问题,提出了一种改进的独立双差观测值构建与独立基线并行解算的方法,采用并行技术实现多核并行与网络多节点并行的双层自动快速解算策略。通过对约375个IGS站1周的观测数据进行处理,改进的独立双差观测值选取方法比传统路径最短方法所选的单天全网独立双差数据平均多了53万个,E、N、U方向坐标重复性平均提升了14.0%、12.9%和29.2%。采用不同解算策略的计算结果表明,4台普通计算机的并行计算比传统串行方案的计算效率提升了14倍左右,如375个测站采用改进观测值构建方法的4节点并行方案仅需要35.62min,显著提高了整网双差的解算效率。     

基于调和模型的连续Hopfield神经网络次优图像复原

本文提出了一种基于调和模型的连续Hopfield神经网络正则化次优图像复原算法。针对传统正则化图像复原由于"模糊矩阵"和"高通滤波器"规模庞大而带来的复原过程中占用存储资源多的问题,提出了一种基于部分图像信息的次优复原算法,该算法能在性能下降不大的前提下,较好地解决传统复原资源消耗问题。同时算法采用由梯度算子生成的调和模型作为正则项,能在复原的同时保留图像边缘。仿真结果表明了算法的有效性。     

在ArcGIS矢量图中搜寻最短路径的实现

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

交通运输最短路径分析系统的设计与实现

针对目前交通运输效力发挥不足的问题,研究道路网络模型构建和道路数据库设计,探讨分析交通运输最短路径分析流程,基于Dijkstra算法的基本原理,设计实现交通运输最短路径分析系统,从而优化运输资源配置,实现高质高效的交通运输。