AI 筆記7 - Un-informed Search: DFS

DFS(先找最深的node)

演算法跟BFS不一樣只在使用了LIFO stack而非queue。

DFS Performance

complete: 如果不revisit explored node的話，search space是有限的，就會保證我們一定找到solution。

time:  同樣我們定義effort為“expanded nodes數目”。

這邊用m這個參數表示“可能抵達的最大深度”，因為DFS遇到fail node才會backrack，所以可能已經抵達很深的depth = m才backtrack，最後在某個較淺的subtree depth = d找到solution，不過不懂為什麼是以下的式子：

所以當m >> d的時候，那就是一個很糟的problem instㄝance。
但是當 m ~= d的時候，DFS可能會比BFS先找到solution，因為DFS會比BFS expand較少的node。

space: O(bm)。這是一個linear space complexity （只跟m有關）。因為我們只需要儲存目前可以供backtrack的路徑上的nodes即可，所以每個level需要把b個nodes放入fringe，但同時最多只需要放入b*m個。

optimal: NO! 庭院深深深幾許啊！


DFS的linear space complexity遠勝 BFS！