AI 筆記5 - Search Space

State Space

可以說是一個要解決的問題的所有可能的狀態(state)的集合。

Search Space

在解決問題的過程中，能抵達任何可能的狀態(state)的抽象路徑（藉由sequence of actions)。通常會用search tree 資料結構來model search space，每個state就是一個node。

每個node會有一個expand function，告訴我們怎麼map一個parent node到所有的children nodes。

search nodes 有三種state:

1. explored: 已經explored的nodes 
2. frontier / fringe: 下一批要被explore的unexplored nodes的queue
3. unexplored

所以一開始所有nodes會是unexplored，然後隨著演算法挑選哪些要加入frontier，然後再從frontier去explore所有的frontier nodes。

Tree Search Algorithm

演算法框架如下，簡單來說就是一個個explore node，但什麼順序explore node 則是獨立的演算法(search strategy)，可以視需要抽換，例如BFS or DFS。

上面這個演算法，以下tree就是上面演算法的視覺化：

如果我們用DFS來選擇exploration的順序：

不過這個馬上面臨一個問題，child node A也能再回到parent node B，如果neighbors(A)有包含B的話，這會形成infinite search space，也就是我們演算法會形成無窮迴圈。

改良：graph search with explored set

不過其實可以一開始就講graph search不就好了.... @@

Search Strategies

就是決定fringe裡面哪一個先被explore的順序的演算法。

這個演算法好壞取決於time/space complexity，有以下三個面向：

(1) maximum branching factor b: 一個node最多有幾個action (to children)

(2) 到solution的深度 d

(3) state space的最大深度 m: 這可能是無限的！