Path finding on a grid
Runs breadth-first, depth-first, uniform-cost, greedy best-first, A*, and weighted A* search on a grid with walls you draw, one expansion at a time, alone or two side by side.
- Lecture reference: Informed Search · slides 23–24
- Lecture reference: Informed Search · slides 38–40
Search
Grids use graph search: a cell enters the explored set when it is expanded and is never added to the frontier again; a cheaper path to a cell already on a priority-queue frontier replaces it. Lecture reference: Solving Problems by Searching · slide 36
Grid 32 × 22
A* search
Priority queue ordered by f(n) = g(n) + h(n)- Expanded
- 0
- Generated
- 1
- Frontier
- 1 max 1
- Path
- Not found yet
Heuristics
| Heuristic | h(n) | Admissible with |
|---|---|---|
| Manhattan distance h(n) = |dx| + |dy| | |dx| + |dy| | 4-connected moves only (exact without walls, 4-connected) |
| Euclidean distance h(n) = √(dx² + dy²) | √(dx² + dy²) | 4- and 8-connected moves |
| Octile distance h(n) = max(|dx|, |dy|) + (√2 − 1)·min(|dx|, |dy|) | max(|dx|, |dy|) + (√2 − 1)·min(|dx|, |dy|) | 4- and 8-connected moves (exact without walls, 8-connected) |
| Chebyshev distance h(n) = max(|dx|, |dy|) | max(|dx|, |dy|) | 4- and 8-connected moves |
| Zero (h = 0) h(n) = 0 | 0 | 4- and 8-connected moves |
dx and dy count the columns and rows between a cell and the goal. An admissible heuristic never overestimates the true cost h*(n) Lecture reference: Informed Search · slide 25. Weighted A* orders the frontier by g(n) + α·h(n); with an admissible h its path costs at most α times the optimal cost Lecture reference: Informed Search · slide 38. With h = 0, A* is uniform-cost search.
Questions from the slides
When is UCS equivalent to BFS?
Lecture reference: Uninformed Search · slide 45Show answer
How can we fix the greedy problem?
Lecture reference: Informed Search · slide 15