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:

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.