A* (A-Star)

A* (A-Star) 是一种搜索算法，对于有多个节点的路径求出最低通过成本。

过程

定义：

• $g$ ：初始状态到当前状态的距离函数；
• $h$ ：当前状态到最终状态的距离函数（估计）；
• $h^{\ast}$ ：当前状态到最终状态的距离函数（精确）；
• $f = g + h$ ：每个点的评估函数。

条件：

1. 如果 $h \leq h^{\ast}$ 恒成立，则函数 $h$ 满足可采纳性，即算法能找到起点与目标节点之间的最短路。

2. 如果对任意节点 $u, v$，满足 $h(v)+h^{\ast}(v, u) \geq h(u)$ 且 $h(u)+h^{\ast}(u,v)\geq h(v)$ （即 $h(v), h(u), h^{\ast}(v,u) / h^{\ast}(u,v)$ 满足三角形不等式），则函数 $h$ 满足一致性，即结点不会被重复加入队列。

A* 算法每次从优先队列中取出一个 $f$ 最小的元素，然后更新相邻的状态。

当 $h=0$ 时，A* 算法变为 Dijkstra；当 $h \gg g$ 时，A* 算法变为 BFS。

P1379 八数码难题

题意：数字华容道，给初始状态，求到达最终状态最小步数，保证有解。

函数 $h$ 可以定义为，没有在正确位置的数字个数。

容易发现 $h$ 满足上述两个性质，此题可以使用 A* 求解。

priority_queue 记得反着写符号。

Submission

P2901 [USACO08MAR] Cow Jogging G

题意：前 k 短路，输出路径长度。

函数 $h$ 可以定义为，反向建图从终点到该节点的最短距离。

最短路一定非长于 k 短路，可采纳性成立，A* 算法可以找到答案。

Submission