A* 搜索的评估函数为 ，其中：
- 是从初始状态到节点 n 的实际代价。
- 是从节点 n 到目标状态的估计代价（启发式函数）。
A 树搜索 (Tree Search) 的最优性*
证明 A* 树搜索最优性的条件是启发式函数 是可采纳的 (admissible)。 一个启发式函数是可采纳的，如果它从不估计过高实际到达目标的代价，即对于所有节点 n，，其中 是从 n 到达目标的实际最小代价。
证明思路 ：
假设存在一个最优目标节点 G 和一个次优目标节点 G′。我们需要证明 A* 算法会先选择 G 而不是 G′ 进行扩展。
证明步骤 ：
- 假设 G′ 已经存在于前沿（fringe/open list）中。
- 假设在通往最优目标节点 G 的路径上，存在某个节点 n 也在前沿中。
- 我们需要证明节点 n 会在 G′ 之前被选择扩展。
- 步骤 1：证明
- 根据 f 函数的定义：。
- 因为启发式函数 h 是可采纳的，所以 （从 n 到 G 的真实最小代价）。
- 因此，。
- 就是通过节点 n 到达最优目标节点 G 的实际最小代价，即 。
- 由于 G 是目标节点，所以 。因此，。
- 所以，。
- 步骤 2：证明
- 因为 G 是最优目标节点，G′ 是次优目标节点，所以从初始状态到达 G 的实际代价小于到达 G′ 的实际代价，即 。
- 由于 G 和 G′ 都是目标节点，它们的启发式函数值都为 0 ()。
- 因此， 且 。
- 所以，。
- 步骤 3：得出结论 n 会在 G′ 之前扩展
- 综合步骤 1 和步骤 2，我们得到。
- A* 算法总是选择前沿中 f 值最小的节点进行扩展。因此，节点 n（最优路径上的祖先节点）会在次优目标节点 G′ 之前被扩展。
- 这个逻辑可以推广到最优路径 G 上的所有祖先节点都会在 G′ 之前被扩展。最终，最优目标节点 G 会在任何次优目标节点 G′ 之前被从前沿中取出并扩展。
因此，如果启发式函数是可采纳的，A* 树搜索算法是最优的。
