AI 筆記10 - Informed Search: Greedy search

Heuristics

我們如果對problem有domain knowledge的話，希望能有一個heuristics function告訴我們目前的state“大概”離goal state還有多遠，用“大概”表示heuristics function只是個略算，但已經能大大減少我們瞎繞search space的浪費（如果heuristics正確的話）。

一個例子是在兩個城市間的最短火車路徑搜尋，我們可以有一個heurisitcs table顯示任意兩個城市的”直線距離”：

以下是幾種使用了heuristics的informed search：

Greedy Search

這個approach利用一個heuristics cost function h(n)來提示我們任意兩個城市的直線travel的cost，每次expand node的時候，當然就是找此h(n)最小的者當作child來加入fringe，因為其“greedy”本質。

greedy search不是真正的greedy algorithm，所以不能保證找到optimal solution！

演算法跟UCS幾乎一樣採用min heap，差別在cost function換成heuristics function:

Greedy search討論

假設以下設定：

Consider Greedy Best-First Search on a search space where the branching factor b is finite, the shallowest goal is at finite depth d, step costs are finite, greater than some small positive constant, but not necessarily all equal.

1. 如果search space是finite，completeness是保證的，跟heuristics是否admissible無關。因為有goal到任意node n的cost，所以每次選最小者，一定eventually會選到cost = 0的goal。簡單來說就像一個finite sorted list，總是能夠被iterate完，最差就是走過每一個node。

2. 不保證optimality。即便heuristics是admissible，簡單想如果保證的話，那何必要開發A*?