In an uninformed search, only the goal test and the successor function are known. Uninformed search algorithims generate a search tree without any domain specific knowledge, i.e. heuristic values.
BFS expands the shallowest node first, then ripples out.
BFS uses a queue, which is a first-in-first-out (FIFO) data structure.
Pseudocode
Complete? Yes!
Optimal? Yes if edge cost is constant
Time complexity: O(bd)
Space complexity: O(bd)
where b = branching factor (assume finite), d = goal depth
UCS proceeds like BFS but instead of expanding the shallowest node, UCS expands the node with the least cost first. This is done using a priority queue.
Complete? Yes!
Optimal? Yes!
Time complexity: O(bC*/ε)
Space complexity: O(bC*/ε)
where b = branching factor (assume finite), C* = optimal path cost to the goal, ε = minimum cost of an action
DFS expands the deepest node first.
DFS uses a stack, which is a last-in-first-out (LIFO) data structure.
Pseudocode
Complete? Nope!
Optimal? Nope!
Time complexity: O(bm)
Space complexity: O(bm)
where b = branching factor (assume finite), m = graph depth
IDS combines the completeness and optimality of BFS with smaller space complexity of DFS. IDS repeatedly performs DFS with a depth limit, incrementing the limit until the goal is found.
Complete? Yes!
Optimal? Yes if edge cost is constant
Time complexity: O(bd)
Space complexity: O(bd)
where b = branching factor (assume finite), d = goal depth
Bidirectional search involves two simultaneous breadth-first searches, one that starts at the initial state and one that starts at the goal node.
Complete? Yes!
Optimal? Yes if edge cost is constant
Time complexity: O(bd/2)
Space complexity: O(bd/2)
where b = branching factor (assume finite), d = goal depth
| Complete | Optimal | Time | Space | |
| BFS | Yes | Yes if* | O(bd) | O(bd) |
| UCS | Yes | Yes | O(bC*/ε) | O(bC*/ε) |
| DFS | No | No | O(bm) | O(bm) |
| IDS | Yes | Yes if* | O(bd) | O(bd) |
| BIBFS | Yes | Yes if* | O(bd/2) | O(bd/2) |
b = branching factor, d = goal depth, m = graph depth, C* = optimal path cost to the goal, ε = minimum cost of an action
*edge cost is constant or positive non-decreasing in depth