Hot-Link Menu in Right-Side Column
Last Updated 6-29-2010
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:
A description of the code is given below:
Creating and running the executable gives us the following output for the Breadth-First Search:
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:
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.
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:
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:
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.
Artificial IntelligenceBig O Notation
Problem DefinitionFormulating Problems
The Knuth Sequence
Real World Problems
Route Finding Problems
Traveling Salesperson Problem
Automatic Assembly Sequencing
Searching For Solutions
Frontier Node ExpansionSearch Algorithm Infrastructure
Child Node Creation
Measuring Algorithm Performance
Uninformed Search StrategiesBreadth-First Search
C++ Breadth-First Search Code
Breadth-First Data Structure
Breadth-First Main ProgramBreadth-First Make Map
Breadth-First Make Neighbor
Breadth-First Point of Origin
Breadth-First Print CitiesBreadth-First Initial Listing
Breadth-First Path RecordBreadth-First Get Child City
C++ Breadth-First Search Code
Breadth-First Print Goal PathUniform-Cost Search
Depth-First SearchDepth-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()
Iterative Depth SearchBidirectional Search
Informed Search StrategiesGreedy Best-First
Conditions For OptimalityOptimality of A*
C++ A* Search CodeA* Search Data Structure
A* Search Data Entry
A* Search GetChildCity()C++ Min Priority Queue
C++ A* Search Code FunctionC++ A* Headers & Prototypes
C++ A* Search Main()
Normalized Information Distance