Last Modified 3-20-2010

IUSB

Home

AI Topic Links

Problem Solving Agents

Uninformed Search Strategies

Breadth-First Search
Uniform-Cost Search
Depth-First Search
Depth First C++ Solution
Depth Limited Search
Iterative Depth Search
Bidirectional Search
Comparing Strategies

Informed Strategies
Greedy Best-First
Conditions For Optimality
A* Search
C++ A* Search Code


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


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.

Now that we have a data structure capable of containing all the necessary data for a Depth-First Search algorithm, as well as functions to build the Depth-First Search data structure. We still need to transfer the data from the map into the data structure. For this process, we will create a function called MakeMap(). MakeMap() will take advantage of the City AddNeighbor function, to add the neighboring city information to each of the corresponding cities:


void	MakeMap()
{
	City TempCity;

//Enter data for Arad

	TempCity.Name="Arad";
	TempCity.Neighbors.clear();

	TempCity.AddNeighbor("Zerind",75);
	TempCity.AddNeighbor("Sibiu", 140);
	TempCity.AddNeighbor("Timisoara",118);
	Cities.push_back(TempCity);

//Enter data for Bucharest

	TempCity.Name="Bucharest";
	TempCity.Neighbors.clear();
	TempCity.AddNeighbor("Giurgiu",90);
	TempCity.AddNeighbor("Urziceni",85);
	TempCity.AddNeighbor("Fagaras",211);
	TempCity.AddNeighbor("Pitesti",101);
	Cities.push_back(TempCity);
}

						

Figure DFS-5: Code to Manually Enter data using City Class data structure.


The data in this example will be entered in alphabetical order. Notice that it is not necessary to order the data for the algorithm to function. The explanation of the code is as follows:

  • City TempCity: Declare a temporary copy of the City class data structure to transfer data into the Cities vector.

  • TempCity.Name="Arad": Assign the name to City.

  • TempCity.Neighbors.clear(): Each time we enter data for a new city, we have to clear out the Neighbors vector so the data from the preceding cities does not accumulate.

  • TempCity.AddNeighbor("Zerind",75): Add the data describing the connection between Arad and Zerind.

  • Cities.push_back(TempCity): Save the data in the Cities vector so we can reuse TempCity to reenter data for the remaining data points.

Now that a couple of data points are entered. We should print out the map to make sure the data structure is functioning as planned. The following code will print the data structure to the screen. It can also be used to help conceptualize the methods used for extracting data from the Cities vector:


//Function to Display contents of Cities data structure to screen:

void	PrintCities()
{
	City		TempCity;
	Neighbor	TempNeighbor;

	vector<City>::iterator	CityNumber;

//Loop Through Entire Cities vector

	for(CityNumber=Cities.begin();CityNumber<Cities.end();CityNumber++)
	{
		TempCity=*CityNumber;
		cout<<"Current City: "<<TempCity.Name<<endl;
		cout<<"Neighbors: ";

//Loop Through Each Neighbor printing name and distance

		for(TempCity.NeighborNumber=TempCity.Neighbors.begin();
			TempCity.NeighborNumber<TempCity.Neighbors.end();
				TempCity.NeighborNumber++)
		{
			TempNeighbor=*TempCity.NeighborNumber;
			cout<<"  "<<TempNeighbor.Name;
			cout<<","<<TempNeighbor.Distance;
		}
		cout<<endl<<endl;
	}
}
						

Figure DFS-6: Code to print contents of Cities Data structure


Let's see how the data is being printed out:

  • void PrintCities ( ): A void function because we don't need to return anything.

  • City TempCity: Temporary Class construct of type City .

  • Neighbor TempNeighbor: Temporary Neighbor Structure.

  • vector <City> ::iterator CityNumber: An index to step through our Cities vector.

  • vector <Neighbor> ::iterator NeighborNumber: An index to step through our Neighbors sub vector.

  • for(CityNumber=Cities.begin( );
      CityNumber<Cities.end( );
        CityNumber++)
    • CityNumber=Cities.begin( ): Initialize the index to the first City in the Cities vector.
    • CityNumber<Cities.end( ): Test for the last City in Cities vector.
    • CityNumber++: Increment the index to the next City.

  • TempCity=*CityNumber: Transfer the indexed vector element into TempCity.

  • for(NeighborNumber=TempCity.Neighbors.begin( );
      NeighborNumber<TempCity.Neighbors.end( );
        NeighborNumber++)
    • NeighborNumber=TempCity.Neighbors.begin( ): Initialize the index to the first Neighbor of the city we are looking at.
    • NeighborNumber<TempCity.Neighbors.end( ): Test for last Neighbor in Neighbors vector.
    • NeighborNumber++: Increment index to next Neighbor.
  • TempNeighbor=*NeighborNumber: Transfer the indexed vector element into TempNeighbor.

  • cout<<" " <<TempNeighbor.Name;
    cout<<"," <<TempNeighbor.Distance;
    cout<<"," <<TempNeighbor.ShortestDistance;
    Print out the Neighbor Name, Distance and Straight Line Distance

Putting it all together

We now have the minimum components to test and run our code. The complete listing is below:

#include <stdio.h>
#include <string>
#include <iostream>
#include <vector>
#include <deque>

using namespace std;

//Declare Data Structures

//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;
	vector<Neighbor>		Neighbors;
	vector<Neighbor>::iterator	NeighborNumber;

	City();
	City(string);
	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;


void	MakeMap();

//Function to Display contents of Cities data structure to screen:

void	PrintCities();
void	PrintCities()
{
	City		TempCity;
	Neighbor	TempNeighbor;

	vector<City>::iterator	CityNumber;

//Loop Through Entire Cities vector

	for(CityNumber=Cities.begin();CityNumber<Cities.end();CityNumber++)
	{
		TempCity=*CityNumber;
		cout<<"Current City: "<<TempCity.Name<<endl;
		cout<<"Neighbors: ";

//Loop Through Each Neighbor printing name and distance

		for(TempCity.NeighborNumber=TempCity.Neighbors.begin();
			TempCity.NeighborNumber<TempCity.Neighbors.end();
				TempCity.NeighborNumber++)
		{
			TempNeighbor=*TempCity.NeighborNumber;
			cout<<"  "<<TempNeighbor.Name;
			cout<<","<<TempNeighbor.Distance;
		}
		cout<<endl<<endl;
	}
}

//Program starts here:

int	main()
{
	MakeMap();
	PrintCities();
	return 0;
}

//Function used to enter data manually

void	MakeMap()
{
	City TempCity;

//Enter data for Arad

	TempCity.Name="Arad";
	TempCity.Neighbors.clear();

	TempCity.AddNeighbor("Zerind",75);
	TempCity.AddNeighbor("Sibiu", 140);
	TempCity.AddNeighbor("Timisoara",118);
	Cities.push_back(TempCity);

//Enter data for Bucharest

	TempCity.Name="Bucharest";
	TempCity.Neighbors.clear();
	TempCity.AddNeighbor("Giurgiu",90);
	TempCity.AddNeighbor("Urziceni",85);
	TempCity.AddNeighbor("Fagaras",211);
	TempCity.AddNeighbor("Pitesti",101);
	Cities.push_back(TempCity);
}
						

Figure DFS-7: Listing to enter and print data points.


The listing above is "cut and pasteable". Running the code through the linux g++ compiler gives the following output in the putty shell:

Depth First 1

Figure DFS-8: Depth-First Search Output


The remaining nodes and connections will need to be entered. After which we begin the construct for the Depth-First Search algorithm. A useful subroutine will be to search the database for the City class with the same name as the Neighbors that we are parsing through. Viewing our current position as the Parent, each Neighbor will be considered a Child. The function will be called GetChildCity and will return a City class by reference. An empty search will return a false, indicating, at least for this application, that we have an error in entering our database information.


//Function to return Success or Failure on finding the Child Node given the
//Parent is a structure of type Neighbor. The ChildCity is returned by reference.

bool	GetChildCity(Neighbor Parent, City* ChildCity)
{
	City			TempCity;
	vector<City>::iterator	CityNumber;
		
	for(CityNumber=Cities.begin();CityNumber<Cities.end();CityNumber++)
	{
		TempCity=*CityNumber;
		
		if(TempCity.Name==Parent.Name)
		{
			*ChildCity=TempCity;
			return true;
		}
	}
	return false;
}
						

Figure DFS-9: Code Listing for GetChild


The following is a description of the functioning of the code:

  • bool GetChildCity(Neighbor Parent, City* ChildCity): Function declaration returning true or false.

    • Neighbor Parent: Neighbor containing the name of City class needed for analysis.

    • City* ChildCity: Pointer to City class data structure match returned with true.

  • City TempCity: Temporary City class data structure used to transfer data out of Cities vector.

  • vector<City>::iterator CityNumber: Index pointer to move through Cities vector.

  • for(CityNumber=Cities.begin();CityNumber<Cities.end();CityNumber++):

    • Loop through all the elements in the Cities vector.

  • TempCity=*CityNumber: Transfer data from Cities vector into temporary City data structure.

  • if(TempCity.Name==Parent.Name): Comparison for match.

  • *ChildCity=TempCity: Transfer data from Temporary container to passed pointer.

  • return true: Indicate successful match found and data in passed pointer is valid.

  • return false: Indicate match was not found - error in database.

