文档视界 最新最全的文档下载
当前位置:文档视界 › 并行K最短路径搜索算法研究

并行K最短路径搜索算法研究

目录

第一章绪论 (1)

1.1 论文研究背景 (1)

1.2 国内外研究现状 (2)

1.3 论文的研究目标及意义 (6)

1.4 本文的组织结构 (6)

第二章最短路径问题基础 (8)

2.1 城市路网中的最短路径问题 (8)

2.2 图论的基本概念 (8)

2.3 图的存储表示 (10)

2.3.1 邻接矩阵 (10)

2.3.2 邻接表 (11)

2.3.3 两种存储表示方式对比 (12)

2.4 城市交通网络分析 (13)

2.4.1 城市道路的网络拓扑 (13)

2.4.2网络模型及其构建实例 (17)

2.5城市路网网络分解的基本知识 (19)

2.5.1网络分解的基本要求 (19)

2.5.2网络划分方法 (20)

2.5.3交通网络分割算法 (21)

2.6本章小结 (22)

第三章 K最短路径算法的并行化设计 (23)

3.1K最短路径算法 (23)

3.1.1算法的基本思想 (23)

3.1.2算法的程序设计 (24)

3.2并行算法认识 (26)

3.2.1并行算法的概念 (26)

3.2.2并行算法的网络分解原则 (27)

3.2.3并行编程的几种常见模型 (29)

3.3并行K最短路径算法 (30)

3.3.1并行K最短路径算法的设计思路 (30)

3.3.2并行K最短路径算法程序设计与实现 (32)

3.4本章小结 (35)

第四章并行K最短路径算法的性能测试 (36)

i v

4.1并行算法的几个评估指标 (36)

4.2本文的实验环境 (36)

4.3实验结果分析 (37)

4.4本章小结 (39)

第五章并行K最短路径算法的应用 (40)

5.1实验平台Hadoop概述 (40)

5.1.1Hadoop的分布式文件系统HDFS (41)

5.1.2Hadoop的编程模型MapReduce (42)

5.1.3Hadoop环境的搭建与测试 (45)

5.2城市路网交通流问题 (48)

5.3并行K最短路径算法分配交通流 (49)

5.4本章小结 (53)

第六章总结与展望 (54)

6.1全文总结 (54)

6.2未来展望 (55)

参考文献 (56)

攻读学位期间取得的研究成果 (59)

致谢 (60)

v

第一章绪论

第一章绪论

1.1 论文研究背景

城市文化和经济的快速发展,使得城市交通越来越受到我国甚至世界各国的关注。车辆和人口的快速增长给城市交通造成了极大的压力,进而引发交通堵塞,而交通堵塞问题一直是令我们每个人都十分头疼的问题,它给人们的日常出行带来了极大不便。

近年来,计算机和互联网网络通信技术的广泛研究与应用,带动了智能交通行业的快速成长,随着国家和社会以及个人对交通现状的高度重视,再加之它具有成本低、维护简单的特点,使得智能交通成为管理有关交通问题的重要手段。智能交通[1]是指以高科技技术为基础,以信息的获取、信息处理和信息公布这个模式来发展交通系统,最终形成一个集信息与智能为一体的实时、新型的交通管理系统。现代智能交通充分和高效地结合了各种交通资源,有效减少了交通事故的发生频率、降低了因汽车尾气所带来的大气污染,缓解了人们旅途停车位不足等许多交通问题。

新型的智能交通系统为我国城市交通发展带来了许多有益的影响,总的来说主要有以下三个方面:

(1)道路畅通性:采用智能交通系统有助于改善城市路网的通行能力,提高了系统的运行效率。

(2)出行安全性:智能交通系统的发展有助于提高交通运营安全性能,避免出行过程中交通事故的频繁发生,降低交通事故所带来破坏问题。

(3)周围环境性:智能交通系统的发展对于缓和交通堵塞特别有效,也减轻了各种出行车辆对环境的污染。

交通问题与我们每个人的切身利益息息相关换,用户出行时的路径查询问题一直是智能交通领域研究的热点。传统求解最短路径的算法主要包括经典的Dijkstra、A*、Dial、KSP、Bellman-ford算法等等,其中Dijkstra算法最受关注。给定一对节点,Dijkstra 算法只能搜索到一条最短路径,多用户同时出行,容易在这一条路径上产生拥挤。KSP 算法[2]可以搜索到给定节点间好多条符合要求的路径,在有多个用户请求同时按该对节点行驶的情况下,KSP算法能够为同时出行的用户提供多条最合理的路径,相比之下,KSP算法的搜索结果达到了对路网中交通流的有效分配,减少了交通负荷。路网规模越大,需要处理的数据量就越多,KSP算法的负荷就逐渐加重,进而导致查询最短路径过

1

相关文档