Hot-Link Menu in Right-Side Column

Last Updated 6-29-2010


Breadth-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 BFS-18: 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.

Creating and running the executable gives us the following output for the Breadth-First Search:

Arad-Bucharest Breadth First

Figure BFS-19: Breadth-First Search Output.


So far, the news about breadth-first search has been good. The news about time and space is not so good. Imagine searching a uniform tree where every state has b successors. The root of the search tree generates b nodes at the first level, each of which generates b more nodes, for a total of b2 at the second level. Each of these generates b more nodes, yielding b3 nodes at the third level, and so on. Now suppose that the solution is at depth d. In the worst case it is the last node generated at that level. Then the total number of nodes generated is:

b + b2 + b3 + ... + bd = O(bd).

d would be expanded before the goal was detected and the time complexity would be O(bd+1).).

As for space complexity: for any kind of graph search, which stores every expanded node in the explored set, the space complexity is always within a factor of b of teh time complexity. For breadth-first graph search, in particular, every node generated remains in memory. There will be O(bd-1) nodes in the explored set and O(bd) nodes in the frontier, so the space complexity is O(bd), i.e., it is dominated by the size of the frontier. Switching to a tree search would not save much space, and in a state space with many redundant paths, switching could cost a great deal of time.

An exponential complexity bound such as O(bd) quickly becomes unwieldy. Figure BFS-19 shows why. It lists for various solutions of depth d, the time and memory required for a breadth-first search with branching factor b = 10. The table assumes that 1 million nodes can be generated per second, and each node requires 1000 bytes of storage. Many search problems fit roughly within these assumptions, give or take a few orders of magnitude:

Depth Nodes Time Memory
2 110 .11 mS 107 kB
4 11,110 11 mS 10.6 MB
6 106 1.1 Sec 1 GB
8 108 2 Min 103 GB
10 1010 3 hours 10 TB
12 1010 13 days 1 PB
14 1014 3.5 Years 99 PB
16 1016 350 Years 10 XB

Figure BFS-20 Time and Memory Requirements for Breadth-First Search


Two lessons can be learned from Figure BFS-20. First, the memory requirements are a bigger problem for breadth-first search than the execution time. Looking at a node depth of 12, one might wait 13 days for the solution to an important problem, but personal computers do not currently have 1 petabyte of memory it would take. Fortunately, other strategies require less memory.

The second lesson is that time is still a major factor. If your problem has a solution of depth 16, then it could take 350 years for breadth-first or most any other uniformed search strategy to find a solution. In general, exponential-complexity search problems cannot be solved by uninformed methods, for any but the smallest instances.


Uniform-Cost Search

When all step costs are equal, breadth-first search is optimal because it always expands the shallowest unexpanded node. By a simple extension, we can find an algorithm that is optimal with any step-cost function. Instead of expanding the shallowest node, uniform-cost search expands the node n the the lowest path cost g(n). This is done by storing the frontier as a priority queue ordered by g. The algorithm is shown in Figure UCS-1:

function Uniform-Cost Search(problem)returns a solution or failure.
  node←a node with State = problem. Initial-State, Path-Cost=0
  frontier←a priority queue ordered by Path-Cost, with node as the only element.
  explored←Empty Set

  loop do
    if Empty?(frontier) then return failure.
    nodePOP(frontier) /*chooses the lowest code node in frontier */
    If problem.Goal-Test(node.State) then return Solution(node).
    add node.State to explored.

    for each action in problem.Actions (node.State) do
      childChild-Node(problem, node, action)
      if child.State is not in explored or frontier then
        frontierInsert(child, frontier)
      else if child.State is in frontier with higher Path-Cost then
        replace that frontier node with child.

Figure UCS-1: Uniform-cost search on a graph.


The algorithm of Figure UCS-1 is identical to the general search algorithm in BFS-1, except for the use of a priority queue and the addition of an extra check in case a shorter path to a frontier state is discovered. The data structure for frontier needs to support efficient membership testing, so it should combine the capabilities or a priority queue and a hash table.

In addition to the ordering of the queue by the path-cost, there are two other significant differences from breadth-first search. The first is that the goal test is applied to a node when it is selected for expansion (as in the graph-search algorithm shown in Figure BFS-1) rather than when it is first generated. The reason is that the first goal node that is generated may be on a suboptimal path. The second difference is that a test is added in case a better path if found to a node currently on the frontier.

Both of these modification come into play in Figure UCS-2, where the problem is to get from Sibiu to Bucharest. The successors of Sibiu are Rimnicu Vilcea and Fagaras, with costs of 80 and 99, respectively. The least-cost node, Rimnicu Vilcea, is expanded next, adding Pitesti with cost 80+97=177. The least-cost node is now Fagaras (177>99), so it is expanded, adding Bucharest with cost 99+211=310. Now a goal has been generated, but, Uniform Cost Search keeps going, choosing Pitesti for expansion and adding a second path with cost: 80+97+101=278. Now the algorithm checks to see if this new path is better than the old one; it is, so the old one is discarded. Bucharest, now with g-cost 278, is selected for expansion and the solution is returned:

Sibiu - Bucharest

Figure UCS-2: Sibiu to Bucharest Uniform Cost Search Diagram


It is easy to see that uniform-cost search is optimal in general. First, we observe that whenever uniform-cost search selects a node n for expansion, the optimal path to that node has been found. (Were this not the case, there would have to be another frontier node n' on the optimal path from the start to node n, by graph separation property of Figure Agent-11; by definition, n' would have lower g-cost than n and would have been selected first.) Then, because step costs are nonnegative, paths never get shorter as nodes are added. These two facts together imply that Uniform-Cost Search expands nodes in order of their optimal path cost. Hence, the first goal node selected for expansion must be the optimal solution.

Uniform-cost search does not care about the number of steps a path has, but only about their total cost. Therefore, it will get stuck in an infinite loop if there is a path with an infinite sequence of zero-cost actions - for example, a sequence of No Op actions. Completeness is guaranteed provided the cost of every step exceeds some small positive constant ε.

Uniform-cost search is guided by path costs rather than depths, so its complexity is not easily characterized in terms of the depth, or the number of nodes. Instead, let C* be the cost of the optimal solution, and assume that every action costs at least ε. Then the algorithm's worst-case time and space complexity is O(b1+[C*/ε]), which can be much greater than bd. This is because uniform-cost search can explore large trees of small steps before exploring paths involving large and perhaps useful steps. When all step costs are equal, b1+[C*/ε] is just bd+1. When all step costs are the same, uniform-cost search is similar to breadth-first search, except that the latter stops as soon as it generates a goal, whereas uniform-cost search examines all the nodes at the goal's depth to see if one has a lower cost; thus uniform-cost search does strictly more work by expanding nodes at depth d unnecesarily.

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