It will be necessary to keep track of the paths taken during progession of the algorithm. The following class data structure will record the progression made during the search process:


class	PathRecord
{
public:
	string	AccumulatedPath;
	string	LastEntry;
	int	AccumulatedDistance;

	PathRecord(string);
	void	AddPath(PathRecord, City, Neighbor);
};

PathRecord::PathRecord(string Start)
{
	AccumulatedPath=Start;
	LastEntry=Start;
	AccumulatedDistance=0;
}

void	PathRecord::AddPath(PathRecord ParentRecord, City ChildCity, Neighbor CurrentNeighbor)
{
	this->AccumulatedPath=ParentRecord.AccumulatedPath+" - "+ChildCity.Name;
	this->LastEntry=ChildCity.Name;
	this->AccumulatedDistance=ParentRecord.AccumulatedDistance+CurrentNeighbor.Distance;
}

vector<PathRecord>	PathsTraveled;

						

Figure DFS-10: Class Data Structure to Record Paths Taken


The purpose of the Path Record class, is that we will need to keep track of the cities that we have explored, and how we got there. Let's go through an explanation of the code:

  • class PathRecord: Declaration of PathRecord class.

  • string AccumulatedPath: This will be the history of all cities we have visited to get to the current destination.

  • string LastEntry: When the current city we are evaluating matches the last entry - it means we are continuing that path.

  • int AccumulatedDistance: The distance we have accumulated from the start to our current position.

  • PathRecord(string): Constructor to create and initialize the PathRecord construct.


  • void AddPath(PathRecord, City, Neighbor): Add the current city we are exploring to the appropriate path.

  • PathRecord::PathRecord(string Start): Constructor/Initializer for the PathRecord construct.

  • AccumulatedPath=Start: The path we have traveled starts with the name of the beginning location.

  • LastEntry=Start: The path we have traveled ends with the name of the beginning location as well.

  • AccumulatedDistance=0: We have not moved yet, so our total distance is initially 0.


  • void PathRecord::AddPath(PathRecord ParentRecord, City ChildCity, Neighbor CurrentNeighbor): Function to Add the current location to the path already traveled.
    • PathRecord ParentRecord: Record of Path already traveled to arrive at current location.
    • City ChildCity: Name of Current Location
    • Neighbor CurrentNeighbor: Construct containing distance between last location and current location.

  • this->AccumulatedPath=ParentRecord.AccumulatedPath+" - "+ChildCity.Name: Add Current location to path traveled.

  • this->LastEntry=ChildCity.Name: Change the Last Entry flag to the name of the current location.

  • this->AccumulatedDistance=ParentRecord.AccumulatedDistance+CurrentNeighbor.Distance: Add the distance between the last location traversed and the current location to the distance already traveled.

  • vector<PathRecord> PathsTraveled: Each entry in PathsTraveled is a Record of each of the individual paths that have been traversed.

It is now time to develop the code using the algorithm in Figure DFS-2. The following is the C++ code for peforming a C++ Depth-First Search algorithm:


//Perform Depth First Search giving Start Location and Ending Location

bool	DepthFirstSearch(string StartName, string EndName)
{	
	City		CurrentCity;
	City		StartCity;
	City		ChildCity;
	City		ExploredCity;
	City		FrontierCity;

	Neighbor	CurrentNeighbor;

	bool	StartCityFound=false;
	bool	GoalFound=false;
	bool	AlreadyExplored;
	bool	AlreadyInFrontier;
	bool	NewChildFound;
	bool	PathFound;

	vector<City>::iterator	CityNumber;

	deque<City>			Frontier;
	deque<City>			Explored;

	deque<City>::iterator	FrontierCityNumber;
	deque<City>::iterator	ExploredCityNumber;

	PathRecord				NewRecord(StartName);
	PathRecord				TemporaryRecord("");

	vector<PathRecord>::iterator	PathNumber;

	if(StartName==EndName) return true;

	if(StartName=="" || EndName == "") return false;

//*************************************************************************
//			Search For Start
//*************************************************************************

	for(CityNumber=Cities.begin();CityNumber<Cities.end();CityNumber++)
	{
		CurrentCity=*CityNumber;
		if(CurrentCity.Name==StartName)
		{
			StartCity=CurrentCity;
			StartCityFound=true;
		}
	}

	if(StartCityFound==false) return false;

	PathsTraveled.push_back(NewRecord);
	Frontier.push_back(StartCity);

//*************************************************************************
//			Search For Goal
//*************************************************************************

	cout<<"\nRecording Exploratory Process:\n"<<"Start Location: "<<
		StartName<<"\t Ending Location: "<<EndName<<endl;

//Get Next Location in the Frontier

	while(!Frontier.empty() && GoalFound==false)
	{
		CurrentCity=Frontier.back();
		cout<<"\nCurrent City: "<<CurrentCity.Name<<endl;
		NewChildFound=false;

//Look through the Neighbors until an explored City is found.

		while(CurrentCity.NeighborNumber<CurrentCity.Neighbors.end() && NewChildFound==false)
		{
			CurrentNeighbor=*CurrentCity.NeighborNumber;
			cout<<"Current Neighbor: "<<CurrentNeighbor.Name<<endl;
			if(GetChildCity(CurrentNeighbor, &ChildCity)==false) 
			{
				cout<<"Didn't find a child\n";
				return false;
			}
			if(ChildCity.Name==EndName) 
			{
				cout<<"Goal Found\n";
				GoalFound=true;
			}

//Check for Child Already Explored

			AlreadyExplored=false;
			ExploredCityNumber=Explored.begin();
			
			while(AlreadyExplored==false && ExploredCityNumber<Explored.end())
			{
				ExploredCity=*ExploredCityNumber;
				
				if(ExploredCity.Name==ChildCity.Name) AlreadyExplored=true;
				ExploredCityNumber++;
			}
			

//Check for Child Already in Frontier

			if(AlreadyExplored==false)
			{
				AlreadyInFrontier=false;
				FrontierCityNumber=Frontier.begin();
				
				while(AlreadyInFrontier==false && FrontierCityNumber<Frontier.end())
				{
					FrontierCity=*FrontierCityNumber;
					
					if(FrontierCity.Name==ChildCity.Name) AlreadyInFrontier=true;
					FrontierCityNumber++;
				}
				
			}

//Put the parent in the Frontier queue and Expand the Child Node
//Record the process in the Paths Traveled vector.

			if(AlreadyExplored==false && AlreadyInFrontier==false)
			{
				Frontier.push_back(ChildCity);
				NewChildFound=true;
				PathNumber=PathsTraveled.begin( );
				PathFound=false;
				while(PathFound==false && PathNumber<PathsTraveled.end( ))
				{
					TemporaryRecord=*PathNumber;
					if(TemporaryRecord.LastEntry==CurrentCity.Name)
					{
						NewRecord.AddPath(TemporaryRecord, 
							ChildCity, CurrentNeighbor);
						PathsTraveled.push_back(NewRecord);
						PathFound=true;
					}
					PathNumber++;
				}
			}
			
			CurrentCity.NeighborNumber++;
		}

//Display the Explored Queue on each pass

		if(NewChildFound==false) 
		{
			Explored.push_back(CurrentCity);
			Frontier.pop_back();
		}

		cout<<"Explored: ";
		
		for(ExploredCityNumber=Explored.begin();
			ExploredCityNumber<Explored.end();ExploredCityNumber++)
		{
			ExploredCity=*ExploredCityNumber;
			cout<<ExploredCity.Name<<" \t";
		}
		cout<<endl;

//Display the Frontier Queue on each pass

		cout<<"Frontier: ";
		for(FrontierCityNumber=Frontier.begin(); 
			FrontierCityNumber<Frontier.end();FrontierCityNumber++)
		{
			FrontierCity=*FrontierCityNumber;
			cout<<FrontierCity.Name<<" \t";
		}
		cout<<endl;
	}
	
	return GoalFound;
}


						

Figure DFS-11: Code Listing for Depth-First Search


