A*寻路算法 Day0825

概念：

启发式搜索：

启发式搜索就是在状态空间中对每一个搜索的位置进行评估，得到最好的位置，在从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率

在启发式搜索当中，对未知的估价十分重要。采用了不同的估价可以有不同的效果

估价函数;从当前节点移动到目标节点的预估费用：这个估计就是启发式的，在寻路问题和迷宫问题中，我们通常用曼哈顿算法估价函数预估费用

A*算法的特点：A*算法在理论上是时间最优的，但是缺点是：他的空间增长是指数级别的

在A*寻路算法中，我们通过从A点开始，检查相邻方格的方式，向外扩展直到找到目标

开启列表：待检查方格的集合列表，寻找周围可以达到的点，加入到此列表当中，并保存中心点喂父节点

关闭列表：保存不需要再次检查的方格

路径评分：

G- 与起始点的距离

H-与目标点的距离

F的值是G和H的和，F，G和H的评分被谢爱每个方格里面

F中间 G左上 H右上

选在经过那个方格的关键是：F=G+H

---

开始搜索

1.把起始格添加到开启列表

2.寻找七点周围所有可到达或者可通过的方格，把他们加到开启列表

3.从开启列表中删除点A，把它加入到关闭列表当中，列表中保存所有不需要再次检查的方格

继续搜索

4.把当前格子（红色的42）从开启列表中删除，然后添加到关闭列表当中。

5.检查所有红色42相邻的格子。跳过那些已经在关闭列表中的或者不可通过的，把他们添加到开启列表，把选中的方格（红色42）作为新的方格的父节点

6.如果某个相邻已在开启列表当中。检查现在的这条路径G值是否会更低一些。如果新的G值更低，那就把相邻方格的父节点改选为目前选中的方格，重新计算F和G的值

为什么?  随着关闭列表当中的确定，也就是新路径的确定，开启列表中的G值也会改变，所以需要重新计算