A*算法学习

A*算法伪代码

步骤1：

创建地图。

说明：A*算法中的地图大多是用栅格图形构建的，可以在代码中使用数组或列表来实现。 一般采用二维数组索引来表示每个节点的坐标。 索引内容0表示地图可以通过，1表示地图中有障碍物。

第2步：

设置起点，目标点即终点。 将起始点添加到open list()中，这个过程可以看成是初始化。

说明：是一个列表，存储了待检测的节点。 列表中存在一个或多个待检测节点。 待检测节点需要检测和计算的信息为：

1、从起点到当前待检测节点的移动成本（cost），通常用G表示

2、从当前节点到终点的预估成本，通常用H表示

3、总成本，通常用F表示，F（总成本）=G（搬家成本）+H（预估成本）。

第三步：

如果不为空，则说明还有节点需要检测，循环执行以下步骤：

1）找到表中cost最小的节点，即F最小的节点，将该节点作为当前节点。

说明：当前节点是列表中的一个元素。 该列表是一组已检测到的节点。 每次检测都是以当前节点为中心，检测周围的8个节点（如果检测到8个节点，通常就变成8邻域搜索方法，也有24邻域搜索方法）用比较官方的语言表达就是将已经检测到的当前节点添加到其中，同时将当前节点的8个邻域坐标添加到其中。 此时需要注意的是，如果当前节点邻域内的元素是端点、障碍物或者与第一个当前节点的邻域重叠，则判断下一步。 另请注意，步骤 2 中只添加了一个起点，因此无论如何计算，起点的成本都会被认为是最小的，这意味着在循环的第一轮中，起点将是当前点。

2）判断当前节点的邻居状态：

A。 如果邻居是地图中的障碍物，则不进行任何操作（只有添加了才会进行下一步操作）

b. 该邻域为终点，跳出循环，并以当前节点作为该邻域的父节点。

说明：父节点的概念如下。 父节点的作用是找到一条从终点到起点的反向路径。

C。 邻域是其中的一个元素，不执行任何操作。

d. 如果邻域不是 中的元素，则当前节点将作为该邻域的父节点，并将该邻域添加到其中。

解释：该邻域不是 中的元素，即表中没有相同的元素，但该邻域元素紧邻当前节点，这意味着该邻域有可能成为下一条路径，即当前节点可能会进入下一步。 这个邻里点。 所以这里扩展了父节点的概念，因为当前节点下一步可能会走到这个邻域点，所以当前点就被视为这个邻域的父节点。 同时，这个邻域有没有可能成为下一个路径节点？ 因此，需要添加这个邻域来检测其F成本。

e. 邻域是 中的一个元素，此时需要再次进行判断。 如果到达当前邻域终点的成本小于 中已存在的成本，则删除 中现有的邻域并将其添加为当前邻域，并将当前节点作为当前邻域的父节点邻里。 如果不小于，则不进行任何操作。

说明：这里你需要仔细思考。 定义当前节点的邻域为E。那么你需要知道 中存在这个邻域。 这个元素在谁的邻居中？ 是作为当前节点的前一个邻域。 定义中的一些邻域是（最后一个值）。 E 和 E 到终点有各自的成本，因为它们的移动成本 G 不同。 因此，我们可以通过比较F来确定谁是最优路径。

F。 通过上面的判断，会得到一个新的表，循环第三步。

第四步：

完成上述循环后，如果已经找到路径，则从目标终点开始，依次查找各个节点的父节点，直到找到起点，从而形成一条路径。

说明：在代码测试过程中，发现列表中存储的每个元素都是一个路径，但这在理论上是不正确的，需要验证。

项目代码如下：