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!
沒有留言:
張貼留言