Best-First Search Technique

Best-first search combines the systematic bookkeeping of breadth-first/depth-first search with the guidance of a heuristic: at every step it expands the node in the frontier that currently looks most promising, regardless of where in the tree it lies.

OPEN and CLOSED Lists

Algorithm

1. Put the initial state on OPEN.
2. If OPEN is empty, fail.
3. Remove from OPEN the node n with the best heuristic value; put n on CLOSED.
4. If n is a goal state, return the path to n and stop.
5. Expand n, generating its successors. For each successor:
   - If not already on OPEN or CLOSED, compute its heuristic value and add to OPEN.
   - If already on OPEN/CLOSED with a worse path, update it with the better path found.
6. Sort OPEN by heuristic value (or insert in sorted position).
7. Go to step 2.

A* Search — Best-First With a Guarantee

**A-star (A)* is the most important best-first algorithm. It evaluates each node n using:

f(n) = g(n) + h(n)

Admissibility: if h(n) never overestimates the true remaining cost (h(n) is less than or equal to the true cost to goal, for every n), A* is guaranteed to find an optimal solution.

Worked Mini-Example (8-Puzzle)

A common admissible heuristic for the 8-puzzle is h = number of misplaced tiles, or the stronger h = sum of Manhattan distances of each tile from its goal position. A* using Manhattan distance expands far fewer nodes than blind BFS because f(n) actively steers the search toward the goal.

Strengths and Weaknesses