Problem Formulation
以板橋車站坐捷運至台北
Initial State :
ex: 板站
Action :
一個state定義一些action
ex : 板站GO 府中 or GO江子翠
Successor Function :
目前這個state的子集合。input 一個set，output 一個子集合
ex : input 板站，output 江子翠、龍山寺、西門 ......
Goal Test :
判斷是否達到目標
Path Cost :
尋找最佳路徑
Solution :
a set of action
Search Strategies
Completeness (有解?)
Optimality (最佳解?)
Time Complexity
Space Complexity
Notice: Time and space complexity are measured in terms of problem difficulty defined by
- b : successors of any node
- d : depth of the shallowest goal node
- m : maximum depth of the state space (may be infinite)
Search Algorithm
1 . Breadth-First Search ( BFS )
What is BFS ?
A: 簡單來說就是 一層一層搜尋，過程中使用 FIFO 的 queue 儲存
Completeness :
If b is finite, we can find a solution.
Optimality :
YES ， " 可能 " 找到最佳解
Time Complexity :
1 . Assume Root has b successors.
2 . Each node at next level has b successors again.
3 . Assume solution at depth d
4 . Worst case : expand all but the last node at d
Q : 為什麼 last node 例外?
A : 紅點為解，在解之前都會展開子代，所以最後一項要 - b (如圖)
5 . Big O
Space Complexity :
也是 b^(d+1) ，如果每個node都有的話
缺點 :
Space Complexity 是 Exponential 在data比較大的時候會超級大
2 . Depth - First Search (DFS) :
Q : What is DFS ?
A : 深度優先
Completeness :
NO!!! 如果左邊的樹深不見底，且答案在右邊的樹，就找不到了
Optimality :
NO!!!
假如 J是一個解我們會先找到他，但是最佳解在 C
Time Complexity :
由於他是深度優先，所以會跑一邊，長度為 m
Space Complexity :
往下走 m 個點，每個點展開 b >> 優於BFS
缺點 :
m 可能是 " 無窮大 " ， 假如一開始走左邊而答案在右邊，會GG
解決方法 : Depth Limit Search
限制搜尋深度為 l ， 但是設定 l 的值也是個問題，不能太大或太小
3 . Iterative Deepening Search (IDS)
What is IDS ?
改寫 DLS ， l 值慢慢放大。
EX : 100層找不到就101層等等
有點像 BFS + DFS
Completeness :
Yes!! 總有一天 l > d
( no, if infinite paths )
Optimality :
YES if step cost is 1
Time Complexity :
每更新一次limit又要重新做一次
最上面那個一共做 d次以此類推
當 b = 10 d = 5
IDS = 123,450
BFS = 111,100
所以重複做沒有相差很少
Space Complexity :
從 O(bm)改為O(bd)