A*算法

人工智能课堂上提到的，顺便就去学了下原文

---

其实就是一种寻路算法，寻找图中A到B最短路径（图中可能存在障碍物）

最简单粗暴就是广度优先，每一次扩增一圈，是一种浪费时间的算法

那么就会想到以这种方式进行改进—-给每个点附加一个评价函数

————-

开始：

1. 从起点 A 开始，并把它就加入到一个由方格组成的 open list( 开放列表 ) 中。这个 open list 有点像是一个购物单。当然现在 open list 里只有一项，它就是起点 A ，后面会慢慢加入更多的项。 Open list 里的格子是路径可能会是沿途经过的，也有可能不经过。基本上 open list 是一个待检查的方格列表。
2. 查看与起点 A 相邻的方格 ( 忽略其中墙壁所占领的方格，河流所占领的方格及其他非法地形占领的方格 ) ，把其中可走的 (walkable) 或可到达的 (reachable) 方格也加入到 open list 中。把起点 A 设置为这些方格的父亲 (parent node 或 parent square) 。当我们在追踪路径时，这些父节点的内容是很重要的。稍后解释。
3. 把 A 从 open list 中移除，加入到 close list( 封闭列表 ) 中， close list 中的每个方格都是现在不需要再关注的。

---

计算出组成路径的方格的关键是下面这个等式：

F = G + H

沿着到达指定方格的路径来计算 G 值，那么计算出该方格的 G 值的方法就是找出其父亲的 G 值，然后按父亲是直线方向还是斜线方向加上 10 或 14

有很多方法可以估算 H 值。这里我们使用 Manhattan 方法，计算从当前方格横向或纵向移动到达目标所经过的方格数，忽略对角移动，然后把总数乘以 10 。之所以叫做 Manhattan 方法，是因为这很像统计从一个地点到另一个地点所穿过的街区数，而你不能斜向穿过街区。重要的是，计算 H 时，要忽略路径中的障碍物。这是对剩余距离的估算值，而不是实际值，因此才称为试探法

---

继续搜索：

1. 从 open list 中选择 F 值最小的 ( 方格 ) 节点，把它从 open list 里取出，放到 close list 中。
2. 检查所有与它相邻的方格，忽略其中在 close list 中或是不可走 (unwalkable) 的方格 ( 比如墙，水，或是其他非法地形 ) ，如果方格不在open list 中，则把它们加入到 open list 中。
3. 把我们选定的方格设置为这些新加入的方格的父亲。
4. 如果某个相邻的方格已经在 open list 中，则检查这条路径是否更优，也就是说经由当前方格 ( 我们选中的方格 ) 到达那个方格是否具有更小的 G 值。如果没有，不做任何操作。
5. 相反，如果 G 值更小，则把那个方格的父亲设为当前方格 ( 我们选中的方格 ) ，然后重新计算那个方格的 F 值和 G 值。

---

因此，进入close list的条件是被选为F值最小的节点，进入open list的条件是与被选中的节点相邻，发生G值比较的情形是当前节点选取相邻节点时发现其中已有open list节点

---

题外话：这个A-star有点像当初学最短路径的一种方法（djiskra算法）每次取出未访问结点中距离最小的，用该结点更新其他结点的距离