《人工智慧》第二周問題集4 uninformed search - dfs/iterative deepening search

1. DFS

最常用的實現方法是recursion，也可以用LIFO queue。

time complexity要比bfs更糟，m是最深的層數。

dfs既不complete，又不optimal，time complexity又比bfs還要糟，那還為什麼要介紹dfs？

但是它的space complexity很低！

2. Depth-Limited Search(DLS)

對於bfs來說，completeness/optimal/time complexity都還好，而dfs這三項不行，但是space complexity很好，所以能不能combine這兩種方法？

先來解決completeness問題，在depth infinite的時候，dfs不completeness（陷入最左邊分支的黑洞了），最簡單的方式就是限制深度。

如果解不在l層以內，那麼則不complete。

3. 還能再改進嘛？

Iterative-Deepening Search(IDS)

想法就是把深度的限制慢慢的放寬。

那麼會重複搜索會不會很慢？從時間複雜度來看這些項都被忽略掉了，因為相比limit＝l時都不是一個數量級。

但實際上浪費的並不多，只是看起來很浪費。數學上可以算出來差別大概只有10%。

IDS的一個使用場景是棋類，因為一般比賽都有時間上的要求，所以可以根據剩餘的時間選擇搜索的深度。

4. 下面介紹另外一種search：Bidirectional Search

如果我們直到goal state的話，我們也可以從goal往回展。

但是這種方法的限制比較大，一個是我們不一定直到goal state，並且因為要把兩個search tree對起來，space complexity也會增加到指數級別。

5. 總結