The following listing describes the function of the Depth-First Search Code:

  • bool DepthFirstSearch(string StartName, string EndName): Declaration Statement

    • bool DepthFirstSearch: returns true (goal found) or false (failure to find goal.

    • string StartName: Text used to match start location.

    • string EndName: Goal Location.

  • City CurrentCity: Temporary City Variable used as container during parsing of Cities vector.

  • City StartCity: Temporary City Variable used to extract starting location from Cities vector.

  • City ChildCity: Temporary City Variable used to extract Child nodes from Cities vector.

  • City ExploredCity: Temporary City Variable used to compare nodes in Explored queue.

  • City FrontierCity: Temporary City Variable used to compare nodes in Frontier queue.

  • Neighbor CurrentNeighbor: Neighbor Container used to extract data from CurrrentCity.Neighbors vector.

  • bool StartCityFound=false: Flag used to indicate whether or not requested start position is in the available database.

  • bool GoalFound=false: Flag used to indicate whether or not the search was successful (function return value).

  • bool AlreadyExplored: Flag used to indicate whether the current Neighbor City under analysis has been explored.

  • bool AlreadyInFrontier: Flag used to indicate whether the current Neighbor City under analysis has been placed in the Frontier.

  • bool NewChildFound: Flag used to indicate if the path to Neighbor City from the current location exists.

  • bool PathFound: Flag used to indicate if the path from the current location to the current Neighbor City exists.

  • vector<City>::iterator CityNumber: Iterator to parse through Cities vector.

  • deque<City> Frontier: Stack to coordinate expanding not fully explored cities.

  • deque<City> Explored: Queue to keep record of explored cities.

  • deque<City>::iterator FrontierCityNumber: Iterator to parse through Frontier Queue.

  • deque<City>::iterator ExploredCityNumber: Iterator to parse through Explored Queue.

  • PathRecord NewRecord(StartName): Record of path being created. Used to transfer data to Paths Traveled vector.

  • PathRecord TemporaryRecord(""): Container used to extract data from Paths traveled vector.

  • vector<PathRecord>::iterator PathNumber: Iterator to parse through Paths traveled vector.

  • if(StartName==EndName) return true: If the destination and location are the same, job is finished and successful.

  • if(StartName == "" || EndName == "") return false: If the start or destination is non-existent, a search cannot be made and the attempt is a failure.

  • for(CityNumber=Cities.begin();CityNumber<Cities.end();CityNumber++): For loop to parse through all elements in the City Structure

  • CurrentCity=*CityNumber: Extract element from Cities vector and place in CurrentCity.

  • if(CurrentCity.Name==StartName): Perform comparison between the initial location and the name in the Cities vector.

  • StartCity=CurrentCity: Create City structure with name of start location.

  • StartCityFound=true: Set flag indicating successful creation of start location.

  • if(StartCityFound==false) return false: Check to see if start location has been created, return failure if unsuccessful.

  • PathsTraveled.push_back(NewRecord): Initialize PathsTraveled vector with Start Location.

  • Frontier.push_back(StartCity): Initialize Frontier queue with Start Location.

  • while(!Frontier.empty( ) && GoalFound==false): Check until the Goal is found or all locations have been checked.

  • CurrentCity=Frontier.back( ): Place element in back of Frontier queue in the CurrentCity structure.

  • Frontier.pop_back( ): Remove the back element from the Frontier queue.

  • Explored.push_back(CurrentCity): Place CurrentCity structure in Explored queue

  • NewChildFound=false: Set flag indicating we have found the deepest node and need to move back up.

  • while(CurrentCity.NeighborNumber<CurrentCity.Neighbors.end() && NewChildFound==false)
    • while while loop proceeding until all children have been explored.

  • CurrentNeighbor=*CurrentCity.NeighborNumber: Create CurrentNeighbor with data from Neighbors vector.

  • if(GetChildCity(CurrentNeighbor, &ChildCity)==false): ChildCity becomes the City with the same name as the Neighbor under analysis - exit if no match found - Database Error.

  • AlreadyExplored=false: Preset Explored flag to failure.

  • ExploredCityNumber=Explored.begin(): Initialize ExploredCityNumber to first element in Explored queue.

  • while(AlreadyExplored==false && ExploredCityNumber<Explored.end()): Loop through all elements in Explored queue until a match is found.

  • ExploredCity=*ExploredCityNumber: Extract data from Explored queue and place in ExploredCity.

  • if(ExploredCity.Name==ChildCity.Name) AlreadyExplored=true: Check to see if ChildCity has already been explored. Set AlreadyExplored flag if it has.

  • ExploredCityNumber++: Move the index to the next location in Explored queue.

  • if(AlreadyExplored==false): Test to see if ChildCity was NOT in the Explored queue.

  • AlreadyInFrontier=false: Preset Frontier flag to failure.

  • FrontierCityNumber=Frontier.begin(): Initialize FrontierCityNumber to first element in Frontier queue.

  • while(AlreadyInFrontier==false && FrontierCityNumber<Frontier.end()): Loop through all elements in Frontier queue until a match is found.

  • FrontierCity=*FrontierCityNumber: Extract data from Frontier queue and place in FrontierCity.

  • if(FrontierCity.Name==ChildCity.Name) AlreadyInFrontier=true: Check to see if ChildCity has already been placed in the Frontier. Set the AlreadyInFrontier flag if it has.

  • FrontierCityNumber++: Move the index to the next location in the Frontier queue.

  • if(AlreadyExplored==false && AlreadyInFrontier==false): Test for Child NOT Explored and NOT in Frontier.

  • Frontier.push_back(ChildCity): Save Child in Frontier.

  • NewChildFound=true: Set flag that more nodes are to be expanded.

  • PathNumber=PathsTraveled.begin( ): Set Path Record iterator to beginning of array.

  • PathFound=false: Preset PathFound flag to Failure.

  • while(PathFound==false && PathNumber<PathsTraveled.end()): Loop Through all Paths in PathsTraveled vector until a match is found.

  • TemporaryRecord=*PathNumber: Extract Path from PathsTraveled vector and place in TemporaryRecord.

  • if(TemporaryRecord.LastEntry == CurrentCity.Name): Check to see if CurrentCity is the Last Entry in the Path.

  • NewRecord.AddPath(TemporaryRecord, ChildCity, CurrentNeighbor): Call AddPath Member function to append Current Child to PathsTraveled.

  • PathsTraveled.push_back(NewRecord): Save path as new element in PathsTraveled.

  • PathFound=true: Set flag to break out of loop.

  • PathNumber++: Index to next element in PathsTraveled vector.

  • CurrentCity.NeighborNumber++: Index to next neighbor in current node.

  • return GoalFound: Return success or failure.

Of course, no self-respecting program wouldn't tell about the great work, it has just accomplished. For this reason, a little routine needs to display the path taken to arrive at our intended location:


//Goal Path will print the path used to locate the Goal
//Supply the name of the goal after a search has been successful

void	PrintGoalPath(string GoalName)
{
	vector<PathRecord>::iterator	PathNumber;
	PathRecord			TemporaryRecord("");

	cout<<"\nGoal Path:  "<<endl;

	for(PathNumber=PathsTraveled.begin();PathNumber<PathsTraveled.end();PathNumber++)
	{
		TemporaryRecord=*PathNumber;
		if(TemporaryRecord.LastEntry==GoalName)
			cout<<TemporaryRecord.AccumulatedPath
				<<"  "<<TemporaryRecord.AccumulatedDistance<<endl;
	}
	cout<<endl;
}
						

Figure DFS-12: Code to print goal path.


A description of the code is given below:

  • void PrintGoalPath(string GoalName): Prints any path that ended with the same name as supplied as a parameter.

  • vector<PathRecord>::iterator PathNumber: Create an iterator to step through all paths recorded in the search.

  • PathRecord TemporaryRecord(""): Create a container to extract data from PathRecord vector.

  • for(PathNumber=PathsTraveled.begin( );PathNumber<PathsTraveled.end( );PathNumber++): Step through all recorded paths.

  • TemporaryRecord=*PathNumber: Transfer data out of PathRecord vector.

  • if(TemporaryRecord.LastEntry==GoalName): Print the path if the end point matches the parameter supplied.

Now that all of the necessary functions have been created. We can take this puppy for a test spin, and see what kind of results come out. Don't forget to complete the data table, and declare the functions, somewhere before they are used. We will need to make a couple of minor modifications to main, so it calls out the Depth-First Search and prints the results. Listed below is the change to the main( ) function:


//Program Starts here:

int	main()
{
	bool	GoalFound;

	MakeMap();
	string	StartLocation="Arad";
	string GoalState="Bucharest";
	GoalFound=DepthFirstSearch(StartLocation, GoalState);
	if(GoalFound) PrintGoalPath(GoalState);
		else 	cout<<"Couldn't Do It - "<<GoalState<<" is nowhere to be found!!\n";
	return 0;
}


						

Figure DFS-13: C++ main( ) function for Depth-First Search map program

Cutting and pasting all of the above code examples, and placing them in a file called r5.cpp, adding in the necessary function declaration statements like: bool DepthFirstSearch(string, string); then compiling the file with the GNU C++ linux compiler gives us the following output:

Depth First 2

Figure DFS-14: Output listing of C++ Depth-First Search


Well, according to this result, we were better off with the Breadth-First Search. I would suppose that sometimes the Depth-First search might outperform the Breadth-First Search, depending on how we stack the dataset. The time-complexity of the Breadth-First search is bounded by the size of the state space (which may be infinite). A depth-first tree search, on the other hand, may generate all of the O(bm) nodes in the search tree, where m is the maximum depth of any node; this can be much greater than the size of the state space. Note that m itself can be much larger than d (the depth of the shallowest solution) and is infinite if the tree is unbounded.

So far, depth-first search seems to have no clear advantage over breadth-first search, so why even consider it? The reason is space complexity. For a graph search, there is no advantage whatsoever, but, a depth-first tree search needs to store only a single path from the root to a leaf node, along with the remaining unexpanded sibling nodes for each node on the path. Once a node has been expanded, it can be removed from memory as soon as all of it's descendants have been fully explored as shown in figure DFS-1. For a state space with branching factor b and maximum depth m, depth-first search requires only O(bm) nodes. Using the same assumptions as for Figure BFS-19 and assuming that nodes at the same depth as the goal node have no successors, we find that depth-first search would require 156 kilobytes instead of 10 exabytes at depth d=16, a factor of 7 trillion times less space. This has led to the adoption of depth-first tree search as the basic work-horse of many areas of AI, including constraint satisfaction, propositional satisfiability, and logic programming. We will now focus on the tree-search version of depth-first search.

A variant of depth-first search called backtracking search uses still less memory. In backtracking, only one successor is generated at at time rather than all successors; each partially expanded node remembers which successor to generate next. In this way, only O(m) is needed rather than O(bm). Backtracking search facilitates yet another memory and time saving trick: the idea of generating a successor by modifying the current state description rather than copying it first. This reduces the memory requirements to just one state description and O(m) actions. For this to work, we must be able to undo each modification when we go back to generate the next successor. For problems with large state descriptions, such as robotic assembly, these techniques are critical to success.

Depth Limited Search

The embarrasing failure of depth-first search in infinite state spaces can be alleviated by supplying depth-first search with a predetermined depth-limit of l. That is, nodes at depth l are treated as if they have no successors. This approach is called Depth Limited Search. The depth limit solves the infinite-path problem. Unfortunately, it also introduces an additional source of incompleteness if we choose l<d, that is, the shallowest goal is beyond the depth limit (which is likely when d is unknown). Depth Limited Search will also be non-optimal if we choose l>d. Its time complexity is O(bl) and its space complexity is O(bl). Depth-first search can be viewed as a special case of depth-limited search with l=∞.

Sometimes, depth limits can be based on knowledge of the problem. For example, on the map of Romania there are 20 cities. Therefore, we know that if there is a solution, it must be of length 19 at the longest, so l=19 is a possible choice. But, in fact, if we studied the map carefully, we would discover that any city can be reached from any other city in at most 9 steps. This number, known as the diameter of the state space, gives us a better depth limit, which leads to a more efficient depth-limited search. For most problems, however, we will not know a good depth limit until we have solved the problem.

Depth-limited search can be implemented as a simple modification to the general tree-graph or graph-search algorithm. Alternatively, it can be implemented as a simple recursive algorithm. Notice that depth-limited search has two modes of failure:

  1. standard failure - no solution.
  2. cutoff failure - no solution within the depth limit.

Iterative Deepening Depth Search

Iterative Deepening Depth Search or iterative deepening depth-first search) is a general strategy, often used in combination with depth-first tree search, that finds the best depth limit. It does this by gradually increasing the limit - first 0, then 1, then 2, and so on - until a goal is found. This will occure when the depth reaches d, the depth of the shallowest goal node. The algorithm is shown in Figure DFS-15:

