AI 筆記8 - Un-informed Search: Depth limited search & Iterative Deepening

Depth limited search

DFS可能會在某個subtree極端深入，但是最後是fail node。我們要限制factor m，可以定義一個最大搜尋深度限制factor L。這通常在我們對problem有domain knowledge的時候（那不能放入un-informed search吧？！）。

Iterative Deepening: 

這其實是DFS的變形，但卻有深度限制控制：

我們照常做DFS，但是每個iteration只停在搜尋深度限制L。
下一個iteration我們會放寬factor L，直到我們找到最淺層的solution，由於深度被控制，每個iteration疊加起來看起來有點像是BFS。見以下範例：

Optimal if path costs are positively identical: 因為每個depth的subtree一定會整個search完，不會是像default DFS一樣在哪一個branch找到goal node就放棄了其他的sibling brach。