学位论文 > 优秀研究生学位论文题录展示
基于路网分层的多级搜索算法的研究与实现
作 者: 任金胜
导 师: 朱清新
学 校: 电子科技大学
专 业: 计算机应用技术
关键词: 最短路径 A~*算法 RTree 三段寻径 路网分层
分类号: TP301.6
类 型: 硕士论文
年 份: 2008年
下 载: 159次
引 用: 0次
阅 读: 论文下载
内容摘要
近年来,智能交通系统(ITS)、车载GPS定位系统、城市交通诱导系统等相关地理信息系统(GIS)技术的广泛应用对电子地图搜索服务提出了更高的要求。因此,对电子地图搜索及其相关领域的研究已变得炙手可热。本文研究了电子地图搜索服务中的一个核心议题:最短路径问题求解。拥有海量数据是GIS系统的一个显著特点,合理地提取、组织、分析和处理电子地图数据是提高寻径效率的关键。传统最短路径问题的研究更多地注重算法的改进和优化,或者是基于少量地图数据的寻径系统的实现;本文则侧重于海量数据下的寻径及其性能优化,提出基于路网分层的多级搜索算法,实现了全美国的Door2Door(门牌号到门牌号)寻径系统。其主要研究工作如下:1.提出基于路网分层的多级搜索算法,并比较几种传统寻径算法的优劣,选择了适合GIS中大数据量寻径的A~*算法作为其通用最短寻径算法;2.将分层思想引入路网数据组织,从地图数据中提取出需要的数据通过分层、合并、简化等方式组织成特定的道路数据文件,并建立路网数据库;3.通过实验得出了适用于全美寻径系统的A~*算法的估价函数的加权模型;以此为基础提出了基于海量数据下的各种寻径策略,并讨论其具体实现的细节问题;4.讨论寻径中的必备工具——RTree模块,研究TIGER数据和Shape文件的组织格式;5.基于前面的研究实现了一个实用高效的寻径系统。全文主要对GIS寻径问题中海量数据的处理进行了较为深入的探索并提出相应的算法,并且初步实现了全美国的Door2Door寻径系统,证明了理论研究的价值和可行性。目前国内关于大数据量下的最短路径问题的研究还比较薄弱,实用性的资料较少,因此本文的研究有较大的理论意义,而且本文已经初步实现了一个寻径系统,因此有着更大的现实意义。
|
全文目录
摘要 4-5 ABSTRACT 5-10 第一章 绪论 10-16 1.1 研究背景 10-11 1.2 GIS中最短路径问题的研究现状 11-13 1.2.1 最短路径算法 11-12 1.2.2 寻径策略和数据组织 12-13 1.3 研究内容及意义 13-15 1.3.1 研究内容 13-14 1.3.2 研究意义 14-15 1.4 本论文的章节安排 15-16 第二章 基于路网分层的多级搜索算法 16-34 2.1 算法的提出 16-20 2.1.1 算法提出的背景 16-18 2.1.2 分层与多级搜索思想的引入 18-19 2.1.3 基于路网分层的多级搜索算法的提出 19-20 2.2 MSA-HR的特点 20-21 2.3 MSA-HR的最短路径通用算法 21-33 2.3.1 传统最短路径算法及性能分析 21-26 2.3.2 通用最短路径算法的选择及改进 26-33 2.4 小结 33-34 第三章 基于分层思想的路网数据组织 34-56 3.1 路网分层策略 34-41 3.1.1 路网数据分层 34-39 3.1.2 数据分层存在的问题 39-40 3.1.3 道路的简化 40-41 3.2 路网数据的组织 41-50 3.2.1 数据源——TIGER数据 41-45 3.2.2 中间数据格式——Shape文件 45-50 3.3 道路数据文件的生成 50-52 3.3.1 道路数据文件的作用 50 3.3.2 道路数据路段结构 50-51 3.3.3 道路数据文件的生成 51-52 3.4 全美道路网数据库的建立 52-55 3.4.1 道路网数据提取策略 52-53 3.4.2 全美道路网数据库的设计 53-55 3.5 小结 55-56 第四章 MSA-HR的寻径策略分析 56-65 4.1 估价函数的加权模型 56-58 4.2 “三段寻径”分析 58-60 4.3 基于MSA-HR的寻径策略 60-64 4.3.1 County内寻径 61-62 4.3.2 State内寻径 62-64 4.3.3 USA内寻径 64 4.4 小结 64-65 第五章 系统实现 65-76 5.1 必要工具——RTree模块 65-68 5.1.1 空间索引 65-66 5.1.2 R树 66 5.1.3 R树索引的建立 66-67 5.1.4 R树索引在本文中的应用 67-68 5.2 系统需求分析 68-70 5.3 程序的主要结构及核心代码 70-71 5.3.1 系统类图 70-71 5.3.2 核心代码 71 5.4 性能分析 71-75 5.4.1 最短路径搜索算法性能对比 71-72 5.4.2 MSA-HR和平面算法性能对比 72-73 5.4.3 不同分层方式寻径结果对比 73-74 5.4.4 与Google寻径结果对比 74-75 5.5 小结 75-76 第六章 总结与展望 76-78 致谢 78-79 参考文献 79-83 攻硕期间取得的研究成果 83
|
相似论文
- 基于Agent的无线传感器网络自组织演化机制研究,TN929.5
- 单指派和多指派共存下含枢纽的物流网络设计,F252
- 高速公路养护站点分级建立与选址研究,U418.2
- 配送中心拣货路径信息采集与处理研究,F253.9
- 基于电子纸的电子地图技术研究与实现,P28
- 基于SSH的交通疏导空间信息服务系统分析与设计,U495
- 计算机兵棋中兵力机动路径规划研究,E919
- GIS空间分析在森林防火中的应用研究,S762
- 混合算法在物流运输问题中的研究和应用,TP301.6
- 基于矢量图形的城市交通地理信息系统研究,P208
- 社会关系网络紧密性测度研究,O157.5
- 基于路段流量的高速公路联网收费清分方法研究,U495
- 森林防火应急资源调度模型研究,S762
- 基于改进的Vickrey拍卖模型的网格作业调度算法研究,TP393.01
- 协同通信平台的设计与实现,TP311.52
- 公路运输费用计算系统的分析与设计,TP311.52
- 三维模拟车载导航系统的设计与实现,TN966
- ASON网络中GMPLS控制面的研究和开发,TN929.1
- 集装箱堆场智能算法研究,U691
- 厂区铁路设计阶段即时仿真基础问题研究,U212
- OSPF协议中ISPF算法及其实现的研究,TP393.04
中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 一般性问题 > 理论、方法 > 算法理论
© 2012 www.xueweilunwen.com
|