function Iterative-Deepening-Search(problem) returns a solution, or failure
  for depth=0 todo
    resultDepth-Limited-Search(problem, depth)
    if resultthen return result

Figure DFS-15: Iterative Deepening Search Algorithm


Iterative deepening combines the benefits of depth-first search and breadth-first search. Like depth-first search, its memory requirements are modest: O(bd) to be precise. Like breadth-first search, it is complete when the branching factor is finite and optimal when the path-cost is a non-decreasing function of the depth of the node.

Iterative deepening search may seem wasteful because states are generated multiple times. It turns out this is not too costly. The reason is that in a tree search tree with the same (or nearly the same) branching factor at each level, most of the nodes are in the bottom level, so it does not matter much that the upper levels are generated multiple times. In an iterative deepening search, tehe nodes on the bottom level (depth d) are generated once, those on the next-to-bottom level are generated twice, and so on, up to the children of the root, which are generated d times. So the total number of nodes generated in the worst case is:

N(IterativeDeepeningSearch)=(d)b + (d-1)b2 + ... + (1)b2

This gives a time complexity of O(bd) - asymptotically the same as breadth-first search. There is some extra cost for generating the upper levels multiple times, but it is not large. For example, if b=10 and d=5, the numbers are:

N(IterativeDeepeningSearch)=50+400+3,000+20,000+100,000=123,450

N ( Breadth First Search ) = 10+100+1,000+10,000+100,000=111,110

If you are really concerned about repeating the repetition, you can use a hybrid approach that runs breadth-first search until almost all of the available memory is consumed, and then runs iterative deepening from all nodes in the frontier. In general, iterative deepening is the preferred uninformed search method when the search space is large and the depth of the solution is not known.

Iterative deepening is analogous to breadth-first search in that it explores a complete layer of new nodes at each iteration before going on to the next layer. It would seem worthwhile to develop an iterative analog to uniform-cost search, inheriting the latter algorithm's optimality guarantees while avoiding its memory requirements. The idea is to use increasing path-cost limits instead of increasing depth-limits. The resulting algorithm, called iterative lengthening search. Unfortunately, it turns out that iterative lengthening incurs substantial overhead compared to uniform-cost search.

Bidirectional Search

The idea behind bidirectional search is to run two simultaneous searches - one forward from the initial state and the other backward from the goal - hoping the two searches meet in the middle. The motivation is that bd/2 + bd/2 is much less than bd.

Bidirectional search is implemented by replacing the goal test with a check to see whether the frontiers of the two frontiers intersect; if they do, a solution has been found. It is important to realize that the first such solution found may not be optimal, even if the two searches are both breadth-first; some additional search is required to make sure there isn't another short-cut across the gap. The check can be done when each node is generated or selected for expansion and, with a hash table, will take constant time. For example, if a problem has solution depth d = 6, and each direction runs breadth-first search one node at a time, then in the worst case the two searches meet when they have generated all the nodes at depth = 3. For b = 10, this means a total of 2,220 node generations compared with 1,111,110 for a standard breadth-first search. Thus, the time complexity of bidirectional search using breadth-first searches in both directions is O(bd/2). The space complexity is also O(bd/2). We can reduce this by roughly one half if one of the two searches is done by iterative deepening, but at least one of the frontiers must be kept in memory so that the intersection check can be done. The space requirement is the most significant weakness of the bidirectional search.

The reduction in time complexity makes bidirectional search attractive, but how do we search backward? This is not as easy as it sounds. Let the predecessors of a state x be all those states that have x as a successor. Bidirectional search requires a method for computing predecessors. When all the actions in the state are reversible, the predecessors of x are just its successors. Other cases may require substantial ingenuity.

Consider the question of what we mean by "the goal" in searching "backward from the goal." For the 8-puzzle and for finding a route in Romania, there is just one goal state, so the backward search is very much like the forward search. If there are several explicitly goal states - for example, the two dirt-free states in Figure Agent-3 - then we can construct a new dummy state whose immediate predecessors are all the actual goal states. But if the goal is an abstract description, such as the goal that "no queen attacks another queen" in the n-queens problem, then bidirectional search is difficult to use.

Comparing Uninformed Search Strategies

Criterion Breadth-First Uniform Cost Depth-First Depth-Limited Iterative Deepening Bidirectional
Complete Yes Yes No No Yes Yes
Time O(bd) O(b1+[C/ε]) O(bm) O(bl) O(bd) O(bd/2)
Space O(bd) O(b1+[C/ε]) O(bm) O(bl) O(bd>) O(bd/2)
Optimal? Yes Yes No No Yes Yes

Figure DFS-16: Evaluation of Tree-Search Strategies


Informed Search Strategies

This section shows how an informed search strategy - one that uses problem-specific knowledge beyond the definition of the problem itself - can find solutions more efficiently than can an uninformed search strategy.

The general approach we consider is called best first search. Best-first search is an instance of the general Tree-Search or Graph-Search algorithm in which a node is selected for expansion based on an evaluation function, f(n). The evaluation function is construed as a cost-estimate, so the node with the lowest evaluation is expanded first. The implementation of best first graph search is identical to that for Uniform-Cost Search, except for the use of f instead of g to order the priority queue.

The choice of f determines the search strategy. Most best-fit algorithms include as a component of f a heuristic function denoted h(n):

h(n) = estimated cost of the cheapest path from the state at node n to a goal state.

Notice that h(n) takes a node as an input, but, unlike g(n) it depends only on the state at that node. For example, one might estimate the cost of the cheapest path from Arad to Bucharest via the straight-line distance from Arad to Bucharest.

Heuristic functions are the most common form in which additional knowledge of the problem is imparted to the search algorithm. We also consider them to be arbitrary, nonnegative, problem specific functions, with one constraint: if n is a goal node, then h(n)=0. Following are two ways to use heuristic information to guide search.

Greedy Best-First Search

Greedy best-first search tries to expand the node that is closest to the goal, on the grounds that it is likely to lead to a solution quickly. Thus, it evaluates nodes by using just the heuristic function; that is, f(n)=h(n).

Let us see how this works for the route-finding problems in Romania; we use the straight-line distance heuristic, which we will call hSLD. If the goal is Bucharest, we need to know the straight-line distances to Bucharest, which are shown in Figure ISS-1:

City Distance City Distance City Distance City Distance
Arad 366 Bucharest 0 Craiova 160 Drobeta 242
Eforie 161 Fagaras 176 Giurgiu 77 Hirsova 151
Iasi 226 Lugoj 244 Mehadia 241 Neamt 234
Oradea 380 Pitesti 100 Rimnicu Vilcea 193 Sibiu 253
Timisoara 329 Urziceni 80 Valusi 199 Zerind 374

Figure ISS-1: Values of hSLD - straight line distances to Bucharest


