Search Algorithms Comparison
Uninformed vs Informed Search
Uninformed Search (Blind Search)
Algorithms that explore without knowledge of the goal location. Examples include Breadth-First Search (BFS) and Depth-First Search (DFS).
- Breadth-First Search (BFS): Explores all neighbors at the current depth before moving to the next depth. Guarantees the shortest path in unweighted graphs but explores extensively in all directions.
- Depth-First Search (DFS): Explores as deep as possible along each branch before backtracking. Does not guarantee the shortest path and may get stuck in infinite loops on infinite graphs.
Deep Dive: Algorithmic Characteristics
Choosing the right algorithm depends on the requirements: Do you need the absolute shortest path? Is memory a constraint?
The Trade-off: BFS vs. DFS
BFS uses significant memory to store all nodes at the current depth (frontier). In a grid with branching factor b and depth d, BFS stores O(b^d) nodes. This is often impractical for large maps.
DFS is memory efficient, storing only the current path and unexplored neighbors of nodes on that path O(d). However, it may wander down an infinite path or return a path far from the shortest, making it unsuitable for most shortest-path problems.
Informed Search (Heuristic Search)
Algorithms that use domain knowledge (a heuristic) to guide the search towards the goal. Examples include Greedy Best-First Search, Dijkstra's Algorithm, and A*.
- Greedy Best-First Search: Expands the node that appears closest to the goal based on the heuristic. Fast, but not optimal.
- Dijkstra's Algorithm: Explores nodes in order of their cost from the start node. Guarantees optimality but explores uniformly in all directions.
A* Algorithm: The Best of Both Worlds
A* combines the cost-optimality of Dijkstra's algorithm with the goal-oriented focus of Greedy Best-First Search.
The core formula is:
f(n) = g(n) + h(n)
- g(n): The actual cost from the start node to node n.
- h(n): The heuristic estimate from node n to the goal.
- f(n): The total estimated cost of the path through node n.
A* is efficient because it prioritizes nodes with lower f(n). If the heuristic h(n) is admissible (never overestimates the cost), A* is guaranteed to find the shortest path.
Step-by-Step Visualization Example
Consider a simple 3x3 grid. A* expands nodes based on the lowest f(n) value. Below is a conceptual state table during the search:
| Step | Open Set | Closed Set | Focus (Lowest f) |
|---|---|---|---|
| 1 | {Start} | {} | Start |
| 2 | {N1, N2} | {Start} | N1 |
| 3 | {N2, N3, N4} | {Start, N1} | N2 |
The Open Set holds candidates for exploration, while the Closed Set contains nodes already evaluated. A* iteratively picks the best candidate from the Open Set until the goal is reached.
Performance Comparison
| Algorithm | Optimal | Complete |
|---|---|---|
| BFS | ✓ | ✓ |
| DFS | ✗ | ✗ |
| DFS | ✗ | ✗ |
| Greedy | ✗ | ✗ |
| Dijkstra | ✓ | ✓ |
| A* | ✓ | ✓ |