Hot-Link Menu in Right-Side Column

Last Updated 6-29-2010


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


C++ City Class Data Structure

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.

A* Search Data Entry

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.

In order to continue with this guide, and start the discussion of C++ A* GetChildCity Function and the corresponding C++ code:

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