第三：启发式搜索：A* 算法

文章目录

1、前言

使用 A* 算法求解扫地机器人从起点到终点的最短路径搜索。

2、A*算法

上一关介绍的深度优先搜索和广度优先搜索都是盲目搜索算法，搜索范围比较大，效率比较低。如何在搜索过程中引入启发信息，减少搜索范围，以便尽快的找到解，这种搜索策略则称为启发式搜索。

而启发式搜索中最为经典且最常用的算法是A * 算法。 A* 算法最为典型的应用就是寻路。假设我造了一个扫地机器人，现在这个扫地机器人需要从 A 走到 B 去充电（其中灰色部分表示墙，扫地机器人不能穿墙）。怎样才能让扫地机器人更加智能地找到去充电的最短路径呢？没错，我们可以使用 A* 算法！

在了解 A* 算法的算法流程之前，先要知道两个列表：开启列表和关闭列表。开启列表其实就是一个等待检查的方块的列表，关闭列表是不需要检查的方块的列表。

好了，我们来看看 A* 算法的执行流程。

从起点 A 开始，把它作为待处理的方