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:
- explored: 已經explored的nodes
- frontier / fringe: 下一批要被explore的unexplored nodes的queue
- 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: 這可能是無限的!
沒有留言:
張貼留言