## Heuristic Search

## 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 betterMaybe computers can do better?

*Heuristic:*add up Manhattan distance from each tile to its goal position, smaller is betterHeuristic search doesn't really help the unsat problem

## Sliding Tile Puzzles: Dijkstra's Algorithm

Blind (no heuristic)

*best-first*searchFor 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 againBut at

*sc*the bad path and the good path now have the same heuristic value, but the bad path is longerWe must thus proceed by expanding the good path until it reaches

*sc*

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