A*算法 思想与实现

1.思想

BFS是很好的最短寻路算法，但是可以对BFS进行进一步的优化，A算法应运而生。
A算法核心思想是贪心+BFS，区别于BFS盲目地对目标进行搜索，A*算法会对目标点的曼哈顿距离（$dis(x_1,y_1,x_2,y_2) = (x_1-x_2)^2 + (y_1-y_2)^2$）进行排序，优先对较近的目标点进行搜索。
当对近距离的点搜索失败的时候，选用较远的搜索点

2.一般性描述

2.1 评估函数

在搜索过程中，用一个评估函数进行评估当前的状态，可以表示为：
$f(x) = g(x)+h(x)$

• $g(x)$表示初始状态到当前的代价
• $h(x)$表示当前状态到目标点的代价，因此$h(x)$被称为启发函数

2.1.1 评估函数的特殊情况

• $h(x)=0$时$f(x)=g(x)$，此时退化成为BFS算法
• $g(x)=0$时$f(x)=h(x)$，此时退化成为贪心算法，但是贪心容易陷入局部最优解中，无法到达终点

3.实现、题目

待填