Hot-Link Menu in Right-Side Column

Last Updated 6-29-2010


C++ Depth-First Print Goal Path()

Of course, no self-respecting program wouldn't tell about the great work, it has just accomplished. For this reason, a little routine needs to display the path taken to arrive at our intended location:


//Goal Path will print the path used to locate the Goal
//Supply the name of the goal after a search has been successful

void	PrintGoalPath(string GoalName)
{
	vector<PathRecord>::iterator	PathNumber;
	PathRecord			TemporaryRecord("");

	cout<<"\nGoal Path:  "<<endl;

	for(PathNumber=PathsTraveled.begin();PathNumber<PathsTraveled.end();PathNumber++)
	{
		TemporaryRecord=*PathNumber;
		if(TemporaryRecord.LastEntry==GoalName)
			cout<<TemporaryRecord.AccumulatedPath
				<<"  "<<TemporaryRecord.AccumulatedDistance<<endl;
	}
	cout<<endl;
}
						

Figure DFS-12: Code to print goal path.


A description of the code is given below:

  • void PrintGoalPath(string GoalName): Prints any path that ended with the same name as supplied as a parameter.

  • vector<PathRecord>::iterator PathNumber: Create an iterator to step through all paths recorded in the search.

  • PathRecord TemporaryRecord(""): Create a container to extract data from PathRecord vector.

  • for(PathNumber=PathsTraveled.begin( );PathNumber<PathsTraveled.end( );PathNumber++): Step through all recorded paths.

  • TemporaryRecord=*PathNumber: Transfer data out of PathRecord vector.

  • if(TemporaryRecord.LastEntry==GoalName): Print the path if the end point matches the parameter supplied.

C++ Depth-First Main()

Now that all of the necessary functions have been created. We can take this puppy for a test spin, and see what kind of results come out. Don't forget to complete the data table, and declare the functions, somewhere before they are used. We will need to make a couple of minor modifications to main, so it calls out the Depth-First Search and prints the results. Listed below is the change to the main( ) function:


//Program Starts here:

int	main()
{
	bool	GoalFound;

	MakeMap();
	string	StartLocation="Arad";
	string GoalState="Bucharest";
	GoalFound=DepthFirstSearch(StartLocation, GoalState);
	if(GoalFound) PrintGoalPath(GoalState);
		else 	cout<<"Couldn't Do It - "<<GoalState<<" is nowhere to be found!!\n";
	return 0;
}


						

Figure DFS-13: C++ main( ) function for Depth-First Search map program


Cutting and pasting all of the above code examples, and placing them in a file called r5.cpp, adding in the necessary function declaration statements like: bool DepthFirstSearch(string, string); then compiling the file with the GNU C++ linux compiler gives us the following output:

Depth First 2

Figure DFS-14: Output listing of C++ Depth-First Search


Well, according to this result, we were better off with the Breadth-First Search. I would suppose that sometimes the Depth-First search might outperform the Breadth-First Search, depending on how we stack the dataset. The time-complexity of the Breadth-First search is bounded by the size of the state space (which may be infinite). A depth-first tree search, on the other hand, may generate all of the O(bm) nodes in the search tree, where m is the maximum depth of any node; this can be much greater than the size of the state space. Note that m itself can be much larger than d (the depth of the shallowest solution) and is infinite if the tree is unbounded.

So far, depth-first search seems to have no clear advantage over breadth-first search, so why even consider it? The reason is space complexity. For a graph search, there is no advantage whatsoever, but, a depth-first tree search needs to store only a single path from the root to a leaf node, along with the remaining unexpanded sibling nodes for each node on the path. Once a node has been expanded, it can be removed from memory as soon as all of it's descendants have been fully explored as shown in figure DFS-1. For a state space with branching factor b and maximum depth m, depth-first search requires only O(bm) nodes. Using the same assumptions as for Figure BFS-19 and assuming that nodes at the same depth as the goal node have no successors, we find that depth-first search would require 156 kilobytes instead of 10 exabytes at depth d=16, a factor of 7 trillion times less space. This has led to the adoption of depth-first tree search as the basic work-horse of many areas of AI, including constraint satisfaction, propositional satisfiability, and logic programming. We will now focus on the tree-search version of depth-first search.

A variant of depth-first search called backtracking search uses still less memory. In backtracking, only one successor is generated at at time rather than all successors; each partially expanded node remembers which successor to generate next. In this way, only O(m) is needed rather than O(bm). Backtracking search facilitates yet another memory and time saving trick: the idea of generating a successor by modifying the current state description rather than copying it first. This reduces the memory requirements to just one state description and O(m) actions. For this to work, we must be able to undo each modification when we go back to generate the next successor. For problems with large state descriptions, such as robotic assembly, these techniques are critical to success.


Depth Limited Search

The embarrasing failure of depth-first search in infinite state spaces can be alleviated by supplying depth-first search with a predetermined depth-limit of l. That is, nodes at depth l are treated as if they have no successors. This approach is called Depth Limited Search. The depth limit solves the infinite-path problem. Unfortunately, it also introduces an additional source of incompleteness if we choose l<d, that is, the shallowest goal is beyond the depth limit (which is likely when d is unknown). Depth Limited Search will also be non-optimal if we choose l>d. Its time complexity is O(bl) and its space complexity is O(bl). Depth-first search can be viewed as a special case of depth-limited search with l=∞.

Sometimes, depth limits can be based on knowledge of the problem. For example, on the map of Romania there are 20 cities. Therefore, we know that if there is a solution, it must be of length 19 at the longest, so l=19 is a possible choice. But, in fact, if we studied the map carefully, we would discover that any city can be reached from any other city in at most 9 steps. This number, known as the diameter of the state space, gives us a better depth limit, which leads to a more efficient depth-limited search. For most problems, however, we will not know a good depth limit until we have solved the problem.

Depth-limited search can be implemented as a simple modification to the general tree-graph or graph-search algorithm. Alternatively, it can be implemented as a simple recursive algorithm. Notice that depth-limited search has two modes of failure:

  1. standard failure - no solution.
  2. cutoff failure - no solution within the depth limit.

In order to continue with this guide, and start the discussion of Iterative Deepening Depth 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