code

2017年1月25日 星期三

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: 這可能是無限的!



沒有留言:

張貼留言