发现尼姑上没有太多 A* 学习笔记，来一发。

A* 又称启发式搜索，能够解决带权有向图上的最短路问题。具体的，给出起点 $s$ 和终点 $t$，它能在不劣于（不是一定优于）优先队列 bfs（即 Dijkstra）的时间内求出从起点到终点的最短路。

我们先来思考，为什么 Dijkstra 会在有些情况下慢呢？因为它的优先队列只保证了 $s$ 到队头点的距离最短，但如果队头到 $t$ 的最短路不是最优解，而队尾点到 $t$ 是最优解，那么就会花费大量时间使用优先队列前面的点松弛，松弛出来的也不是最优解。A* 就解决了这个问题，它保证了在优先队列中靠前的点 $u$ 从 $s$ 到 $u$ 再到 $t$ 的路径一定是比较优的。

具体的，对于每个点 $x$ 都有两个属性 $g(x),h(x)$，其中 $g(x)$ 为起点到当前节点的最短路（由前驱点松弛得到），$h(x)$ 为 $x$ 的预估价值，在最短路问题中就是预估的 $x$ 到 $t$ 的最短路。定义 $x$ 点的价值 $f(x)=g(x)+h(x)$，优先队列中的节点按价值 $f$ 排序。

可以发现，当 $h(x)=0$ 时，一个点的价值就相当于起点到当前点的最短路，这时算法就退化为了 Dijkstra。这启示我们，恰当的 $h$ 函数值可以让 A* 算法的复杂度降低。需要特别注意的是，$h$ 预估的值必须是最乐观的估计，即只能估少不能估多。具体证明可以看这篇文章。sto

稍微总结一下，Dijkstra 只是保证了 $s$ 到队头 $u$ 最优，而 A* 虽然没有保证它，但它保证了 $s$ 到 $u$ 再到 $t$ 是最优的。

A* 算法最重要的就是 $h$ 函数的设计。

给出一个 $n \times m$ 的迷宫，每单位时间内可以从一个点向四个方向走一步求从 $(1,1)$ 到 $(n,m)$ 最少需要多少单位时间。

显然 dfs 和 bfs 可做。这里给出 A* 做法。

显然 $f(x,y)$ 可以