题目：基于城市路网最短路径并行搜索算法的研究

随着当前城市规模的不断扩大，交通网络越来越复杂，出现了动态性和大规模性的新特征。对新特性网络的最短路径问题研究变得更有现实价值。与传统小规模网络相比较，大规模网络中会出现成百上千甚至上万个顶点，使得最短路径求解变得更加复杂化，计算量也更加庞大。同时计算消耗的时间和所需的存储空间也将增加。随着计算机网络技术的不断发展，使基于网络的分布式并行计算技术得到了较快发展，出现了大量并行算法。从而为快速求解大规模网络的最短路径问题提供了一种高效的途径。
本文首先对并行计算基础知识进行了简单介绍，包括并行计算机模型，并行算法设计方法，提高并行算法的几个关键因素及目前运用较多的并行环境。结合本文研究内容，文章中对规模较大的城市交通网络进行分析，提取特征，然后给出了大规模城市路网的宏观和微观模型，建立了交通路网的图结构。接着对经典串行Dijkstra算法进行并行化设计，采用Master/Slave模式来具体实现求解大规模网络最短路径的细粒度并行算法，并在MPI并行环境下对算法进行了实验验证，从理论上分析，并行化后使算法复杂度由O(N2)减到O(N2/P + N*(P-1))，提高了算法的效率。
针对具体的大规模交通网络来说，运用并行方法求解最短路径的过程中，对交通网络的分割起着很关键的作用，文章中给出了几个常用的分割方法，并对他们各自的优缺点进行了说明，本文采用Metis图划分方法对网络进行分割，通过修改Metis库中源文件，提取出计算最短路径所需的相关信息。同时给出了分层并行求解最短路径思想，并在多机下环境下实现了最短路径查询。具体针对西安市电子地图中，本文将其分成两层来对整个复杂路网进行化简，根据分而治之的思想策略，采用SPMD模式在分布式环境下对最短路径进行求解，求解过程中采用了上述的并行搜索算法。运用该方法大大提高了计算效率，节省了时间开销，同时降低了对计算机的内存存储需求。负载平衡问题几乎是所有并行计算都要考虑的问题，本文同时提出了一种基于益处评价函数的负载平衡策略及其具体的调度算法，运用并行快速排序算法对其进行了验证，取得了较好的实验效果。该方法对同类问题具有很好的借鉴价值。
最后文章简单介绍了并行计算环境，基于消息传递模式的MPI(Message Passing Interface)运行平台，结合本文，通过4台PC机搭建并行试验平台，用VC ++6.0为编译环境，对三部分内容进行了实验测试，(1)对并行Dijkstra算法的测试；(2)结合西安市电子地图，运用Mapinfo软件将地图信息导出，在PC机群的并行环境下对其进行实现。实验结果表明，该方法在运行时间和内存空间分配都具有明显的优势，具有良好的实用性。(3)对负载平衡策略进行测试，获得了较高的执行效率。