定義
對於problem沒有domain knowledge的search方法。可能有以下幾種search strategy（也就是explore node的順序）：
不過先定義什麼叫explored:
1. goal-test
2. expand children nodes into fringe
BFS (先expand深度最淺者）
下圖中灰色代表放入fringe, 黃色代表被explored，黑色代表此subtree fails（不會再被expand)。
演算法如下：
可以看到其實跟general search的演算法幾乎一樣，差別只在於BFS單純用FIFO queue就可以達成。
分析BFS performance
complete: 如果branching factor(最大children node數目）是有限的，search space就是有限的，我們終究可以找到solution。time: 可以定義成expanded node的數目，假設我們solution在depth = d的時候被expand，則我們總共expand了:
space: 看起來跟time complexity的需求一樣。
optimal: 意思是我們的演算法找到的goal是否是cost最低的？是的，BFS因為找最淺的node，所以如果每次step cost相同的時候，我們保證找到optimal solution。
BFS 是exponential time/space complexity，只有在某些特定的application才適合使用（solution會在很淺的node被找到）:
沒有留言:
張貼留言