#heuristics#greedy#a-star#admissibility#dominance#8-puzzle
Heuristic Search
Click a tile next to the blank to slide it.
Goal
0 moves
h1 misplaced0
h2 Manhattan0
h* true moves0
View
Click anywhere to add a state.
Ready
Fringesorted by f
Visited0
Closedset
Properties at a glance
| UCS | Greedy | A* | |
|---|---|---|---|
| Fringe sorted by | f = g | f = h | f = g + h |
| Complete? | Yes* | No** | Yes* |
| Optimal? | Yes | No | if h admissible |
| Time (worst) | b1+⌊C*/ε⌋ | bm | bm |
| Space (worst) | b1+⌊C*/ε⌋ | bm | bm |
Admissible
h(n) ≤ h*(n) for every node: it never overestimates. So h(goal) = 0. No path to a goal: h* = ∞.
Dominance
h2 ≥ h1 everywhere. Both admissible ⇒ A* with h2 never expands more nodes. max(h1, h2) dominates both and stays admissible.
Footnotes
* if every step costs ≥ ε > 0 and b is finite. ** can loop; complete in finite spaces with a closed set. A good h helps on average, not in the worst case.