A*算法初级总结

说明

最近正好被导师调去做一门和无人机相关课程的助教，需要尽快根据A*算法和相关指引调试一个仿真器。以前Intro of aerial robot课程只是非常浅显的了解过，一学期不应用也没有留下太深刻的印象。现借此机会对网上的一些资料进行总结，因为自己也是小白起家，如果有总结不对的地方，还请各位大佬多多指点。主要资料来源于B站江中游老师的A星算法讲解视频：https://www.bilibili.com/video/BV1y5411b7YX

知识点总结

所谓A*，可以这样理解，因为该算法会对某个像素点周围8个相邻点进行索引，其形状类似于“※”。

首先建立地图如下（截图于视频中）：
图1
图1中，绿色3,3为起点，7,3为终点，蓝色为障碍物。起始遍历的点为“父节点”，其余要被遍历的周围节点称为“子节点”（8个）。每个子结点到终点存在“预估距离（成本）”，具体是不计障碍物到达终点的距离。此时算法利用“曼哈顿算法”。例如，(4,2)点到终点的曼哈顿距离为4（个单元格）。另外说明，为方便计算，根据勾股定理，(4,2)子节点和(4,3)子节点到父节点的成本为14和10。曼哈顿算法的距离成本记为“H”，子节点到父节点的距离成本为“G”，总距离成本“F”，计算方法为F=G+H。计算后的F值如图2所示：

图2
算法的核心为选择F值最小的子节点作为下一个父节点再进行遍历。但需要注意以下几点：

1. 建立开放列表open list，关闭列表close list；首先将第一个父节点（起点）放入close lsit，其8个子节点放入open list并查询最小值，之后放入close list成为下一个父节点，如此循环，直到终点放入其中。
2. 需要判断是否为障碍物，是则不进行遍历；
3. 需要判断是否已经存在close list中，是则不进行遍历；
4. 需要判断是否已经存在open list中，是则不进行遍历；举例，第一次遍历选出(4,3)点为F值最小点，以其为第二个父节点遍历子节点，但因为该点的所有子节点都是障碍物、存在open/close list中，则无需遍历，此时应选择open list内F最小值点作为下一个父节点，即(4,4)点；

图3
图3所示，此时的父节点为(4,4)点，放入close list，并进行子节点遍历，注意根据上述特殊情形，只需要另外遍历第五行的3个子节点，将它们放入open list，遍历所有open list中找F最小值，此时找到(5,5)点为下一个父节点并放入close list，如图4所示，红色为现有open list。此时再遍历open list找到F最小点，为(6,4)点。

图4
如此循环，进行遍历，则会发现终点，如图5所示：
图5
如此，找到终点后则找其父节点，循环其父节点则回溯一条最佳路径，如图6所示。
图6
接下来要根据一篇文章进行仿真器的实现，可能会有更多新的认识和补充。
以上，如有错误，还请批评指正。