A*算法

$A^{\ast }$算法，又叫做$A-star$算法，是一种静态路网中求解最短路径最有效的直接搜索方法。

思想

我们首先来回忆一下$BFS$算法，我们的$BFS$算法每次都是从堆顶取出当前代价最小的状态进行扩展。那最先扩展到的就是最优的。

但我们$BFS$算法这种贪心思想是不完善的：我们虽然当前的代价小，但不能保证后来的代价也小（正所谓目光短浅）。这样就会使搜索量增大。

我们的$A^{\ast }$算法就是加上一个估价函数：不断从堆中取出“当前代价+预估代价”最小的进行扩展。

但我们的预估函数有一个基本准则。

基本准则

设从当前状态到目标状态所估计的代价值为$f$。
设未来的搜索中，实际求出的从当前状态到目标状态的实际最小代价为$g$。

则对于任意的状态：$f⩽g$

否则我们的搜索会出现很大的问题：最优解路径上的状态会被错误的估大，然后被压在堆底出不来。

但大家可能会有疑问了：那我们的非最优解路径不就可能先被扩展吗？

这个确实可能发生。

我们如果估值不准确，非最优解路径上的状态$s$就会先被扩展，但是随着“当前代价”的不断累加，在目标状态被取出之前的某个时候：
1.根据$s$并非最优，$s$的“当前代价”就会大于从起始状态到目标状态的最小代价。
2.对于最优解搜索路径上的状态$t$，因为$f(t)⩽g(t)$，所以$t$的“当前代价”加上$f(t)$一定小于等于$t$的“当前代价”加上$g(t)$。

所以，可知道**$t$的当前代价加上$f(t)$小于$s$的当前代价**。因此，$t$就会被从堆中取出来进行扩展。

我们的估价函数越准确，我们的速度就会越快。 所以，设计一个优秀的估价函数十分重要。

$ID{A}^{\ast }$算法

也就是迭代加深的$A^{\ast }$算法。

所谓迭代加深就是每次限制搜索深度， 这样可以在整个搜索树深度很大而答案深度又很小的情况下大大提高效率。

使$k$从$1$开始不断加深枚举， 作为最大步数进行迭代加深搜索判断，而对于不用移动的情况可以一开始直接特判。

例题

1.八数码难题

题目传送门
题解

2.$k$短路

题目传送门
题解