Hot-Link Menu in Right-Side Column

Last Updated 6-29-2010


Breadth-First Main Program

I think it's time to make our 'main' function. I am going to use the linux g++ compiler over the SSH connection, because my Windows is so slow and clunky, and the linux is fast, so I like it. Developing the Windows project as a console application, will be pretty close, if you insist, just slower. I also like the g++ error description, it's pretty easy to figure out what they don't like. Windows is kind of cryptic.

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

Figure BFS-5: Main Program Section for Romania Map Search Functions

That's pretty much all we want main to do right now, we'll put in a call to breadth-search a little later. I like to print out the data first, so it's easier to see how to manipulate the data.

  • int main( ): Line that tells OS where to start program execution. Declared as int, because Linux wants a status on exit
  • MakeMap( ): This function will place data in our data structures: Cities, City & Neighbors
  • PrintCities( ): This function will print out all the data, sorted by City & Neighbors
  • return 0: 0 tells the OS all went well. Other values can make the OS perform different actions

Make Map Reference for Breadth-First

Before we can print out the data - we need to enter it. Let's enter the data for "Oradea" and see what it looks like:

void MakeMap()
{
  City TempCity;
  Neighbor TempNeighbor;

//Enter Data for Oradea

  TempCity.Name="Oradea";

  TempNeighbor.Name="Zerind";
  TempNeighbor.Distance=71;
  TempNeighbor.ShortestDistance=374;
  TempCity.Neighbors.push_back(TempNeighbor);

  TempNeighbor.Name="Sibiu";
  TempNeighbor.Distance=151;
  TempNeighbor.ShortestDistance=253;
  TempCity.Neighbors.push_back(TempNeighbor);

  Cities.push_back(TempCity);
}

Figure BFS-6: Start code for MakeMap


This code will allow us to enter the data relevant to Oradea. Let's look at what is happening;

  • void MakeMap( ): We don't need to return anything, because we are going to enter the data manually for this example.
  • City TempCity: A temporary container so we can place our information in the 'Cities' vector.
  • Neighbor TempNeighbor A temporary container so we can place the neighbor characteristics in the 'Neighbor' vector.
  • TempCity.Name="Oradea": Give the city a name.

  • TempNeighbor.Name="Zerind": Give Oradea's first neighbor a name.
  • TempNeighbor.Distance= 71: This is the distance between Oradea and Zerind from way back at Figure Agent-2.
  • TempNeighbor.ShortestDistance= 374: This is the straight line distance between Zerind and Bucharest, for the A* algorithm.
  • TempCity.Neighbors.push_back(TempNeighbor): Save the 'Zerind' data in 'Oradeas' Neighbor vector.

  • Now that we have copied the contents of TempNeighbor in the vector, we can reuse the variable for the next city.
  • Repeat the Neighbor steps for Sibiu so we can have 2 neighbors for Oradea.

  • Cities.push_back(TempCity): Save Oradea data in the Cities vector. ==> Cities vector now has all the data it needs for Oradea

I can see right now, entering the data for all these cities is going to be quite tedious. We can make a function, to ease the burden a little bit, but I'm tempted to make an optical character recognition program, to scan the distances in automatically, but I guess we'll save that for another day, and just muddle through.

Breadth-First Make Neighbor Function

The following code snippet will ease the data entry process, since we are going to have it make a Neighbor, why don't we call it something really imaginative like ... MakeNeighbor ( ):

Neighbor MakeNeighbor (string NeighborName, int PathLength, int StraightLineDistance)
{
  Neighbor SomeCity;

  SomeCity.Name=NeighborName;
  SomeCity.Distance=PathLength;
  SomeCity.ShortestDistance=StraightLineDistance;

  return SomeCity;
}

Figure BFS-7: C++ Code to Make a Neighbor


  • Neighbor MakeNeighbor(string NeighborName, int PathLength, int StraightLineDistance):
    • Neighbor MakeNeighbor ( ): Since we are creating an entity of type Neighbor, we will return a pointer to the data we just entered.
    • string NeighborName: This is the name of the neighbor we are creating
    • int PathLength: This the distance between our city of origin and the neighbor we are creating.
    • int StraightLineDistance: This is the distance between our Neighbor and our goal city of Bucharest.

  • Neighbor SomeCity: We are going to create a temporary copy of a Neighbor which will we can return to the calling function.

  • SomeCity.Name=NeighborName: This fills in the Name portion of our Neighbor structure.

  • SomeCity.Distance=PathLength: This fills in the distance portion of our Neighbor structure.

  • SomeCity.StraightLineDistance: This fills in the ShortestDistance portion of our Neighbor structure.

  • return SomeCity: Place the pointer to our temporary Neighbor structure on the stack, so the calling routine can save it somewhere.

Breadth-First Create Point of Origin

Below is the code to make another point of origin to place in our MakeMap ( ) function, but this time using our MakeNeighbor function:

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

TempCity.Neighbors.push_back(MakeNeighbor("Oradea",71,380));
TempCity.Neighbors.push_back(MakeNeighbor("Arad",75,366));

Cities.push_back(TempCity);

Figure BFS-8: Code to create point of origin using MakeNeighbor ( )


Well, that's better than Figure 19, but it's still going to be a lot of data entry. Here is the explanation of what is happening:

  • TempCity.Name="Zerind": We are going to reuse our TempCity structure to make the remaining points of origin.

  • TempCity.Neighbors.clear ( ): The information from Oradea is still in our neighbors vector, so we have to clear it out, or else it just accumulates every time we do a push_back.

  • TempCity.Neighbors.push_back(MakeNeighbor("Oradea",71,380)): Stuff the data returning from our MakeNeighbor ( ) function immediately into the TempCity Neighbors vector.

  • Cities.push_back(TempCity): Save the Zerind data in our Cities vector for safe keeping.

In order to continue with this guide, and continue the discussion on Developing the PrintCities() subroutine for Breadth-First Search: 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