我不明白证明$A^*$是最优的。

证明是矛盾的：

认为$A^*$返回$p$但存在一个$p'$那更便宜。什么时候$p$从边界中选择，假设$p''$（这是路径的一部分$p'$) 是从边界中选择的。自从$p$之前被选中$p''$，那么我们有$\text{cost}(p) + \text{heuristic}(p) \leq \text{cost}(p'') + \text{heuristic}(p'')$.$p$以目标结束，因此$\text{heuristic}(p) = 0$. 所以$\text{cost}(p) \leq \text{cost}(p'') + \text{heuristic}(p'') \leq \text{cost}(p')$因为启发式是可以接受的。所以我们有矛盾。

我很困惑：我们难道不能假设有一条更便宜的路径位于更靠近起始节点的边界上吗？$p$? 或者是不可能的证明的一部分，因为$A^*$会检查那条路径，因为它就像具有最低成本搜索的 BFS，所以，如果有更便宜的路径，它会处于更远的边界吗？