| 【中文题名】 | 复杂网络中最短路径问题的优化算法研究 |
| 【英文题名】 | Research on the Algorithm for Shortest Path Problem in Complicated Network |
| 【学科专业】 | 计算机软件与理论 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-9-17 |
| 【中关键词】 | 公共交通多重图,最短路径,最短K条路径,A~*算法,KSPA算法, |
| 【英关键词】 | multi-graph of public traffic,shortest path,K-shortest path,A~* algorithm,KSPA algorithm, |
| 【分类导航】 | 天文学、地球科学>测绘学>一般性问题>测绘数据库与信息系统>> |
| 【论文摘要】 |
随着计算机科学和地理信息科学的迅速发展,地理信息系统(GIS)因其强大的功能得到日益广泛和深入的应用。GIS、GPS等技术在全球范围内已被广泛的应用于智能交通系统(ITS)中。GIS中的网络分析是它最主要的功能之一,最短路径问题是网络分析中最关键的问题。因此,研究城市公共交通网络中的最短路径优化算法,寻找并提供一条或多条快速、经济、方便的从出发点到目的地的最优换乘方案,是公共交通系统中最基本最关键的问题,也是城市信息化建设中一个不容忽视的研究课题,更是运用各种高新技术和人工智能技术建立具有控制能力的、现代化的智能交通系统的迫切要求。
本文针对复杂网络中的优化问题,以城市公共交通为背景,对最短路径问题及最短K条路径问题进行了研究。首先通过分析城市公共交通网络的特点,根据图论中拓扑结构的原理对其进行了合理的抽象表示,给出的城市公共交通网络模型是一个复杂多重图。然后针对传统算法在求解多重图中的最短路径时存在的不足和缺陷,提出了改进的A*算法来求解多重图中的最短路径,并在改进的A*算法的基础上给出了一种KSPA算法来求解多重图中的最短K条路径问题。实验结果表明改进的A*算法和KSPA算法具有很高的执... |
| 【论文题纲】 |
|
摘要 |
4-5 |
|
Abstract |
5-8 |
|
第一章 绪论 |
8-14 |
|
1.1 课题研究背景 |
8-9 |
|
1.2 研究现状综述 |
9-13 |
|
1.3 论文研究内容及结构安排 |
13-14 |
|
第二章 城市公共交通网络模型的构建 |
14-25 |
|
2.1 基本概念 |
14-15 |
|
2.2 城市公共交通网络的抽象表示 |
15-19 |
|
2.3 时空搜索最短路径模型的建立和分析 |
19-24 |
|
2.4 本章小结 |
24-25 |
|
第三章 最短路径优化算法及改进 |
25-44 |
|
3.1 DIJKSTRA 算法求解站点间的步行关系 |
25-26 |
|
3.2 最短路径求解面临的问题 |
26-28 |
|
3.3 启发式搜索算法 |
28-32 |
|
3.4 改进的A~*算法 |
32-35 |
|
3.5 改进的A~*算法求解多重图中的最短路径 |
35-38 |
|
3.6 算法仿真及结果分析 |
38-43 |
|
3.7 本章小结 |
43-44 |
|
第四章 多重图中最短K 条路径优化算法研究 |
44-50 |
|
4.1 KSPA 算法原理 |
44-45 |
|
4.2 KSPA 算法描述及实例说明 |
45-47 |
|
4.3 算法仿真及结果分析 |
47-49 |
|
4.4 本章小结 |
49-50 |
|
第五章 智能公交查询系统的设计与实现 |
50-57 |
|
5.1 智能公交查询系统的总体设计 |
50-53 |
|
5.2 模块实现 |
53-56 |
|
5.3 本章小结 |
56-57 |
|
第六章 总结与展望 |
57-59 |
|
6.1 总结 |
57-58 |
|
6.2 展望 |
58-59 |
|
参考文献 |
59-63 |
|
致谢 |
63-64 |
|
攻读硕士期间发表的论文 |
64 |
|
| 【DOI】 | LunWen.ID:2.2008.37338 |
