A* 算法

· · 个人记录

A* 算法是一种剪枝的BFS算法（它适用于只要没有负权回路的题中，且一定要保证有解）

A*与一般的BFS算法不同之处在于它用到了优先队列。

同时A*算法用优先队列记录了，从起点到当前点的真是距离 + 从当前点到终点的估计距离、

它的基本模板是：

while(!q.empty())
{
  t < -- 取出优先队列队头（小根堆）
  当终点第一次出队时，break;
  for  t的所有临边
    将临边入队
}

接下来要证明给算法的正确性:

设当前状态为state

则 d(state) 表示由起点到state的真实距离，g(state) 表示从state到终点的真实距离， f(state) 表示从state到终点的估计距离。 要想A*算法一定正确 -- >

0 <= f(state) <= g(state) （如果不大于等于0，可能在没有找到最优解时终点就被弹出）

(越接近的话剪掉的状态越多)

那为什么满足这个条件下是对的呢？

反证法：

假设终点第一次出队时，不是最小值 -- >

dist > d最优解 （1）

由于一定有解,所以队列中一定存在一个点在最优路径上（最坏情况下是起点） 设这个点为u，所以

d(u) + f(u) <= d(u) + g(u) == d最优 （2）

所以由（1）和 （2）得：

dist > d最小 >= d(u) + f(u)

因为

dist 优先出队

所以 -- > 该假设不成立

完美收（汁）