Sliding Tile Puzzles: Heuristic Search

  • Prefer moves that make progress toward the goal

  • Wat? Well, humans try to solve one tile at a time from first to last as much as possible. Heuristic: Number of in-place tiles at the front, larger is better

  • Maybe computers can do better? Heuristic: add up Manhattan distance from each tile to its goal position, smaller is better

  • Heuristic search doesn't really help the unsat problem

Sliding Tile Puzzles: Dijkstra's Algorithm

  • Blind (no heuristic) best-first search

  • For this problem, exactly the same as BFS!

  • If the costs of moves are different (in some other problem), this can do better

A✶ Search

  • Maybe adding a heuristic to Dijkstra would help

  • But want to preserve shortest-path

  • A✶ ("a-star") idea: use an "admissible" heuristic — one that is always "optimistic"

  • The heuristic guides us toward the goal: for example, Euclidean distance from the goal on a map

  • Basic idea is Dijkstra, but instead of expanding nodes in order of least distance from the origin, expand in order of least distance from origin plus heuristic distance to goal

  • g(s) is the distance of state s from the origin

  • h(s) is the heuristic distance of state s from the goal

  • "0" is an admissible heuristic, but boring

  • A perfect heuristic eliminates all missteps

Correctness Of A✶ Search

  • Does A✶ preserve the shortest-path property? It does!

  • The proof is tricky and relies on the heuristic being admissible

    • Assume A✶ found a longer "bad" path first

    • That means at some state on the bad path a "correct" next state was not chosen, but instead some worse next state

    • At some state sc (maybe the goal), the paths converged again

    • But at sc the bad path and the good path now have the same heuristic value, but the bad path is longer

    • We must thus proceed by expanding the good path until it reaches sc

  • Original Paper

  • Textbook also discusses. Also CLRS

Sliding Tile Puzzles: A✶

  • Fairly simple modification to Dijkstra

  • Use a priority queue (min-heap), but keyed on g(s) + h(s) instead of just g(s)

  • No separate stop list is needed

  • Expands minimum number of states to goal (theorem)

  • Complete search algorithm: will stop when all states have been examined

  • Will actually stop when out of memory

Last modified: Monday, 5 October 2020, 9:23 PM