张海亮，张 征

（1.山西工程科技职业大学，山西 晋中 030619；2.浙江工业大学机械工程学院，杭州 310014）

0 引言

随着计算机技术、网络技术的成熟，包括无人驾驶在内的道路规划［1］与最短路径算法［2］逐渐成为研究热点。

A*算法［3-4］作为最短路径中最成熟的算法之一，在广度优先搜索的基础上，以启发式搜索为基础，同时具有Dijkstra 算法［5］在搜索速度和效率上的优势。A*算法在启发式搜索的过程中，采用了曼哈顿权值函数作为最优邻接点的评估标准，相对于广度优先搜索，减少了大量的无效邻接点的扩展验证，有效提高了算法的搜索效率［6-8］。但是对于大数据量下的网络拓扑，A*算法在进行空间搜索时，算法效率呈阶梯式下降，且起始点和目标点越远，中间的间隔越大，A*算法在进行最优邻接点选取时的时间就越长。GeoHash 索引［9］以地理经纬度信息为基础，将经纬度信息转化为GeoHash 值赋值给栅格节点，可以在A*算法中作为最优邻接点的权值评估参考，进一步确定最优邻接点。

1 A*算法

A*算法在求解最短路径时（如图1a 所示），整体的思路是从起始点A 开始，通过迭代方式查找相邻方格，不断扩展直至找到目标点B。在迭代查找相邻方格时，采用曼哈顿函数对相邻方格进行评估，通过对比每个相邻方格与目标终点之间的方格数，来判断哪个方格为最优邻接方格，并将其作为下一步选择的起点，然后再进行迭代查找，在迭代的过程中，每次都对当前起点的邻接方格进行曼哈顿函数评估，每次都计算出一个最优邻接点作为下一步的起点，这样不断向外扩展，一直扩展到目标终点为止。……