,,

(1.上海电力学院 计算机科学与技术学院,上海 200090;2.中国计量大学 机电工程学院,浙江 杭州 310018)

城市交通导航中最基本的路线搜索就是最短路径问题,因此,我们经常会使用经典的广度优先算法——Dijkstra算法来解决该问题。其主要特点是以找寻的起始点开始搜索所有与其连接的点,从中心向外层扩展,直到找到终点。该算法大多用来计算单源最短路径。

另外一种常用的经典深度优先算法是Floyd算法。该算法利用动态规划的思想,通过加权寻找与距离起始点最短距离的点并深入下去,多用于计算多源最短路径。

虽然这两个算法都能解决最短路径的计算问题,但都存在着效率问题,不仅需要搜索大量的节点,而且如果遇上交通导航或者游戏寻路导航这样庞大的系统问题时,其处理能力和数据的存储还存在一定的局限。

A*算法作为另外一种算法,解决了庞大系统的计算和障碍物复杂度等问题,常被运用到城市交通和游戏的路径导航。因此本文着重于A*算法变种的对比和改进。

1 A*算法及其变种

1.1 A*基本算法

A*算法是目前广泛使用的基于启发式的最短路径算法,通过计算函数的相对最优解来筛选出发点周围的后继点,能适用于各种场景,相当灵活。它主要使用了静态路网中求解路径最有效的直接搜索方法——启发式,而且A*算法还使用了两个存放等待检查点的Open表和存放不需要再检查点的Close表,然后通过计算函数和父节点的对比来寻找路径上的点[1]。……