A星搜索 (A Star search)是一种在图形平面上从有多个节点的路径中求出最低通过成本的算法。

Agreement

Terms

1. cost function

$f(n)=g(n)+h(n)$

其中

  1. $g(n)$ 是从起始节点到考察节点的代价函数
  2. $h(n)$是从考察节点到目标节点的最小代价的启发式估计函数，该函数需要具体问题具体分析
2. open list

在经由起始节点出来后，将待搜索的节点加入到其中，算法将按顺序逐个检查列表中的节点。

3. close list

将从open list中取出检查过的节点存入该列表。

A* Search

Description

A星搜索（A Star Search, A*）是一种以加权图来表示的搜索算法。它从图的起始节点出发，维护起于该节点的路径树，并一次扩展一条边的路径直到满足终止条件，来寻找到目标节点的最小代价（如最小距离、最短时间等）路径。

Algorithm

以网格化后的一种路径搜索为例，地图中绿色块为起始节点，红色快为目标节点，蓝色块为障碍物。

每一节点需要保存其前驱节点（父节点）信息，便于最后回溯路径

地图

  1. 将节点放入open list

    对于第一步，就是起始节点

  2. 从open list取出具有最小 cost 的一个节点，放入close list

    对于第一步，就是起始节点

  3. 搜索该节点相邻的所有可到达节点（忽略其中已在 close list 中的节点），并加入open list

    相邻可到达节点

  4. 如果节点不在 open list 中，将其加入；否则，如果自当前节点到达该节点更优（更小的 $g$ 值），将该节点的前驱设置为当前节点，并重新计算 $g$ 值和 $h$ 值。

  5. 在允许的迭代步内重复 1-4 步，直到目标节点被加入 open list

    搜索示例

Variants & Improvements

Summary

Appendix

Reference
  1. A* Pathfinding for Beginners
  2. A* 寻路算法
Archive