《人工智慧》第三周問題集1 informed search － best first search, greedy search

1. 什麼是informed search?

預估哪些action會更好。注意是估計，只是可能比較好，而不一定100%對哦。

2. 什麼是best-first search？

就是每次都挑目前看起來最好的那個action走。

greedy search就是100%依靠目前看起來哪個action最好就走哪個。

A*就是除了這個估計值之外，我們還加上目前為止的cost。

uniform search也是best-fit search的一個特例，它相當於是f(n)=g(n)

所以A*可以看作是greedy＋uniform cost，它的想法就是一方面可以盡量保證uniform cost的optimal，一方面又可以走的更快一些。

3. Greedy Search

greedy search並不保證completeness，舉例：

如果從中山國中到台北車站，那麼可以選擇先去松山機車或南京中路，而松山機場直線距離更短，所以先到松山機場，然後又返回中山國中，然後又到松山機場，陷入死循環。

而graph search則可以規避掉死循環的問題，是complete的。