Hot-Link Menu in Right-Side Column

Last Updated 6-29-2010


C++ Depth-First Search GetChildCity()

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.


C++ Depth-First PathRecord Class

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.

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


Home


Artificial Intelligence

Big O Notation

NP Completeness

Intelligent Agents


Problem Definition

Formulating Problems

Toy Problems

Vacuum World


8-Puzzle

8 Queens

The Knuth Sequence

Real World Problems

Route Finding Problems

Touring Problems

Traveling Salesperson Problem

VLSI Layout

Robot Navigation

Automatic Assembly Sequencing


Searching For Solutions


Frontier Node Expansion

Search Algorithm Infrastructure

Child Node Creation

Measuring Algorithm Performance


Uninformed Search Strategies

Breadth-First Search

Breadth-First Characteristics

C++ Breadth-First Search Code

Breadth-First Data Structure


Breadth-First Main Program

Breadth-First Make Map

Breadth-First Make Neighbor

Breadth-First Point of Origin


Breadth-First Print Cities

Breadth-First Initial Listing


Breadth-First Path Record

Breadth-First Get Child City

C++ Breadth-First Search Code


Breadth-First Print Goal Path

Uniform-Cost Search


Depth-First Search

Depth-First C++ Solution

Depth-First Data Structure


Depth-First MakeMap()

Depth-First Display Data

Depth-First Initial Listing


Depth-First GetChildCity()

Depth-First Path Record


Depth-First Search Function


Depth-First PrintGoalPath()

Depth-First Main()

Depth-Limited Search


Iterative Depth Search

Bidirectional Search

Comparing Strategies


Informed Search Strategies

Greedy Best-First

A* Search


Conditions For Optimality

Optimality of A*


C++ A* Search Code

A* Search Data Structure

A* Search Data Entry


A* Search GetChildCity()

C++ Min Priority Queue


C++ A* Search Code Function

C++ A* Headers & Prototypes

C++ A* Search Main()


Normalized Information Distance