## Advanced Search

## Sliding Tile Puzzles: Complete Search

Rather than running around randomly, want a solver that is guaranteed to

Return a shortest solution if one exists

Say "no" otherwise

Given sufficient time and memory, of course

## Sliding Tile Puzzles: Breadth-First Search

Examine states in increasing order of distance from start

Guaranteed to eventually hit the goal state if exists

Will not terminate if no solution because "looping"

Use a stop list as before

The alternative is to organize the states in some DAG

Note that the stop list could be used as a priority queue for Dijkstra's Algorithm: This is arguably the way to proceed here

## Sliding Tile Puzzles: Depth-First Search

We could use depth-first search in an attempt to save memory. From start state

Try each possible first move

Recursively solve the resulting state

Never revisit a state

*along the current path*

Will construct long paths for no reason

Still need a stop list (even more)

## Sliding Tile Puzzles: Depth-First Iterative Deepening

Could use

*depth-first iterative deepening*(DFID): artficially cut off search at depth 1, 2, 3, …DFID advantage: uses memory proportional to depth, finds shortest path

Complete but not

*systematic*: "redoing" search is not that expensive because branching factor

## 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