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

摘要

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