吕博 都美晔 李璐君

摘 要 由于A*算法在进行启发式搜索时具有较高的算法效率，并且可以基于评估函数找到最优路径，本文针对在大型停车场中寻车困难的问题提出采用A*算法进行路线规划。文章阐述了A*算法的原理及实现过程，并对停车场进行建模，通过仿真实验验证了算法应用于停车场寻车路径规划的可行性。

关键词 A*算法；路径规划；停车场

引言

随着经济的发展，中国汽车保有量及市场规模逐年增长。为满足人们停车的需求，住宅区及大型商场的停车场面积增大、层数增加，提供大量车位的同时对用户寻车也造成了一定困难。仅靠车位编号寻找车辆的方法效率较低，因此建立停车场寻车系统帮助用户寻找车辆位置，规划寻车路线十分重要。最短路径算法是计算机科学、人工智能科学等研究的热点问题[1]。两点间的所有路径中，一定有一条最佳的路径使时间和效率均为最优，这时就需要使用限制搜索区域内的最短路径算法[2]。其中，A*算法由于其性能和准确性被广泛使用[3]。

1 A*算法原理与实现

A*算法的原理是借助于开启列表（OpenList）和关闭列表（ClosedList）两个列表，通过估值函数来引导整个路径搜索的过程，快速寻找到一条最短的路径。其中，开启列表和关闭列表是 A*算法在寻路搜索的过程中必须维护的两张表。开启列表中存放着即将被访问但未被访问的节点，同时这些节点所对应着的估值值也被存放在该表中；而关闭列表中则存放着已经访问完成的节点。……