Graph Traversals for Maze Search

We are going to look at three graph traversal strategies for quickly finding donuts in a maze. The basic idea behind all three is the same: they all visit the node that is next in a data structure they maintain (implementing a stack, queue or priority queue), mark it, and add its unvisited neighbors to the structure. They differ in which nodes they explore first and which they leave for later.

I. Recursive Depth First Search (DFS)

Depth First search (DFS) 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, whenever DFS visits a maze cell c, it recursively searches the sub-maze whose origin is c. This recursive behaviour can be simulated by an iterative algorithm using a stack. A cell can have three states:

Unvisited. The cell has not yet been visited by DFS.
Visit In Progress. The cell has been discovered, but not yet finished. Ie, the recursive search which begins at this node has not yet terminated.
Visited. The cell has been discovered, and the submazes which start at this node have been completely visited also.

The algorithm for DFS is thus:

Depth-First-Search-Kickoff( Maze m )
    Depth-First-Search( m.StartCell )
End procedure

Depth-First-Search( MazeCell c )
    If c is the goal
        Exit
    Else
        Mark c "Visit In Progress"
        Foreach neighbor n of c
            If n "Unvisited"
                Depth-First-Search( n )
        Mark c "Visited"
End procedure

The end result is that DFS will follow some path through the maze as far as it will go, until a dead end or previously visited location is found. When this occurs, the search backtracks to try another path, until it finds an exit.

Note that this assignment asks you to modify the above algorithm to use an iterative solution based on a stack.

See this page for more information on DFS, and this page for a graphical comparison of DFS and BFS.

II. Breadth First Search (BFS)

Breadth First search (BFS) 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, whenever BFS examines a maze cell c, it adds the neighbours of c to a set of cells which it will to examine later. In contrast to DFS, these cells are removed from this set in the order in which they were visited; that is, BFS maintains a queue of cells which have been visited but not yet examined (an examination of a cell c consists of visiting all of its neighbors). Thus, a cell can have three states:

Unvisited. The cell has not yet been visited by BFS.
Visited but Not Examined. The cell has been discovered, but BFS has not evaluated whether its neighbors should be added to the Queue.
Examined. The cell has been visited, and all its neighbours are/have been in the queue (ie, they are already "Visited but Not Examined" or "Examined").

The algorithm for BFS is thus:

Breadth-First-Search( Maze m )
    EnQueue( m.StartNode )
    While Queue.NotEmpty 
        c <- DeQueue
        If c is the goal
            Exit
        Else
            Foreach neighbor n of c
                If n "Unvisited"
                    Mark n "Visited"                    
                    EnQueue( n )
            Mark c "Examined"                
End procedure

The end result is that BFS will visit all the cells in order of their distance from the entrance. First, it visits all locations one step away, then it visits all locations that are two steps away, and so on, until an exit is found. Because of this, BFS has the nice property that it will naturally discover the shortest route through the maze.

See this page for more information on BFS, and this page for a graphical comparison of BFS and DFS.

III. 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).