AI 筆記11 - Informed Search: A* Search

對Heuristics的改良

光是靠heuristics function h(n)容易找出non-optimal solution，因為h(n)提供的是估算，而不是真正的cost function。A* search結合了真正的cost function g(n)和h(n)，形成一個combined estimated cost function f(n):

root到某個node n先用g(n)來計算，而n到goal則用h(n)來計算，所以root到goal的"estimated cost"是一個混合真實cost和heuristics cost的function:

演算法跟UCS也是幾乎一樣，只差別在使用了f(n)而非真實的cost function:

城市旅行最短距離範例

在initial state，root到root的cost g(root) = 0，所以一開始的estimated cost只有h(goal) = 180:

 expand root node之後：

以此類推下去。

Admissible Heuristics

不過heuristics估計出來的cost，要小於等於真實的cost，否則在A*中我們不一定能找到optimal solution！

admissible定義如下：

以地圖搜尋的h(n)來說，兩個城市間的直線距離一定是 <= 真實的cost（相當於飛機路線與公路路線），所以是一個admissible heuristics，所以保證了找到optimal solution。

舉8-puzzle例子來說，假設我們的start state和goal state如下：

所以真實的cost g(goal) = 26。
我們可以採用以下兩種admissible heuristics h(n):

h1(n): 總共錯置的tile數目（或說放對的數目也可），上圖h1(n) = 8
h2(n): 所有tile到goal state狀態的manhattan distance，上圖h2(n)對tile 1~8依序來說是 = 3 + 1 + 2 + 2 + 2 + 3 + 2 + 2 = 18，這是一個較好的heuristics，能expand較少數目nodes。

兩者都小於等於true cost（不過應該要證明對每個state都是這樣，課堂中並無證明），所以即便有優劣之分，都是能幫助A*找到optimal solution。

A* performance

complete: 是的，我們一定會找到solution（如果有的話）。
time: exponential
memory: exponential (把所有nodes都放入記憶體中）

optimal: YES! if heuristics is admissible

Optimality Proof

欲證明下面理論：

假設在search tree中有兩個solution node Go (optimal)和Gs (sub-optimal)，且某個node n在optimal path上：

estimated cost:
f(Go) = g(Go) + h(Go) = g(Go)  /* 因為h(Go)根據定義為Go到Go的距離 = 0 */
f(Gs) = g(Gs) + h(Gs) = g(Gs)
所以我們得出 f(Go) = g(Go) = true cost from root to Go，同理f(Gs) = true cost from root to Gs

由於Go is optimal，所以f(Go) < f(Gs)

我們只要證明，A* tree search不會選擇sub-optimal path：亦即任何在optimal path上的node n的estimated cost f(n)都小於f(Gs)，A*永遠不會選擇f(Gs)。

已知n在optimal path上，且heuristics is admissible，則for all n:
h(n) <= h*(n)  /* 這是n到goal node Go的true cost */

如果不等式左右邊兩加上g(n):
f(n) = g(n) + h(n) <= g(n) + h*(n) = true cost from root to goal node = f(Go)

所以f(n) <= f(Go)

根據以上兩個綠色的結論，得證 f(n) <= f(Go) < f(Gs)。

A* search討論

對使用兩個城市之間的直線距離當作heuristics的problem來說，假設以下條件：

n lecture, we see an example of a heuristic for the map problem; that is, the straight line distances h_SLD(n) from n to the goal. Consider A-Star Search applied to this instance of the search problem, using the straight-line distance heuristic (in particular, note that no edges are less than unit cost).

1. 所有的search algorithm都不管最後有幾個step，除非cost function跟此有關，但這邊的cost function是total distance。

2. A*保證在heuristics為admissible的時候是optimal，而此h_SLD function是admissible，因為直線距離永遠大於經過任意第三點的距離。

3. 每個step (explore新的node) 並沒有一定更靠近goal，因為g(n)是一直被update的，例如可能g(a) + h(a) < g(b) + h(b)，所以先選node a expand，但是可能發現a有路到b，所以update g(b)後始得  g(a) + h(a) > g(b) + h(b)。