#bfs#dfs#ucs#dls#ids
Uninformed Search
View
Click anywhere to add a state.
Ready
FringeFIFO queue
Visited0
Closedset
Properties at a glance
| BFS | UCS | DFS | DLS | IDS | |
|---|---|---|---|---|---|
| Fringe | FIFO queue | priority queue (g) | LIFO stack | stack, depth ≤ l | DLS, l = 0, 1, 2 … |
| Complete? | Yes | Yes* | No | if l ≥ d | Yes |
| Optimal? | Yes** | Yes | No | No | Yes** |
| Time | bd+1 | b1+⌊C*/ε⌋ | bm | bl | bd |
| Space | bd+1 | b1+⌊C*/ε⌋ | b·m | b·l | b·d |
Symbols
b branching factor · d depth of the shallowest goal · m longest path (may be ∞) · C* optimal cost · ε smallest action cost.
Footnotes
* complete if every action costs > 0. ** optimal only if all actions cost the same (they find the shallowest goal).
Rule of thumb
Large space, unknown solution depth: use IDS. It is complete like BFS and needs only linear memory like DFS.