2. Astar数据结构 + 公式

1、两个数据结构

1. Open表，用来存储当前能够到达的结点
2. Close表，用来存储已经到达过的结点

2、一个公式

（1）公式：F = G + H

每一个格子拥有三种属性，即：

（2）三种属性的意义

1. G：从起始结点走到当前结点需要花费多少步（已经花了的步数）
2. H：不考虑障碍的情况下，从当前结点走到终点需要花费的步数（预估仍然需要花的步数）
3. F：对G和H的综合评估，也就是路径上如果拥有这个格子的话，最终需要花费的步数数量的预估

3. 算法步骤

1、第一轮操作

1. 首先，我们需要将起点（机器人起始点）放到open表中

1. 在【Open表】中寻找出一个F值最小的结点作为【当前结点】，把【当前结点】移出【Open表】并且加入到

1. 当前的父子结点关系如下

2、第二轮操作

因为当前的【Open表】不为空并且没有找到【end结点】，所以重复第一轮的第二三步操作

1. 寻找【Open表】中F值最小的结点作为【当前结点】，把【当前结点】移出【Open表】并且放入【Close

表】，接下来是对【当前结点】进行扩展

1. 检查【当前结点】四周是否有能够到达的结点（扩展结点），如果这些【扩展结点】不在【Open表】中或者

【Close表】中，就把这些【扩展结点】计算出F值后加入到【Open表】中，并且把【当前结点】设置为这些【扩展结点】的父节点。

1. 因为（3， 3）是【障碍物】，（3， 1）已经存在于【Close表】中，所以这两个结点都不加入【Open表】中

当前的父子结点关系如下：

3、第三轮操作

接下来的方式就是重复以下步骤：

1. 从【Open】表中寻找F值最小的结点移入【Close表中】并且当作【当前结点】进行检查扩展
2. 将能够到达的新结点加入到【Open表】中

下面是全部的过程的动图示例，仔细看F的值，每次都选择F值最小的结点进行检查扩展

原图链接：「代码随想录」知识星球