Optimality of A* Search

Theorem. A* using TREE-SEARCH is optimal if h(n) is admissible.

Proof. 這裡用直覺的說法證明，正式陳述只是反映這個直覺。要證明 A* 會先走到 optimal goal state G，就是證明 A* 不會在那之前走到任何 suboptimal goal state G_2。如果 G_2 根本沒出現在 fringe 裡頭，那當然沒機會走到；如果 G_2 出現了，考慮下面的示意圖。到 G_2 的距離會比到 G 的距離還要遠（因為它是 suboptimal）。因為 h(n) 是個「樂觀的」admissible heuristic，它估出的距離總是比較短。所以當我們在 n 點時，我們會樂觀地以為到 G 的距離比實際上近，而實際上的距離又比「到 G_2 的距離」更近。這段論證對通往 G 沿途上的所有 states 都成立，所以抵達 G 以前，G_2 永遠不會被選到。

--
關鍵當然在 "admissible"。

---

Theorem. A* using GRAPH-SEARCH is optimal if h(n) is consistent.

很可惜，我還沒有寫得出來的直覺證明，目前只能用書上的代數方法做，那就不用特地重打一次了 XD。