Notice that the values of hSLD cannot be computed from the problem description itself. Moreover, it takes a certain amount of experience to know that hSLD is correlated with actual road distances and is, therefore, a useful heuristic.

Figure ISS-2 shows the progress of a greedy best-first search using hSLD to find a path from Arad to Bucharest:

Greedy Expansion

Figure ISS-2: Stages in Greedy Best-First Search for Bucharest.


The first node to be expanded from Arad will be Sibiu because it is closer to Bucharest then either Zerind or Timisoara. The next node to be expanded will be Fagaras because it is closest. Fagaras, in turn, generates Bucharest, which is the goal. For this particular problem, greedy best-first search using hSLD finds a solution without ever expanding a node that is not on the solution path; hence, its search cost is minimal. It is not optimal, however: the path via Sibiu and Fagaras to Bucharest is 32 kilometers longer than the path through Rimnicu Vilcea and Pitesti. This shows why the algorithm is called "Greedy" - at each step it tries to get as close to the goal as it can.

Romania map

Figure ISS-3: Data Source for C++ A* Search Code Example


Greedy best-first tree search is also incomplete even in a finite state space, much like depth-first search. Consider the problem of getting from Iasi to Fagaras. The heuristic suggests that Neamt will be expanded first because it is closest to Fagaras, but it is a dead end street. The solution is to go first to Valusi - a step that is actually farther from the goal according to the heuristic - and then continue to Urziceni, Bucharest, and Fagaras. The algorithm will never find this solution, however, because expanding neamt puts Iasi back into the frontier, Iasi is closer to Fagaras than Valusi is, and so Iasi will be expanded again, leading to an infinite loop. (The graph search version is complete in finite spaces, but not in infinite ones.) The worst case time and space complexity for the tree version is O(bm), where m is the maximum depth fo the search space. With a good heuristic function, however, the complexity can be reduced substantially. The amount of reduction depends on the particular problem and on the quality of the heuristic.

A* Search: Minimizing the total estimated solution cost

The most widely known form of best-first search is called A* search (pronounced "A-star search"). It evaluates nodes by combining g(n), the cost to reach the node, and h(n), the cost to get from the node to the goal:

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

Since g(n) gives the path cost from the start node to node n, the goal node, and h(n) is the estimated cost of the cheapest path from n to the goal, we have:

f(n) = estimated cost of the cheapest solution through n.

Thus, if we are trying to find the cheapest solution, a reasonable thing to try first is the node with the lowest value of g(n)+h(n). As it turns out, this strategy is more than just reasonable: provide that the heuristic function, h(n), satisfies certain conditions, A* search is both complete and optimal. The algorithm is identical to Uniform-Cost Search except that A* uses g+h instead of g.

Conditions for optimality: Admissability and Consistency

The first condition that we require for optimality is that h(n) be an admissable heuristic. An admissable heuristic is one that never overestimates the cost to reach the goal. Because g(n) is the actual cost to reach n along the current path, and f(n)=g(n)+h(n), we have as an immediate consequence that f(n) never overestimates the true cost of a solution along the current path through n.

Admissible heuristics are by nature optimistic because they think the cost of solving the problem is less than it actuall is. An obvious example of an admissable heuristic is the straight line distance, hSLD that we used in getting to Bucharest. Straight-line distance is admissable because the shortest path between any two points is a straight line, so the straight line cannot be an overestimate. Figure ISS-4 shows the progress of an A* tree search for Bucharest:

A* Expansion

Figure ISS-4: A* Search Expansion


The cost values for each node are given in parentheses below each node. The cost is determined by following the path from the start as it progresses through each expansion. Notice in particular, that in level 4 Bucharest, by way of Fagaras, has a lowest possible of cost of 450, but, at the same time, the node at Pitesti is only 417. A* is not ready to settle just yet, so 1 more expansion takes place uncovering the best possible cost with the Bucharest goal only costing 417. Thus the path from A* is Arad-Sibiu-Rimnicu Vilcea-Pitesti-Bucharest.

A second, slightly stronger condition called consistency, or sometimes monotonicity, is required only for applications of A* to graph search. A heuristic h(n) is consistent if, for every node n and every successor n' of n generated by any action a, the estimated cost of reaching the goal from n is no greater than the step cost of getting to n':

h(n) ≤ c(n,a,n') +h (n).

This is a form of the general triangle inequality, which stipulates that each side of a triangle cannot be longer than the sum of the other two sides. Here, the triangle is formed by n,n', and the goal Gn closest to n. For an admissable heuristic, the inequality makes perfect sense: if there were a route form n to Gn via n' that was cheaper than h(n), that would violate the property that h(n) is a lower bound on the cost to reach Gn.

It is fairly easy to show that every consistent heuristic is also admissable. Consistency is therefore a stricter requirement than admissability, but one has to work quite hard to concoct heuristics that are admissable but not consistent. All the admissable heuristics we discuss in this chapter are also consistent. Consider, for example, hSLD. We know that the general triangle inequality is satisified when each side is measured by the straight-line distance and that the straight-line distance between n and n' is no greater than c(n,a,n'). Hence, hSLD is a consistent heuristic.

Optimality of A*

As we mentioned eariler, A* has the following properties: the tree-search version of A* is optimal if h(n) is admissable, while the graph-search version is optimal if h(n) is consistent.

The first step is to establish the following: if h(n) is consistent, then the values of f(n) along any path are nondecreasing. The proof follows directly from the definition of consistency:

