Hot-Link Menu in Right-Side Column

Last Updated 6-29-2010


Depth-First Search

Depth-First search always expands the deepest node in the current frontier of the search tree. The progress of the search is illustrated in Figure DFS-1. The search proceeds immediately to the deepest level of the search tree, where the nodes have no successors. As those nodes are expanded, they are dropped from the frontier, so then the search "backs up" to the next deepest node that still has unexplored successors:

Depth First Progress

Figure DFS-1: Progress of Depth-First Search


The unexplored region is shown in white, the frontier in blue, and the explored region is depicted in gray. The arrow is pointing at the node that is currently under expansion.

The depth-first search algorithm is an instance of the graph-search algorithm in Figure Agents-7; whereas breadth-first search uses a FIFO queue, depth-first search uses a LIFO queue. A LIFO queue means that the most recently generated node is chosen for expansion. This must be the deepest unexpanded node because it is one deeper than its parent - which, in turn, was the deepest unexpanded node when it was selected.

As an alternative to the Graph-Search-style implementation, it is common to implement depth-first search with a recursive function that calls itself on each of its children in turn.

The properties of depth-first search depend strongly on whether the graph-search or tree-search version is used. The graph-search version, which avoids repeated states and redundant paths, is complete in finite spaces because it will eventually expand every node. The tree-search version, on the other hand, is not complete - for example, in Figure Agents-6, the algorithm will follow the Arad-Sibiu-Arad-Sibiu loop forever. Depth-first tree search can be modified at no extra memory cost so that it checks new states against those on the path from the root to the current node; this avoids infinite loops in finites state spaces but does not avoid the proliferation of redundant paths. In infinte state spaces, both versions fail if an infinite non-goal path is encountered.

Listed below is the pseudocode for the Depth-First Search Algorithm:

Function Depth-First Search(Initial State, Goal) returns Success or Failure
  If (InitialState==Goal) return Success
  NodeInitialState
  NodeGoal
  Frontier(LIFO)InitialState,InitialStateChild
  ExploredNULL
  GoalFoundFalse
  while Frontier != NULL
    ParentNode,ChildNode=Frontier.POP
    Explored←ParentNode
    NewChildFound←false
    while still more Children
      If Child==Goal GoalFound= True
      If GrandChild ∉ Explored && GrandChild ∉ Frontier then
        Frontier←ChildNode,GrandChild
        NewChildFoundTrue
      End If
      Child←NextChild
      End while
    End While
  return GoalFound

Figure DFS-2: Pseudocode for Depth-First Search


Using Figure DFS-2 as a guide, we will begin to develop working code using C++ for a Depth-First Search solution to the Romanian map problem.

C++ Code Solution for Depth-First Search Example

As in the solution for the Breadth-First Search we begin by developing a data stucture to contain the information in the following diagram:

Romania map

Figure DFS-3: Data Source for C++ Depth-First Code Example


C++ Depth-First Data Structure

However, unlike the Breadth-First solution, the Depth-First solution requires a bit more complexity in the data structure container. In the breadth-first search example, once a node was completed, it was possible to no longer consider that node during the rest of the search. In the Depth-First search, however, we must keep a node "open" during expansion, while we continually expand the children of the node, until we reach the lowest level of the search tree. For this reason, we will use a Class data structure for both the City data structure as well as the PathRecord data structure:

//Structure for Adding Edge to Graph

struct Neighbor			
{					
	string Name;			
	int Distance;			
	int ShortestDistance;	
};					

//Class Data Structure for City type Node:

class	City								
{									
public:								
	string				Name;							

	City( );							
	City(string);							

	vector<Neighbor>		Neighbors;			
	vector<Neighbor>::iterator	NeighborNumber;

	void	AddNeighbor	(string, int);			
		

};	

//Parameterless Class constructor								

City::City( )
{
	Name="";
	NeighborNumber=Neighbors.begin( );
}

//Class Constructor with Name supplied:

City::City(string CityName)
{
	Name=CityName;
	NeighborNumber=Neighbors.begin( );
}

//Function or Method to Add Connected Node to City data structure

void	City::AddNeighbor(string NeighborName, int NeighborDistance)
{
	Neighbor TempNeighbor;
	TempNeighbor.Name=NeighborName;
	TempNeighbor.Distance=NeighborDistance;
	Neighbors.push_back(TempNeighbor);
	NeighborNumber=Neighbors.begin( );
}

//Data Structure for Entire Map

vector<City>	Cities;
						

Figure DFS-4: Map Data Structure for Romanian Map Depth-First Search Solution


