Hot-Link Menu in Right-Side Column

Last Updated 6-29-2010


C++ A* GetChildCity()

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.

C++ A* Find Shortest Path

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.

In order to continue with this guide, and complete the discussion of C++ A* Search 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