Hot-Link Menu in Right-Side Column

Last Updated 6-29-2010


Breadth-First Path Record

Now that we have a database we can begin to implement the Breadth-First Search algorithm in BFS-1: The database will also be used to implement the Depth-First Search Algorithm as well as the A* algorithm.

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 BFS-14: Class Implementation of Path Record


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.

Breadth-First Get Child City

A useful subroutine to make the Breadth-First Search Routine code a little more compact is returning the City with the same name as the neighbors. This city will be designated a child city of the current city we are evaluating. The code for extracting the City with the same name as one of the neighbors is as follows:

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 BFS-15: Code to extract City with same Name as Neighbor.


Listed below is an explanation of the code to extract the city from the Cities vector with the same name as the neighbor of the parent:

  • bool GetChildCity(Neighbor Parent, City* ChildCity) The function is of type bool to indicate Success (true) or failure (false) of a match being found.
    • Neighbor Parent: The name attribute of the neighbor contains the name of the city we would like to extract from the Cities vector containing the names of all the cities in the map.
    • City* ChildCity: The return pointer used to return the data structure containing the matched city from the Cities vector.

  • City TempCity: City Data Structure to temporarily hold data extracted from Cities vector.

  • vector<City>::iterator CityNumber: Index used to access individual elements in the Cities vector.

  • for(CityNumber=Cities.begin();CityNumber<Cities.end();CityNumber++): Loop through all the elements in the Cities vector.

  • TempCity=*CityNumber: Transfer of City data structure element from Cities vector

  • if(TempCity.Name==Parent.Name): Test for match of City with Neighbor.

  • *ChildCity=TempCity:Transfer data from Temporary Data structure to passed parameter.

  • return true: A successful match was found.

  • return false: No match found - Pointer invalid - unchanged.

C++ Breadth-First Search Code

Looks like there's no option here but to tackle the algorithm in Figure BFS-1 and set it into C++ code. Below is the listing corresponding to the C++ Breadth-First Search code:

//******************************************************************
// C++ Breadth-First Search Code
//******************************************************************

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

  Neighbor CurrentNeighbor;

  vector<City>::iterator CityNumber;
  vector<Neighbor>::iterator NeighborNumber;
  vector<PathRecord>::iterator PathNumber;

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

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

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

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

  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/End Location
//*****************************************************************

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

  while(!Frontier.empty() && GoalFound==false)
  {
    CurrentCity=Frontier.front();
    cout<<"\nCurrent City: "<<CurrentCity.Name<<endl;
    Explored.push_back(CurrentCity);
    Frontier.pop_front();

//*****************************************************************
// Convert Each Neighbor into a ChildCity
//*****************************************************************

    for(NeighborNumber=CurrentCity.Neighbors.begin(); NeighborNumber<CurrentCity.Neighbors.end();NeighborNumber++)
    {
      CurrentNeighbor=*NeighborNumber;
      if(GetChildCity(CurrentNeighbor, &ChildCity)==false) return false;
      if(ChildCity.Name==EndName) GoalFound=true;

//******************************************************************
// Test for Child in Explored Queue
//******************************************************************

      AlreadyExplored=false;
      ExploredCityNumber=Explored.begin();

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

//******************************************************************
// Test for Child 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++;
        }
      }

//*****************************************************************
// Add Child to Path Traveled
//*****************************************************************

      if(AlreadyExplored==false && AlreadyInFrontier==false)
      {
        Frontier.push_back(ChildCity);
        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++;
        }
      }
    }

//****************************************************************
// Display Contents of Explored Queue on each pass
//****************************************************************

    cout<<"Explored: ";

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

//****************************************************************
// Display Contents of Frontier Queue on each pass
//****************************************************************

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

  return GoalFound;
}

Figure BFS-16: C++ Breadth-First Search code


An explantion of the code is given below:

  • bool BreadthFirstSearch(string StartName, string EndName): The function is of type boolean, returning true for success, a path found, or false for failure to find a path.

  • City StartCity; This is the City structure corresponding to the StartName string sent as a parameter.

  • City CurrentCity: This City structure is used to extract data from the Frontier queue.

  • City ChildCity: This City structure contains the City with the same name as the unexplored Neighbor under analysis.

  • City ExploredCity: This City structure is used to extract City structures from the Explored queue
  • City FrontierCity: This City structure is used to extract data from the Frontier queue to determine if the Child City matches a city already in the queue.

  • Neighbor CurrentNeighbor: This Neighbor structure is used to parse the Neighbors structure of the Current City structure.

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

  • vector<Neighbor>::iterator NeighborNumber: Iterator to parse through a Neighbor vector.

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

  • deque<City> Frontier: Queue to coordinate exploring of unexplored 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 paths used to create paths traversed and save data to PathsTraveled vector

  • PathRecord TemporaryRecord(""): Record used to extract data from PathsTraveled vector

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

  • bool GoalFound: Flag used to indicate whether or not 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 PathFound: Flag used to indicate if the path to the current Neighbor City from the current location exists.

  • 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.front(): Place element in front of Frontier queue in the CurrentCity structure.

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

  • Frontier.pop_front(): Remove front element from Frontier queue.

  • for(NeighborNumber=CurrentCity.Neighbors.begin();NeighborNumber<CurrentCity.Neighbors.end();NeighborNumber++): For loop to parse through all the Neighbors of CurrentCity.

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

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

  • if(ChildCity.Name==EndName) GoalFound=true: Once we find the Goal location, it is not necessary to search any more cities. However, we must complete the loop to update the PathsTraveled data structure.

  • 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.

  • 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.

  • return GoalFound: Return success or failure.

In order to continue with this guide, and continue the discussion with Printing the Path Record which is keeping track of our progression: 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