原文传递
嵌入式平台下的导航路径规划算法研究与实现
| 论文题名： | 嵌入式平台下的导航路径规划算法研究与实现 |
| 关键词： | 车载导航;嵌入式平台;路径规划算法;搜索策略;道路交通 |
| 摘要： | 车载导航仪的出现，能够为驾驶员提供多条通往目的地的路径，并从中给出建议的最短路径，供其选择。从而解决因不熟悉道路交通状况而徒劳往返甚至延误时间这一难题。路径规划作为车载导航的核心，常常由于嵌入式环境的限制以及路径规划算法的性能限制，导致车载导航效果不尽如人意。 本文对常用的路径规划算法Dijkstra算法、Bellman-Ford-Moore算法、Floyd算法、启发式搜索算法特别是常用于车载导航中的路径规划算法A*算法等进行了详细的分析，针对求解最短路径问题的经典算法存在的求解速度慢、最优解精度不高等缺点，对算法提出了一定的改进。通过分析A*算法的适用场合、基本原理、具体步骤，考虑到嵌入式平台的特殊环境，为了满足车载导航设备的高效性、正确性和实时性的要求，对建立在A*算法基础上的导航路径规划算法做出优化和改进。首先采用了分层分解的数据组织方式，将数据分层存放，针对不同等级的路段和节点，采用不同复杂度的数据结构。分层的数据之间具有不同的数据结构，占用不同的数据空间，可以简化节点数据结构的复杂度。结合分层数据的组织方式，采用升层搜索策略，使得搜索可以在不同层次数据之间切换。也正是升层搜索策略的采用体现了数据分层存放的优点。既可以减少搜索后继节点的候选集，又可以减少搜索时间、节点存取时间以及内存的使用量。除此之外，还采用双向搜索策略，即可以防止搜索过界问题，又可以避免采用升层策略所引起的升层和降层的频繁切换可能导致的效率问题和时间复杂度提高的问题。采用这些策略可以减少搜索所用的时间，同时减少内存的使用量。 通过对改进前的A*算法和改进后的算法进行对比，无论是在效率上和实时性上都能满足用户的要求。除此之外，本系统还充分考虑了扩展性，例如缩减数据结构的复杂度，并尽量减少内存使用。并可采取在服务器启动时，直接将数据存放到内存中，从而避免数据在内存和外存之间切换。 |
| 作者： | 宋久元 |
| 专业： | 计算机科学与技术(计算机应用技术) |
| 导师： | 滕国库 |
| 授予学位： | 硕士 |
| 授予学位单位： | 大连海事大学 |
| 学位年度： | 2010 |
| 正文语种： | 中文 |
检索历史
应用推荐
