## Best-first search

Best-first search is an algorithm that traverses a graph in
search of one or more goal nodes. As we will discover in a few weeks, a
maze is a special instance of the mathematical object known as a "graph".
In the meantime, however, we will use "maze" and "graph"
interchangeably.

The defining characteristic of this search is that, unlike
DFS or BFS (which
blindly examines/expands a cell without knowing anything
about it or its properties), best-first search uses an evalutation
function (sometimes called a "heuristic") to determine which object
is the most promising, and then examines this object. This "best first"
behaviour is implemented with a PriorityQueue.
The algorithm for best-first search is thus:

**Best-First-Search**( Maze *m* )
Insert( *m*.StartNode )
Until PriorityQueue is empty
*c* <- PriorityQueue.DeleteMin
If *c* is the goal
Exit
Else
Foreach neighbor *n* of *c*
If *n* "Unvisited"
**Mark ***n* "Visited"
Insert( *n* )
**Mark ***c* "Examined"
**End procedure**

For our maze runners, the objects which we will store in the
PriorityQueue are maze cells, and our heuristic will be the cell's
"Manhattan distance" from the exit. The Manhattan distance is a
fast-to-compute and surprisingly accurate measurement of how
likely a MazeCell will be on the path to the exit. Geometrically,
the Manhattan distance is distance between two points if you were
only allowed to walk on paths that were at 90-degree angles from
eachother (similar to walking the streets of Manhattan).
Mathematically, the Manhattan distance is:

` | cell`_{x} - exit_{x} | +
| cell_{y} - exit_{y} |

(Sometimes, the Manhattan distance is scaled up by a constant factor,
to ensure unique values for each cell.)
The end result is that best-first search will visit what it thinks
are the most promising cells first, which gives best-first some of the
nice properties of both BFS and DFS. However, this leaves best-first search
vulnerable to bad heuristics, or certain types of mazes which exploit
weaknesses of certain heuristics.

See
this page for more information on various heuristics (they will
use game theory terminology).

CSE 326 Summer 2003 Homepage