Suppose n' is a successor of n; then g(n') = g(n) + c(n,a,n') for some action a and we have:

f(n) = g(n') + h(n') = g(n) + c(n,a,n') + h(n') ≥ g(n) + h(n) = f(n).

The next step is to prove that whenever A* selects a node n for expansion, the optimal path to that node has been found. Were this not the case, there would have to be another frontier node n', and by the graph separation property as illustrated in the following diagram:

Graph Separation Property

Figure ISS-5: Expanded Node Graph Separation Property


where the frontier (white nodes) always separate the explored region (black nodes) from the unexplored region (gray nodes). Because f is nondecreasing along any path, n' would have lower f-cost than n and would have been selected first.

From the two preceding observations, it follows that the sequence of nodes expanded by A* using Graph-Search is in nondecreasing order of f(n). Hence, the first goal node selected for expansion must be an optimal solution because f is the true cost for goal nodes (which have h = 0) and all later goals will be at least as expensive.

The fact that f-costs are nondecreasing along any path also means that we can draw contours in the state space, just like the contours in a topographic map:

Romania Contours
Figure ISS-6: Map of Romania showing contours at f = 380, f=400, f=420, with Arad as the start state. Nodes inside a given contour have f-costs less than or equal to the contour value.

Inside the contour labeled 400, all nodes have f(n) less than or equal to 400, and so on. Then because A* expands the frontier of lowest f-cost, we can see than an A* search fans out from the start node, adding nodes in concentric bands of increasing f-cost.

With uniform-cost search (A* search using h(n) = 0), the bands will be circular around the start state. With more accurate heuristics, teh bands will stretch toward the goal state and become more narrowly focused around the optimal path. If C* is the cost of the optimal solution path, then we can say the following:

  • A* expands all nodes with f(n) < C*.
  • A* might then expand some of the nodes right on the "goal contour" (where f(n) = C*) before selecting the goal node.

Completeness requires that there be only finitely many nodes with cost less than or equal to C*, a condition that is true if all step costs exceed some finite ε and if b is finite.

Notice that A* expands no nodes with f(n) > C* - for example, Timisoara is not expanded in Figure ISS-4, even though it is a child of the root. We say that the subtree below Timisoara is pruned; because hSLD is admissable, the algorithm can safely ignore this subtree while still guaranteeing optimality. The concept of pruning - eliminating possibilities from consideration without having to examine them - is important for many areas of AI.

One final observation is that among optimal algorithms of this type - algorithms that extend search paths from the root and use the same heuristic information - A* is optimally efficient for any given consistent heuristic. That is, no other optimal algorithm is guaranteed to expand fewer nodes than A* (except possibly through tie-breaking among nodes with f(n) = C*). This is because any algorithm that does not expand all nodes with f(n) < C* runs the risk of missing the optimal solution.

That A* search is complete, optimal, and optimally efficient among all such algorithms is rather satisfying. Unfortunately, it does not mean that A* is the answer to all our searching needs. The catch is that, for most problems, the number of states within the goal contour search space is still exponential in the length of the solution. The basic results of the analysis are as follows: For problems with constant step costs, the growth in run time as a function of the optimal solution depth d is analyzed in terms of absolute error or the relative error of the heuristic. The absolute error is defined as Δ ≡ h* - h, where h* is the actual cost of getting from the root to the goal, and the relative error is defined as ε ≡ (h* - h) / h*.

The complexity results depend very strongly on the assumptions made about the state space. The simplest model studied is a state space that has a single goal and is essentially a tree with reversible actions. In this case, the time complexity of A* is exponential in the maximum absolute error, that is, O(bΔ). For constant step costs, we can write this as O(bεd), where d is the solution depth. For almost all heuristics in practical use, the absolute error is at least proportional to the path cost h*, so ε is constant or growing and the time complexity is exponential in d. We can also see the effect of a more accurate heuristic: O(bεd) = O((bε)d), so the effective branching factor is bε.

When the state space has many goal states - particularly near-optimal goal states - the search process can be led astray from the optimal path and there is an extra cost proportional to the number of goals whose cost is within a factor ε of the optimal cost. Finally, in the general case of a graph, the situation is even worse. There can be exponentially many states with f(n) < C* even if the absolute error is bounded by a constant. For example, consider a version of the vacuum world where the agent can clean up any square for unit cost without even having to visit it: in that case, squares can be cleaned in any order. With N initially dirty squares, there are 2N states where some subset has been cleaned and all of them are on an optimal solution path - and hence satisfy f(n) < C* - even if the heuristic has an error of 1.

The complexity of A* often makes it impractical to insist on finding an optimal solution. One can use variants of A* that find suboptimal solutions quickly, or once can sometimes design heuristics that are more accurate but not strictly admissable. In any case, the use of a good heuristic still provides enormous savings compared to the use of an uninformed search.

Computation time is not, however, A*'s main drawback. Because it keeps all generated nodes in memory (as do all Graph-Search algorithms), A* usually runs out of space long before it runs out of time. For this reason, A* is not practicla for many large scale-problems. There are, however, algorithms that overcome the space problem withou sacrifiing optimality or completeness, but with a small cost in execution time.

C++ Code for A* Search

We now turn our attention to coding the A* algorithm in C++. We are going to up the ante a little bit, and merge the PathRecord with the City class from the previous examples. First, let's write the pseudocode, then get some actual working code: We are going to assume that Frontier is a priority queue, but the C++ STL does not give us the option of 'queueing' based on the value of a single class element, so we'll write a 10 line function or so, to set the priorities accordingly.

StartCity → Frontier.push()
LOOP
	CurrentCity=Frontier.pop()
	Expand CurrentCity
	CurrentCity.Children → Frontier.push()
	IF Child==Goal THEN 
		FALSE → GoalNotFound
WHILE(Frontier.peek()<GoalDistance OR GoalNotFound)
						

Figure ISS-7: Pseudocode for A* Search


The first item on the agenda is creating the City class element. The following code will define the class, methods, and data:

// Structure containing minimum Child Expansion Information

struct	Neighbor
{
	string	Name;
	int	Distance;
};

//Node containing necessary information for A* search

class	City
{
public:

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

	string				Name;
	string				AccumulatedPath;
	int				AccumulatedDistance;
	int				StraightLineDistance;

	City();
	City(string, int);

	void	AddNeighbor	(string, int);
};

//Constructor for Non-Initialized City

City::City()
{
	Name="";
	NeighborNumber=Neighbors.begin();
	AccumulatedPath="";
	AccumulatedDistance=0;
	StraightLineDistance=0;
}


//Constructor for Initialized City

City::City(string name, int sld)
{
	Name=name;
	NeighborNumber=Neighbors.begin();
	AccumulatedPath=name;
	AccumulatedDistance=0;
	StraightLineDistance=sld;
}

//Add Neighbor Method - requires Name of Neighbor and distance to City

void	City::AddNeighbor(string name, int distance)
{
	Neighbor	TempNeighbor;

	TempNeighbor.Name		= name;
	TempNeighbor.Distance	= distance;
	Neighbors.push_back(TempNeighbor);
	NeighborNumber=Neighbors.begin();
}

vector<City>	Cities;
vector<City>	Frontier;

						

Figure ISS-8: A* City Class Declaration


For those of you wanting to understand how the search mimics the diagram in Figure ISS-4 we should go through a brief explanation of the class variable declaration in Figure ISS-8:

  • The Neighbor structure gives a reference to cities accessible from current location (Child nodes).

  • struct Neighbor: C++ structure declaration for possible destinations from current location.
  • string Name: The name of the possible destinations will be using a C++ string variable type.
  • int Distance: The distance units necessary to arrive at the destination from current location.

  • C++ Class Object containing necessary information and procedures to describe current location. (Parent Node).

  • class City: Declaration statement describing City object.
  • public: Unlimited access is Okay, since we are not intending on interfacing this code with other modules.
  • vector<Neighbor>::iterator Neighbor Number: C++ construct necessary to access vector data members.
  • vector<Neighbor> Neighbors: Vector (array) construct to contain information on possible destinations.
  • string Name: The name used to reference the current location.
  • string AccumulatedPath: History of paths taken to arrive at current location.
  • int AccumulatedDistance: Sum of path lengths used to arrive at current location.
  • int StraightLineDistance: Shortest possible distance from current location to goal.
  • City(): C++ prototype for creation of class object with no parameters.
  • City(string, int): C++ prototype for creation of class object with parameters:Name(string) and StraightLineDistance (int).
  • void AddNeighbor (string, int): C++ prototype to add possible destination location.

  • The following constructor gives details on how to construct a City when no parameters are given:

  • Manually set all variables to 0 or NULL since the compiler won't do it automatically.

  • City::City(): Tell the compiler we want to construct a City with no parameters given by user.
    • Name=""
    • NeighborNumber=Neighbors.begin()
    • AccumulatedPath=""
    • AccumulatedDistance=0
    • StraightLineDistance=0

  • The following constructor gives detail on how to construct a City with name and distance given:

  • Manually set the Name and Straight Line Distance - 0 everything else.

  • City::City(string name, int sld): Tell the compiler we want to construct a City with Name and StraightLineDistance given.
    • Name=name
    • NeighborNumber=Neighbors.begin()
    • AccumulatedPathName=name
    • AccumulatedDistance=0
    • StraightLineDistance=sld

  • The following constructor gives detail on how to add in a possible destination (Child Node).

  • void City::AddNeighbor(string name, int distance): Procedure Declaration for adding a possible destination (Neighbor).
    • Neighbor TempNeighbor: Create temporary container until we can save the data in the vector.
    • TempNeighbor.Name=name: Name the destination.
    • TempNeighbor.Distance=distance: Give the distance from the current location.
    • Neighbors.push_back(TempNeighbor): Save the information in the Neighbors vector.
    • NeighborNumber=Neighbors.begin(): Set the iterator to 0 just in case.

  • The following vectors are declared globally so that they easily accessed from anywhere in the program.

  • vector<City>Cities Global declaration of vector to represent Map of Romania
  • vector<City>Frontier Global declaration of vector to represent Priority Queue for Cities waiting for expansion.

The next part of the procedure is the part I find the most distasteful. Having a background in Real-Time control systems, I am used to extracting the information I need automatically from the environment. Once extracted, the data can be archived for later analysis. In a well designed system, data is almost never entered manually. So, what are we going to do now? Enter the data manually, of course. The following code will build a map from data manually extracted from Figure ISS-6. Once that is done, you could 'suck the data off this webpage' and place it in your own program, or you can be really lazy and just cut and paste it. The following is the code to build the map to act as our database:

//Function used to enter Romanian Map manually

void MakeMap()
{
	City	TempCity;
//Enter data for Arad

	TempCity.Name="Arad";
	TempCity.StraightLineDistance=366;
	TempCity.Neighbors.clear();

	TempCity.AddNeighbor("Zerind",75);
	TempCity.AddNeighbor("Sibiu", 140);
	TempCity.AddNeighbor("Timisoara",118);
	Cities.push_back(TempCity);

//Enter data for Bucharest

	TempCity.Name="Bucharest";
	TempCity.StraightLineDistance=0;
	TempCity.Neighbors.clear();
	TempCity.AddNeighbor("Giurgiu",90);
	TempCity.AddNeighbor("Urziceni",85);
	TempCity.AddNeighbor("Fagaras",211);
	TempCity.AddNeighbor("Pitesti",101);
	Cities.push_back(TempCity);


//Enter data for Craiova

	TempCity.Name="Craiova";
	TempCity.StraightLineDistance=160;
	TempCity.Neighbors.clear();
	TempCity.AddNeighbor("Pitesti",138);
	TempCity.AddNeighbor("Rimnicu Vilcea",97);
	TempCity.AddNeighbor("Drobeta",120);
	Cities.push_back(TempCity);

//Enter data for Drobeta

	TempCity.Name="Drobeta";
	TempCity.StraightLineDistance=242;
	TempCity.Neighbors.clear();
	TempCity.AddNeighbor("Craiova",120);
	TempCity.AddNeighbor("Mehadia",75);
	Cities.push_back(TempCity);

//Enter data for Eforie

	TempCity.Name="Eforie";
	TempCity.StraightLineDistance=161;
	TempCity.Neighbors.clear();
	TempCity.AddNeighbor("Hirsova",86);
	Cities.push_back(TempCity);

//Enter data for Fagaras
	
	TempCity.Name="Fagaras";
	TempCity.StraightLineDistance=176;
	TempCity.Neighbors.clear();
	TempCity.AddNeighbor("Bucharest",211);
	TempCity.AddNeighbor("Sibiu",99);
	Cities.push_back(TempCity);

//Enter data for Giurgiu

	TempCity.Name="Giurgiu";
	TempCity.StraightLineDistance=77;
	TempCity.Neighbors.clear();
	TempCity.AddNeighbor("Bucharest",90);
	Cities.push_back(TempCity);

//Enter data for Hirsova

	TempCity.Name="Hirsova";
	TempCity.StraightLineDistance=151;
	TempCity.Neighbors.clear();
	TempCity.AddNeighbor("Eforie",86);
	TempCity.AddNeighbor("Uriceni",98);
	Cities.push_back(TempCity);

//Enter data for Iasi

	TempCity.Name="Iasi";
	TempCity.StraightLineDistance=226;
	TempCity.Neighbors.clear();
	TempCity.AddNeighbor("Valsui",92);
	TempCity.AddNeighbor("Neamt",87);
	Cities.push_back(TempCity);

//Enter data for Lugoj

	TempCity.Name="Lugoj";
	TempCity.StraightLineDistance=244;
	TempCity.Neighbors.clear();
	TempCity.AddNeighbor("Mehadia",70);
	TempCity.AddNeighbor("Timisoara",111);
	Cities.push_back(TempCity);

//Enter data for Mehadia

	TempCity.Name="Mehadia";
	TempCity.StraightLineDistance=241;
	TempCity.Neighbors.clear();
	TempCity.AddNeighbor("Drobeta",75);
	TempCity.AddNeighbor("Lugoj",70);
	Cities.push_back(TempCity);

//Enter data for Neamt

	TempCity.Name="Neamt";
	TempCity.StraightLineDistance=234;
	TempCity.Neighbors.clear();
	TempCity.AddNeighbor("Iasi",87);
	Cities.push_back(TempCity);

//Enter data for Oradea

	TempCity.Name="Oradea";
	TempCity.StraightLineDistance=380;
	TempCity.Neighbors.clear();
	TempCity.AddNeighbor("Zerind",71);
	TempCity.AddNeighbor("Sibiu",151);
	Cities.push_back(TempCity);

//Enter data for Pitesti

	TempCity.Name="Pitesti";
	TempCity.StraightLineDistance=100;
	TempCity.Neighbors.clear();
	TempCity.AddNeighbor("Bucharest",101);	
	TempCity.AddNeighbor("Rimnicu Vilcea",97);
	TempCity.AddNeighbor("Craiova",138);
	Cities.push_back(TempCity);

//Enter data for Rimnicu Vilcea

	TempCity.Name="Rimnicu Vilcea";
	TempCity.StraightLineDistance=193;
	TempCity.Neighbors.clear();
	TempCity.AddNeighbor("Pitesti",97);
	TempCity.AddNeighbor("Sibiu",80);
	TempCity.AddNeighbor("Craiova",146);
	Cities.push_back(TempCity);

//Enter data for Sibiu

	TempCity.Name="Sibiu";
	TempCity.StraightLineDistance=253;
	TempCity.Neighbors.clear();

	TempCity.AddNeighbor("Rimnicu Vilcea",80);
	TempCity.AddNeighbor("Fagaras",99);
	TempCity.AddNeighbor("Oradea",151);
	TempCity.AddNeighbor("Arad",140);
	Cities.push_back(TempCity);

//Enter data for Timsoara

	TempCity.Name="Timisoara";
	TempCity.StraightLineDistance=329;
	TempCity.Neighbors.clear();
	TempCity.AddNeighbor("Lugoj",70);
	TempCity.AddNeighbor("Arad",118);
	Cities.push_back(TempCity);

//Enter data for Urziceni

	TempCity.Name="Urziceni";
	TempCity.StraightLineDistance=80;
	TempCity.Neighbors.clear();
	TempCity.AddNeighbor("Hirsova",98);
	TempCity.AddNeighbor("Bucharest",85);
	Cities.push_back(TempCity);

//Enter data for Valusi

	TempCity.Name="Valsui";
	TempCity.StraightLineDistance=199;
	TempCity.Neighbors.clear();
	TempCity.AddNeighbor("Iasi",92);
	TempCity.AddNeighbor("Urziceni",142);
	Cities.push_back(TempCity);

//Enter data for Zerind

	TempCity.Name="Zerind";
	TempCity.StraightLineDistance=374;
	TempCity.Neighbors.clear();
	TempCity.AddNeighbor("Oradea",71);
	TempCity.AddNeighbor("Arad",75);
	Cities.push_back(TempCity);
}
						

Figure ISS-9: C++ Code for Romania Map Database


The above code is pretty redundant after you get the first city in. So, we'll go through about 1 city, and move on to the real stuff right after that:

  • Function to enter Romanian Roadmap Data manually.

  • void MakeMap() This is void because it doesn't return any value, and you don't give it any parameters.
  • City TempCity: Temporary container to hold data until we stuff in the Cities vector.
  • TempCity.Name="Arad": Give your city a name.
  • TempCity.StraightLineDistance=366: Tell A* how far you're willing to travel to get to Bucharest.
  • TempCity.Neighbors.clear(): Since we are reusing 1 City object, the vector must be cleared, so the dust doesn't accumulate.
  • TempCity.AddNeighbor("Zerind", 75): A neighbor needs a name and the distance between itself and the City we are building.
  • Cities.push_back(TempCity): Save the data in the Cities vector.

The next function will search the Cities database to find a match with the neighbor name, and return a complete City. The city found will be placed in the ChildCity parameter sent by reference. A boolean true or false will be returned to indicate success or failure in the search for a match:

bool	GetChildCity (Neighbor Parent, City* ChildCity)
{
	vector<City>::iterator	CityNumber;

	for(CityNumber=Cities.begin();CityNumber<Cities.end();CityNumber++)
	{
		*ChildCity=*CityNumber;
		if(ChildCity.Name == Parent.Name) 
			return true;
	}
	return false;
}
						

Figure ISS-10: Code for function GetChildCity


Let's go through the code and see if it makes any sense:

  • Function to return ChildCity with same name as Neighbor.

  • bool GetChildCity(Neighbor Parent, City* ChildCity):
    • bool Returns true for match found - data valid or false no match found - data not valid
    • GetChildCity: Function Name
    • Neighbor Parent: Send one of the neighbors from the Neighbors vector.
    • City* ChildCity: City returned by reference.

  • vector<City>::iterator CityNumber: Index to step through the Cities vector.

  • for(CityNumber=Cities.begin();CityNumber<Cities.end();CityNumber++):
    • CityNumber=Cities.begin(): Pass the memory location of the first City to CityNumber.
    • CityNumber<Cities.end(): Check against the memory location of the last City.
    • CityNumber++: Step by +1.

  • *ChildCity=*CityNumber: Extract Data from Cities vector and place in ChildCity.
  • if(*ChildCity.Name == Parent.Name): Check for match.
  • return true: We got what we came for - time to book out of here.
  • return false: Uh-oh we came away empty handed.

The next function uses our Frontier vector and appears to behave as a C++ minimum priority queue based on the AccumulatedDistance + StraightLineDistance value. It will return the city with lowest distance value, as well as that distance:

//C++ Minimum Priority Queue Equivalent - Based on Distance to Goal

City	FindShortestPath(int *LowestPathDistance)
{
	vector<City>::iterator	FrontierNumber;
	vector<City>::iterator	LowestNodeNumber;

	City	CurrentCity;

	FrontierNumber=Frontier.begin();
	CurrentCity=*FrontierNumber;
	*LowestPathDistance=CurrentCity.AccumulatedDistance +
		CurrentCity.StraightLineDistance;
	LowestNodeNumber=FrontierNumber;
	FrontierNumber++;

	while(FrontierNumber<Frontier.end())
	{
		CurrentCity=*FrontierNumber;
		if(*LowestPathDistance>CurrentCity.AccumulatedDistance +
			CurrentCity.StraightLineDistance)
		{
			*LowestPathDistance=CurrentCity.AccumulatedDistance +
				CurrentCity.StraightLineDistance;
			LowestNodeNumber=FrontierNumber;
		}
		FrontierNumber++;
	}
	CurrentCity=*LowestNodeNumber;
	Frontier.erase(LowestNodeNumber);
	return CurrentCity;
}
						

Figure ISS-11: C++ Minimum Priority Queue Equivalent


Let's go through this magical C++ priority queue equivalent, and see what we've really got!!

  • C++ Minimum Priority Queue Equivalent - Function FindShortestPath

  • City FindShortestPath(int *LowestPathDistance):
    • City Returns a pointer to the city with the lowest path distance.
    • FindShortestPath: What we decided to call this puppy.
    • int *LowestPathDistance: Return the lowest path by reference.
  • vector<City>::iterator FrontierNumber: Index to step through Frontier vector.
  • vector<City>::iterator LowestNodeNumber: Pointer to Top Priority element.
  • City CurrentCity Workhorse to shuttle data out of vector so we can take a peek under the hood.
  • FrontierNumber=Frontier.begin(): Let's start by looking at the first element in our vector.
  • CurrentCity=*FrontierNumber: Transfer data out of vector.

  • *LowestPathDistance=CurrentCity.AccumulatedDistance+CurrentCity.StraightLineDistance:
    • *LowestPathDistance: Lowest Path Distance passed by reference so the value is returned.
    • CurrentCity.AccumulatedDistance: Exactly How far have we gone so far?
    • CurrentCity.StraightLineDistance: And at least how much farther do we need to go?

  • LowestNodeNumber=FrontierNumber: Preset min to the first element.
  • FrontierNumber++: We probably better start with the second element.
  • while(FrontierNumber check all remaining nodes in Frontier.
  • CurrentCity=*FrontierNumber: Transfer data out of vector.

  • if(*LowestPathDistance>CurrentCity.AccumulatedDistance+CurrentCity.StraightLineDistance):
    • Check for a lower value yet.

  • *LowestPathDistance=CurrentCity.AccumulatedDistance+CurrentCity.StraightLineDistance):
    • Save the new value if lower.

  • LowestNodeNumber=FrontierNumber: Better save the index, so we can get the rest of the data later.
  • FrontierNumber++: Check the next City on the frontier.
  • CurrentCity=*LowestNodeNumber: Better get the data before the pop.
    • This is the same as the C++ Front statement.

  • Frontier.erase(LowestNodeNumber): Remove the top priority element. Equivalent to C++ pop.
  • return CurrentCity: Send the City back to the calling routine.

Kinda cheesy if you ask me, I was expecting those cool .pop and .push statements. We did say it was equivalent, though, and we could have made a MinPriorityQueue class, but that's more diversion than we should get into right now. Maybe, we will make a real MinPriorityQueue if the need for it rears it's ugly head again.

Now that we have all the support classes, structures, and functions we need for the A* algorithm, it's time to get our hands dirty with the Real McCoy:

bool	AStarSearch(string StartName, string GoalName)
{
	vector<City>::iterator	CityNumber;

	City		CurrentCity;
	City		StartCity;
	City		ChildCity;

	Neighbor	CurrentNeighbor;
	
	bool		StartCityFound=false;
	bool		GoalFound=false;

	int		MinPossibleDistance=0;
	int		GoalDistance=0;

	string		GoalPath;

	if(StartName=="" || GoalName=="") return false;

//Search for Start Location Match

	for(CityNumber=Cities.begin();CityNumber<Cities.end();CityNumber++)
	{
		CurrentCity=*CityNumber;
		if(CurrentCity.Name==StartName)
		{
			StartCity=CurrentCity;
			StartCityFound=true;
			StartCity.AccumulatedPath=StartName;
		}
	}

	if(StartCityFound==false) return false;

	Frontier.push_back(StartCity);

	cout<<"\nRecording Exploratory Process:\n"<<"Start Location: "<<
		StartName<<"\t Ending Location: "<<GoalName<<endl;

//Get Next Location on the Frontier
			
	while(!Frontier.empty() && (GoalDistance>MinPossibleDistance || GoalFound==false))
	{
		CurrentCity=FindShortestPath(&MinPossibleDistance);
		if(GoalDistance>MinPossibleDistance || GoalFound==false)
		{
			for(	CurrentCity.NeighborNumber=CurrentCity.Neighbors.begin();
				CurrentCity.NeighborNumber<CurrentCity.Neighbors.end();
				CurrentCity.NeighborNumber++)
			{
				CurrentNeighbor=*CurrentCity.NeighborNumber;
				if(GetChildCity(CurrentNeighbor, &ChildCity)==false)
				{
					cout<<"Child City not found - Terminating\n";
					return false;
				}

				ChildCity.AccumulatedPath=CurrentCity.AccumulatedPath +
					" - " + ChildCity.Name;
				ChildCity.AccumulatedDistance=CurrentCity.AccumulatedDistance +
					CurrentNeighbor.Distance;
				cout<<"Current Expanded Path: "<<ChildCity.AccumulatedPath<<
					" Distance: "<<ChildCity.AccumulatedDistance<<endl;

				if(ChildCity.Name==GoalName)
				{
					GoalDistance=ChildCity.AccumulatedDistance;
					GoalPath=ChildCity.AccumulatedPath;
					cout<<"Goal Path: "<<GoalPath<<" Distance: "<<
						GoalDistance<<endl;
					GoalFound=true;
				}
				Frontier.push_back(ChildCity);
			}
		}
	}

	cout<<"\n\nBest Goal Path:\n";
	cout<<GoalPath<<" Distance: "<<GoalDistance<<endl;
	cout<<"Evaluation Complete\n";
	return true;
}
						

Figure ISS-12: C++ A* Search Code


It doesn't look too terribly complex. But does it really work? Let's go through the code and check to see if we don't see any missing steps requiring and then some magic happens in order to finish the job:

  • C++ Code for A* Search.

  • bool AStarSearch(string StartName, string GoalName):
    • bool returns true on successful goal completion or false on failure.
    • AStarSearch Yup, that's what we're calling it.
    • string StartName Ascii string for starting location. Case Sensitive.
    • string GoalName Academic for A* since all straight line distances are to Budapest.
      • Everything else will fail.

  • vector<City>::iterator CityNumber: Index pointer to step through Cities vector.
  • City CurrentCity: City data structure to extract elements from Cities vector.
  • City StartCity: City data structure used to match StartName parameter sent by calling routine.
  • City ChildCity: City data structure used to give possible expansion paths.
  • Neighbor CurrentNeighbor: Temporary data structure used to extract data from Neighbors structure.
  • bool StartCityFound=false: Flag indicating success or failure of finding a match for the start location.
  • bool GoalFound=false: Flag indicating success or failure on finding a match for the goal location.
  • int MinPossibleDistance=0: Comparison value used to find Best Cost route.
  • int GoalDistance=0: The current best goal distance value found.
  • string GoalPath: string used to record most recent goal path found.
  • if(StartName=="" || GoalName==""): If they sent an empty string, we might as well pack it up and call it a day.

  • Search Cities vector for Start Location Match

  • for(CityNumber=Cities.begin();CityNumber<Cities.end();CityNumber++):
    • CityNumber=Cities.begin(): Place index at first element of Cities vector.
    • CityNumber<Cities.end(): Check against last entry of Cities vector.
    • CityNumber++: Increment index by one to access each element.

  • CurrentCity=*CityNumber: Transfer data from vector into Current City object.
  • if(CurrentCity.Name==StartName): Test for match.
  • StartCity=CurrentCity: Make a copy once the match is found.
  • StartCityFound=true: Set flag indicating match was found.
  • StartCity.AccumulatedPath=StartName: This is where the path starts.
  • if(StartCityFound==false) return false: No match found - No point in searching for the goal.
  • Frontier.push_back(StartCity): Place Start City in the Frontier so we can begin the expansion process.

  • Process elements in Frontier Priority Queue according to A* rules.

  • while(!Frontier.empty() && (GoalDistance>MinPossibleDistance || GoalFound==false)):
    • while (!Frontier.empty(): If the frontier becomes empty - a match was not found.
    • GoalDistance>MinPossibleDistance: Keep search all lower distance paths even after a goal is found.

    • GoalFound==false): Keep expanding at least until a goal is found.

  • CurrentCity=FindShortestPath(&MinPossibleDistance): Get the Top Priority Element out of Frontier.
  • if(GoalDistance>MinPossibleDistance || GoalFound==false): Prevents overrun after final goal is found.

  • Expand all destination possibilities from the current location:
    • for( CurrentCity.NeighborNumber=CurrentCity.Neighbors.begin():
    • CurrentCity.NeighborNumber<CurrentCity.Neighbors.end():
    • CurrentCity.NeighborNumber++):

  • CurrentNeighbor=CurrentCity.NeighborNumber: Transfer data out of Neighbors vector into CurrentNeighbor
  • if(GetChildCity(CurrentNeighbor, &ChildCity)==false): Get the City that matches the Neighbor.
  • ChildCity.AccumulatedPath=CurrentCity.AccumualatedPath + "-" + ChildCity.Name:
    • Keep a record of the path taken to get here.
  • ChildCity.AccumulatedDistance=CurrentCity.AccumulatedDistance+CurrentNeighbor.Distance:
    • The distance traveled to get to the new location is located in the Neighbor structure.
  • if(ChildCity.Name==GoalName): Have we found a possible path yet?
  • GoalDistance=ChildCity.AccumulatedDistance:
  • GoalPath=ChildCity.AccumulatedPath: Child City contains a record of Path taken and distance to get there.
  • Frontier.push_back(ChildCity): Save the city in the Frontier for possible expansion.

  • Print out the results and exit.

Seems like it should work. Only having 1 destination keeps things simple, multiple destinations could get a little ugly with A*. Before we compile and run, C/C++ is a little picky about prototypes and headers, so we better run a quick checklist to make sure they are all there:

#include <stdio.h>
#include <string>
#include <iostream>
#include <vector>

using namespace std;

bool	GetChildCity(Neighbor, City*);

void	MakeMap();

City	FindShortestPath(int *LowestPathDistance);

bool 	AStarSearch(string, string);
						

Figure ISS-13: C++ Headers & prototypes for A* Search


If one of your prototypes is missing the compiler will complain and ask you to fix it. Let's put in main() which should give us a complete program:

int	main()
{
	MakeMap();
	AStarSearch("Arad", "Bucharest");
	return 0;
}
						

Figure ISS-14: C++ main function for A* Search


All right then, let's run it as a console application in windows or linux and see if the output matches diagram Figure ISS4:

A* Output

Figure ISS-15: Output of C++ A* Search algorithm for Romanian Map Problem


The results are entirely from cut and pasted code on this webpage. If the results don't work for you, it is probably something trivial like a character didn't get copied over or something. I didn't try it on Windows, I ran it on the Linux server that is my webhost, and I used the g++ compiler.

Breadth-First Search Home Depth First Search