学位论文 > 优秀研究生学位论文题录展示

一对一最短路径算法研究及车载导航系统设计

作　者: 廖远
导　师: 黄菊花
学　校: 南昌大学
专　业: 机械电子工程
关键词: 一对一最短路径 多核多线程 A~*算法 自适应遗传算法 车载导航系统
分类号: TP301.6
类　型: 博士论文
年　份: 2012年
下　载: 399次
引　用: 0次
阅　读: 论文下载
 

内容摘要


最短路径问题常见于物流运输、车载导航与通讯网络等之中,有许多基于经典Dijkstra算法的求解方法已被一一提出。不论是在物流运输或者是在车载导航中,最常应用到的最短路径问题就是一对一最短路径问题。本文首先介绍了各种常用的一对一最短路径算法,包括各种经典算法、A*算法、遗传算法和蚁群算法,并对它们各自的优缺点进行了详细的比较。然后,本文以日益成熟的多核与多线程技术为基础,改良传统的A*算法,设计了一种基于多核多线程的A*算法。经过测试系统验证,该算法结合本文对标准二叉堆的改进——直接插入二叉堆数据结构,能够大幅地提高一对一最短路径搜索的时间效率接着,针对大规模网络中一对一最短路径搜索的性能需求以及一对一最短路径模型的特征,本文对遗传算法进行了一系列改进,包括种群初始化方法、选择方法、交叉方法和变异方法,并且实现了交叉率和变异率的自适应调整。测试结果证明,该自适应遗传算法快速、灵活,能够有效地避免断路和环路,并且能够满足大规模网络中一对一最短路径搜索的需求。最后,本文运用上述基于多核多线程的A*算法,在嵌入式平台上以Eclipse为工具设计并实现了一个Android版的动态实时车载导航系统,并在南昌市电子地图真实路网上实际运行该系统,取得了良好的效果。

全文目录


相似论文

  1. 机械臂轨迹规划研究,TP242
  2. 基于服务链的GIS服务组合研究与应用,P208
  3. 甲醇四塔精馏建模与变负荷能耗优化研究,TQ223.121
  4. 车载导航路径规划算法研究,U495
  5. 基于多核平台的高速网络数据捕获和并行处理研究与实现,TP393.08
  6. 三维模拟车载导航系统的设计与实现,TN966
  7. 车载导航系统中地图显示方法的设计与实现,TN967.1
  8. 基于多核技术的并行网络仿真器研究,TN915.09
  9. 主题爬虫关键技术研究及应用,TP391.3
  10. 基于Windows CE的嵌入式车载GPS导航系统设计,TN967.1
  11. 基于WEBGIS的公交查询系统的设计与实现,TP311.52
  12. 车载导航系统中的路径规划算法研究,U495
  13. 基于ARM9车载导航系统的设计研究,TN967.1
  14. 基于智能搜索算法的组卷系统研究与实现,G434
  15. 室内清洁机器人自主返回充电路径规划算法研究,TP242
  16. 电气化铁路接触网系统维修计划的多目标优化研究,U226.8
  17. 蚁群导航优化算法研究及其在MINIGUI上的实现,TN961
  18. 车载导航路径规划技术的研究,TN967
  19. 基于智能优化算法的OFDMA系统自适应资源分配问题研究,TN929.531
  20. 公路运输费用计算系统的分析与设计,TP311.52
  21. 自适应遗传算法的研究,TP18

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 一般性问题 > 理论、方法 > 算法理论
© 2012 www.xueweilunwen.com