Tree Search V.S. Graph Search
對於狀態空間(State Space)的展開可以是無窮盡的，所以我們以下列兩種方式對狀態空間做展開(而不是真的用該data structrue)，可得到相對應的某些特性。
State Space Tree Search :
A state space tree is a tree constructed from all of the possible states of the problem as nodes, connected via state transitions from some initial state as root to some terminal state as leaf.
Alogoritm Pattern
Goal-Test(input:goal state) usually when it is “poped out” from frontier 因為有時候我們將frontier放入Queue時尚且無法保證有optimal solution
State Space Graph Search :
Search Algorithm
Uninformed Search
- Breadth First Search — (BFS)
- Uniform-cost Search
- Depth-first search — (DFS)
- Depth-limited search — (DLS)
- Iterative deepening search — (IDS)
Informed Search
- Greedy search
- A* search
- Iterative deepening A* (IDA*)
- Recursive best-first search (RBFS)
- Simplified memory-bounded A*
Metric Search Algorithm
- Completeness
- Optimality
- Time complexity
- Space complexity
BFS
學過Data Structure / Algorithm 便會知道基本的BFS該怎麼寫，但我實在是看過太多種寫法了(搖頭..)，在AIMA 中居然有整理過的Pattern(So excited)也確實是跟之前學過的寫法是一樣的，不murmur 請看 !!!!!!
UCS
Uniform-Cost Search is equivalent to BFS if step costs are all equal
DFS
同BFS一樣有超多種寫法，甚麼時候goal-test、要不要遞迴… 等等
但其實在Tree Search Pattern只有更換儲存frontier的Data Structure而已。
Frontier = Last In First Out (LIFO) queue,i.e STACK
若以DFS [C.L.S]的寫法來說 : (對於Node u的color欄位)
u.color
- white : not explored
- grey : node in froniter queue
- black : poped out from queue
DLS
DLS = DFS with depth limit l
IDS
IDS = 逐漸放寬標準的DLS
