这在Russell & Norvig的相应章节（第 3.5 章，第 93 至 99 页（第三版））中有很好的介绍。查看更多详细信息。

首先，让我们回顾一下定义：

您对可接受和一致的定义是正确的。

可接受的启发式基本上只是“乐观的”。它从不高估距离。

一致的启发式是您对状态之间距离的先前信念是自洽的。也就是说，您不会认为从 B 到目标花费 5，从 A 到 B 花费 2，而从 A 到目标花费 20。不过，你可以过于乐观。所以你可以相信从 B 到目标是 5，从 A 到 B 是 2，从 A 到目标是 4。

树搜索是一种用于搜索具有树结构的问题的通用搜索策略：也就是说，永远不可能从较晚的状态“双回”到较早的状态。这模拟了某些类型的游戏，例如井字游戏。树搜索不记得它已经访问过哪些状态，只记得它还没有访问过的状态的“边缘”。

图搜索是一种用于搜索图结构问题的通用搜索策略，在这种情况下，可以翻倍回到较早的状态，就像在国际象棋中一样（例如，两个玩家都可以来回移动他们的国王）。为了避免这些循环，图搜索还跟踪它已处理的状态。

有关树与图搜索的更多信息，请参阅此答案。

好的，现在让我们来谈谈证明背后的直觉。

我们首先要证明

如果$h(n)$是可接受的，使用树搜索的 A* 是最优的。

通常的证明是反证法。

1. 假设具有树搜索和可接受启发式的 A* 不是最优的。

2. 非最优意味着 A* 发现的从起点到目标的第一条完整路径（称为$q$) 将比其他路径更长$p$, A* 探索到某个状态$s$，但没有进一步。

3. 由于启发式是可接受的，因此达到目标的估计成本来自$s$必须小于真实成本。

4. 到 3 岁，而且我们知道要达到多少成本$s$沿着$p$, 估计的总成本$p$，因此扩展成本$s$必须小于真实成本$p$.

5. 由于真实成本$p$小于成本$q$（乘以 2），估计的扩展成本$s$必须小于真实成本$q$.

6. A* 总是选择总成本最有希望的路径进行下一步扩展，扩展目标状态的成本由到达它所需的总路径长度给出。

7. 5 和 6 形成矛盾，所以我们在 1 中的假设一定是不正确的。因此 A* 必须是最优的。

图搜索证明使用了非常相似的想法，但说明了您可能会循环回到早期状态的事实。