\(A*\) 算法

这个算法其实就是 dijkstra 的变种，是对于一般的 bfs 的一种优化手段。

首先需要设置一个东西叫做估价函数。普通的 bfs 的估价函数一般取 \(0\)。这个东西如果你要保证一定正确，记起点到当前点的距离为 \(d[i]\)，到末尾的真实距离为 \(g[i]\)，设你的估价函数是 \(f[i]\)，则 \(f[i]\le g[i]\) 就能保证正确。下面我们来证明一下这个结论：

反证法，假设不成立，即当前出队的终点距离不是最优解，即 \(dist>d_{\text{最优}}\)，我们设最优解路径上有一点 \(u\)，则必有 \(d[u]+f[u]\le d[u]+g[u]=d_{\text{最优}}\)，所以 \(dist>d_{\text{最优}}\ge f[u]\)。