城市路网的最短路径并行求解

随着当前城市规模的不断扩大,交通网络变得越来越复杂,计算最短路径问题不仅要消耗大量的空间资源,同时也花费了更多的时间资源。为了提高最短路径求解的实时性,基于城市小区将复杂网络进行化简,在各个小区中寻找代表节点,将其他无关的节点看做透明的不参与计算,保持原有网络的特性。然后采用并行搜索算法及分层思想进行路径查询,并且在PC机群的并行环境下对其进行实现。实验结果表明,该方法在运行时间和内存空间分配都具有明显的优势,具有良好的实用性。

Solving the Shortest Path in Parallel of City Road Network

With the current scale of urban expansion and transport network more complex,the computation of the shortest path problem will consume more time and spatial resources.In order to have a more efficient real-time,simplify the complex network based on the city community.To maintain the original characteristics of network,in every district to find the representative node,and other nodes as transparent has nothing to do.Then do wayfinding used layered calculation of thought and parallel search algorithms.The exp...