论文部分内容阅读
网络图中最短路径的计算问题在图论中是一个经典的问题,一个最实际的应用就是在道路网络中进行路径分析,如在给定的道路网中,寻找起点到目标点的最佳路径问题。在本课题研究中,假设给定的道路网中节点和边不经常改变,即在稳定的道路网中进行最短路径分析。对一般的小规模路网的路径分析问题已有较为成熟的算法,而对大规模道路网的最短路径分析问题,经典的Di jkstra算法因为计算速度非常慢,故而这种经典算法并不适用。在近几年的时间里,针对大规模路网的路径分析问题,提出了许多新的快速算法,这些算法有个共同点,就是预先计算和存储辅助数据用于加速最短路径的查询。然而,在边为非负权重的图中,这些算法通常只考虑计算源点到目标点的最短路径简单问题,而实际问题并没有那么简单,因此,在此需要扩充一下研究问题的定义,设置从源点到目标点的所需要的时间作为边的权重,充分考虑路网中节点和边的属性信息。虽然当前已有根据此提出一些新的算法,但是这些算法并不是很有效。因此研究出一种新的算法是非常有必要的。在本文中,基于道路网节点和边实体的属性信息,对最短路径的分析提出了一种新的加速算法-HP (Hierarchy Partition)算法,这种算法包括如何对道路网的层次划分、如何在路网中构建辅助边、如何对同一层级上的节点进行排序、如何对节点进行抽样和最短路径的求解。实验数据从OpenStreetMap的镜像站点下载,在数据预处理阶段应用开源插件-ArcGIS Editor For OSM Data,安装嵌入ArcGIS中,应用此插件提供的功能对OSM原数据进行预处理,把初步处理好的数据,应用XML2RDF格式转换工具,把OSM数据转成RDF数据格式,并保存在RDF-3X数据库中。在CH算法和TNR启发下,对路网进行层次划分和构建辅助边,结合Reach算法,对实验数据抽样,并求出近似解。在实验过程中,采用5个实验数据,数据节点从5万到2000万,把实验数据分成10个数据集作为查询数据进行实验,在实验中分别比较HP算法、CH算法、Dijkstra算法和TNR算法在距离和路径查询效率。最后对整个实验结果进行了详细的分析,得出在预处理过程HP的空间消耗稍微比CH算法差,但是比其他的2种算法消耗要低得多,而在空间复杂度和时间复杂度上都比其他3种算法优越。