《人工智慧》第二周問題集3 uninformed search - bfs/uniform-cost search

1. 什麼是uninformed search?

就是只使用problem definition的信息，即initial state, goal state, transition model, path cost/step cost這些信息，而不對走哪裡更好進行猜測。所以也叫做blind search。

2. BFS

因為BFS是返回比較淺的解，所以一般情況下並不是最優解。

3. uniform cost search

BFS是uniform cost search的特例。

當step cost相同時，uniform cost search就是BFS。

當作graph search時，如果有重複的state，選擇其中那個path cost最小的path留下來。

time complexity和space complexity和bfs一樣都是指數級的。

4. 為什麼叫做uniform cost search？

In what sense is 「Uniform-cost search」 uniform?

推薦閱讀：