启发式搜索

启发式搜索是一种对搜索到的每一个位置进行评估，然后从评估的最优位置进行搜索直到目的地，
由于搜索时对每一个位置的评估是基于直观或经验的所有叫启发式搜索

A*算法

历史：

1964年Nils Nilsson提出了A1算法，是一个启发式搜索算法，
而后又被改进成为A2算法，直到1968年，被Peter E. Hart改进成为A*算法

主要思想：

1.对于每个搜索到的点求一个估价函数f(x)。
$\large f(x)=g(x)+h(x)$
其中g(x)表示起点到当前点实际走的代价，h(x)表示当前点x到终点的估算代价。
2.并将这个搜索到的点按f(x)加入一个待搜索列表中。
3.每次从待搜索列表取出f(x)最小的点加入搜索过列表，并从这个点开始进行搜索
4.重复1。

注意：如果搜索到的一个点已经在待搜索列表(在搜索过列表不算)中
则要更新它的f值，而不是什么也不做，因为可能出现下面这种情况

红色为起点，绿色为终点，灰色为搜索过列表中的点，黄色为待搜索列表中的点，蓝色的是障碍。
如果按和终点的曼哈顿距离算h(x)则会搜索成这种情况，
这时被圈出的黄色的点g(x)=被圈出的灰色的点的g(x)+1。

这显然不是最优的g值
所以搜索时在遇到待搜索列表中的点要更新它的f值