Listed below is an explanation of the coding statements in Figure DFS-3: C++ code for Depth-First Search Solution:

  • struct Neighbor: this statement describes the information between the city and each of the connected cities. This construct could also be thought of as a Graph->Edge.

    • string Name: Declaration for the Name of the destination, or Child Name from our current position.

    • int Distance: Distance, or cost from current location to destination (Child Node).

  • class City: Data structure used to describe current location. A class structure is used as it allows us to conveniently initialize and modify the associated parameters.

    • string Name: Set of characters used to give a unique name to reference each location on the map.

    • City( ): Constructor used when a City data type is declared with no parameters supplied.
      • Example: City CurrentCity;

      • This type of constructor will create a blank City with no Name and no Neighbors.

    • City(string): Constructor used whe an City data type is decleared with the Name parameter supplied.

      • Example: City CurrentCity("Arad");

      • This type of constructor will automatically name the city when it is declared.

    • vector Neighbors: An array-like construct containing information about the Neighbors.
      • Each City connected to another city is a Neighbor.

      • Zerind, Sibiu, and Timisoara are Neighbors to Arad.

      • Example: CurrentCity.Neighbor.Name="Zerind";

    • vector::iterator NeighborNumber: Index used to step through array of Neighbors.

      • Example: CurrentCity.NeighborNumber=CurrentCity.Neighbors.begin();

        • Sets CurrentCity.NeighborNumber to the first Neighbor of Current City.

    • void AddNeighbor (string, int): Function used to create a Neighbor for the current city data structure.

      • Example: CurrentCity.AddNeighbor("Zerind",75);

        • Will add Zerind as a Neighbor to Arad (the Current City) with a distance of 75 units.

  • City::City( ): Declaration for instructions to create a City data type when no parameters are supplied.

    • Name="": Set the name to a blank string, so it can be named later.

    • NeighborNumber=Neighbors.begin( ): Set the index to the beginning of the empty array.

  • City::City(string CityName): Declaration for instructions to create a City data type when the name is supplied at the time of creation.

    • Name=CityName: Set the Name descriptor to the supplied City Name parameter.

    • NeighborNumber=Neighbors.begin( ): Set the index to the beginning of the empty array.

  • void City::AddNeighbor(string NeighborName, int NeighborDistance): Declaration for instructions to create a new neighbor to the referenced City data construct.

    • Neighbor TempNeighbor: Create a temporary Neighbor construct to move data into the vector.

    • TempNeighbor.Name=NeighborName: Set the Name descriptor of the Neighbor with the supplied parameter name.

    • TempNeighbor.Distance=NeighborDistance: Set the Distance descriptor of the Neighbor with the supplied parameter name.

    • Neighbors.push_back(TempNeighbor): Increase the size of the vector array and save the new Neighbor data in it.

    • NeighborNumber=Neighbors.begin( ): Since we changed the size of the vector the beginning and ending locations are no longer valid, so our counter must be reset to the new location.

  • vector Cities: vector (array) data structure where each element contains all the data for 1 City.

In order to continue with this guide, and start the discussion of Depth-First Search Make Map Function and the associated C++ code to perform the operation: Press the Button below:

Home


Artificial Intelligence

Big O Notation

NP Completeness

Intelligent Agents


Problem Definition

Formulating Problems

Toy Problems

Vacuum World


8-Puzzle

8 Queens

The Knuth Sequence

Real World Problems

Route Finding Problems

Touring Problems

Traveling Salesperson Problem

VLSI Layout

Robot Navigation

Automatic Assembly Sequencing


Searching For Solutions


Frontier Node Expansion

Search Algorithm Infrastructure

Child Node Creation

Measuring Algorithm Performance


Uninformed Search Strategies

Breadth-First Search

Breadth-First Characteristics

C++ Breadth-First Search Code

Breadth-First Data Structure


Breadth-First Main Program

Breadth-First Make Map

Breadth-First Make Neighbor

Breadth-First Point of Origin


Breadth-First Print Cities

Breadth-First Initial Listing


Breadth-First Path Record

Breadth-First Get Child City

C++ Breadth-First Search Code


Breadth-First Print Goal Path

Uniform-Cost Search


Depth-First Search

Depth-First C++ Solution

Depth-First Data Structure


Depth-First MakeMap()

Depth-First Display Data

Depth-First Initial Listing


Depth-First GetChildCity()

Depth-First Path Record


Depth-First Search Function


Depth-First PrintGoalPath()

Depth-First Main()

Depth-Limited Search


Iterative Depth Search

Bidirectional Search

Comparing Strategies


Informed Search Strategies

Greedy Best-First

A* Search


Conditions For Optimality

Optimality of A*


C++ A* Search Code

A* Search Data Structure

A* Search Data Entry


A* Search GetChildCity()

C++ Min Priority Queue


C++ A* Search Code Function

C++ A* Headers & Prototypes

C++ A* Search Main()


Normalized Information Distance