原文传递
基于路网分层的多级搜索算法的研究与实现
| 论文题名： | 基于路网分层的多级搜索算法的研究与实现 |
| 关键词： | 电子地图搜索;车载GPS定位系统;最短路径;多级搜索算法;路网分层 |
| 摘要： | 近年来，智能交通系统(ITS)、车载GPS定位系统、城市交通诱导系统等相关地理信息系统(GIS)技术的广泛应用对电子地图搜索服务提出了更高的要求。因此，对电子地图搜索及其相关领域的研究已变得炙手可热。 本文研究了电子地图搜索服务中的一个核心议题：最短路径问题求解。拥有海量数据是GIS系统的一个显著特点，合理地提取、组织、分析和处理电子地图数据是提高寻径效率的关键。传统最短路径问题的研究更多地注重算法的改进和优化，或者是基于少量地图数据的寻径系统的实现；本文则侧重于海量数据下的寻径及其性能优化，提出基于路网分层的多级搜索算法，实现了全美国的Door2Door(门牌号到门牌号)寻径系统。其主要研究工作如下： 1.提出基于路网分层的多级搜索算法，并比较几种传统寻径算法的优劣，选择了适合GIS中大数据量寻径的A*算法作为其通用最短寻径算法； 2.将分层思想引入路网数据组织，从地图数据中提取出需要的数据通过分层、合并、简化等方式组织成特定的道路数据文件，并建立路网数据库； 3.通过实验得出了适用于全美寻径系统的A*算法的估价函数的加权模型；以此为基础提出了基于海量数据下的各种寻径策略，并讨论其具体实现的细节问题； 4.讨论寻径中的必备工具--RTree模块，研究TIGER数据和Shape文件的组织格式； 5.基于前面的研究实现了一个实用高效的寻径系统。 全文主要对GIS寻径问题中海量数据的处理进行了较为深入的探索并提出相应的算法，并且初步实现了全美国的Door2Door寻径系统，证明了理论研究的价值和可行性。目前国内关于大数据量下的最短路径问题的研究还比较薄弱，实用性的资料较少，因此本文的研究有较大的理论意义，而且本文已经初步实现了一个寻径系统，因此有着更大的现实意义。 |
| 作者： | 任金胜 |
| 专业： | 计算机应用技术 |
| 导师： | 朱清新 |
| 授予学位： | 硕士 |
| 授予学位单位： | 电子科技大学 |
| 学位年度： | 2008 |
| 正文语种： | 中文 |
检索历史
应用推荐
