2007/10/06

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。

Labels:

<< 回到主頁