A* 算法

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

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

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

它的基本模板是：

CPP

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 优先出队

所以 -- > 该假设不成立

文章操作

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

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

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

它的基本模板是：

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

设当前状态为 $state$

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

反证法：

完美收（汁）

相关推荐

评论

A* 算法

文章操作

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

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

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

它的基本模板是：

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

设当前状态为statestatestate

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

反证法：

完美收（汁）

相关推荐

评论

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

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

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

设当前状态为 $state$