A*可以看成BFS的加强版，或者说BFS就是A*的特殊情况。这里我们在BFS的基础上来逐步介绍A*。我们只考虑路经寻找问题，即寻找从初始状态到目标状态的一条最短路径。我们定义 D[u] 为初始状态到状态 u 的最短路径长度，w[u, v] 为状态 u 到状态 v 的路径长度。
首先我们回顾BFS的过程，我们需要一个队列 queue 保存待扩展节点，一个 hash 表保存待扩展和已经扩展的节点，BFS 过程可以表示如下：
1. 将初始状态加入 queue 和 hash 中
2. while (queue 非空)
3. 取出 queue 尾状态 u
4. 若 u 是目标状态，则 D[u] 为答案，结束算法
5. 枚举每个从状态 u 出发可以到达的状态 v
6. 若从 D[u] + w[u, v] < D[v] 则
7. 更新 D[v] = D[u] + w[u, v]
8. 若 v 不再 hash 中
9. v 入队并加入 hash
10. 不存在所需的路径
不难发现，这个过程与 SPFA 很像。
但是这个算法的效率是很低的，特别对于很多状态空间是无限的问题，BFS可能会迟迟找不到解。究其原因，我们发现，BFS过程完全是按照入队列的顺序扩展状态的，也就是说，如果把状态空间看作一个层次图，BFS 每次只遍历这个层次图的一层，然而每个层次中的大部分状态都是没有用的，可不可以不要去碰这些状态呢？另一方面，对于一些特定的问题，从某个状态出发，往往很容易看出一些后继状态是明显没有“前途”的，那么能不能尽量把这些状态延迟取出，以便加速求解（目标状态可能在这些状态开始扩展之前就到达了，这样就省去了扩展这些节点的操作）？
综合以上两种思路，我们考虑为每个状态 u 设计一个函数 h[u]（通常叫做这个算法的启发函数），表示我们估计从 u 状态到目标状态的最短路径还有多长，设 h*[u] 表示 u 到目标状态的实际最短路径常数。如果我们能直接计算出任意的 h[u]=h*[u]，那么 h[初始状态]=h*[初始状态] 就是答案。但这在大部分的问题中都很难做到。于是我们考虑改进 BFS，每次扩展 h 值最小的状态。但是思考之后可以发现这显然是错的，因为大体上来说一个对于任意一个状态 u 的后继状态 v，一般有 h[u] > h[v]，这样算法就很可能朝着一条路径一直搜索下去，即使找到了目标状态也还是不能保证解的最优性。所以我们考虑“经过状态 u 的最短路径的估计函数”f[u]（同上设最短路径长度的实际值为 f*[u]）。设 g[u]=g*[u] 表示从初始状态到状态 u 的最短路径长度，这可以准确得出，则有：f[u] = g[u] + h[u]。于是算法改为：每次扩展 f 值最小的状态。
但是我们又发现，这样仍然不能保证获得最优解，由于对 h* 估计的不确定性，仍然不能保证第一次找到目标状态时的路径就是最短路径（因为最短路径上的某个状态 u 可能由于错误估计的较大 f[u](h[u]) 值而迟迟得不到扩展），于是我们需要对 h 函数加一些限制，使它能更客观真实地反映一个状态的优劣程度。我们要求对任意状态 u，h[u] 必须满足 h[u] <= h*[u]，即 h[u] 是最短路径的下界。
乍一看找不到反例了，但是这种算法的确能保证第一次遇到的解是最优解吗？答案是肯定的，这种算法正是大名鼎鼎的 A* 算法。首先我们将整个算法流程重新描述如下：
算法正确性的证明分为两步（我的数学很烂，不很会严格证明，大家如果想看严格证明可以自己尝试或者参考《人工智能导论》中的相关章节）：
定理 1. 如果存在一条从初始状态到目标状态的路径，A* 算法一定可以找到这条路径。
说明：容易看出，A* 算法退化到极致之后就是朴素的 BFS，所以只要 BFS 可以找到解，A* 就一定可以找到解（当然，这种证明对于状态空间是无限的问题来说还是有些牵强，不过勉强还能说得过去吧）。
定理 2. 设最优解为 F*。A* 算法未完成时，队列 queue 中一定存在 F[u] <= F* 的状态 u。
说明：在一条最短路径（s、v1、v2、……、vk、t）上的状态 u 显然满足：
f[u] = g[u] + h[u] <= g*[u] + h*[u] = f*[u] = F*
即 u 的估计价值 f[u] 不超过 F*。所以若 A* 算法未完成，则最短路径上的状态就没有全部被扩展，所以一定在这样的状态 u。
定理 3. A* 算法找到的解一定是最优解。
说明：首先根据定理 1，A* 算法一定可以找到解。又根据定理 2，只要 A* 算法未完成，总有 f[u] <= F* 的状态 u，所以 A* 算法每次扩展的状态 u 总有 f[u] <= F*，因而扩展到目标状态时，仍然有 f[t] <= F*，而 F* 为最优解，既有 f[t] = F*，定理得证。
