code

2017年1月29日 星期日

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!

沒有留言:

張貼留言