《人工智慧》第二周問題集2 tree search & graph search

0. tree search 和 graph search是什麼意思？

tree search可不是在tree上的search，graph search也不是在graph上的search！！！

它們都假定你是在一個graph上進行search！

tree search可能會訪問同一個state multiple times。而graph search不會。

1. 為什麼講tree search而不是graph search？

一般來說，graph search更general，但是只要不考慮狀態重複，基本上是一樣的。

2. tree search的過程？

需要注意的是，一般並不在add the resulting nodes to the frontier時候（展開的時候）進行goal test，而是在choose a leaf node from frontier的時候才做goal test。原因是如果一展開就進行goal test，可能給出的並不是最優解。

3. graph search時如果不記住repeated states，最壞會怎樣？

那麼一個linear的搜索可能變成指數級別的搜索。

當狀態空間比較大時，比如說棋盤狀態，這個時候記住所有的states可能會相當大，所以就需要用hashing來減少空間的佔用。

4. graph search的過程？

只有2，9，11行和tree search不同。

5. 在實現時，state叫做什麼？

node。在實現時，為了記錄action sequence，所以會記錄parent，path cost等。

6. frontier在實現時用什麼實現？

不同的search algorithm實際上就是不同的queue。

7. 如何來描述不同的search strategy？

要注意的一點是，search algorithm的瓶頸一般不出現在time complexity，而是出現在space complexity上，比如上面提到的repeated states的問題。