Hot-Link Menu in Right-Side Column
Last Updated 6-29-2010
This section shows how an informed search strategy - one that uses problem-specific knowledge beyond the definition of the problem itself - can find solutions more efficiently than can an uninformed search strategy.
The general approach we consider is called best first search. Best-first search is an instance of the general Tree-Search or Graph-Search algorithm in which a node is selected for expansion based on an evaluation function, f(n). The evaluation function is construed as a cost-estimate, so the node with the lowest evaluation is expanded first. The implementation of best first graph search is identical to that for Uniform-Cost Search, except for the use of f instead of g to order the priority queue.
The choice of f determines the search strategy. Most best-fit algorithms include as a component of f a heuristic function denoted h(n):
h(n) = estimated cost of the cheapest path from the state at node n to a goal state.
Notice that h(n) takes a node as an input, but, unlike g(n) it depends only on the state at that node. For example, one might estimate the cost of the cheapest path from Arad to Bucharest via the straight-line distance from Arad to Bucharest.
Heuristic functions are the most common form in which additional knowledge of the problem is imparted to the search algorithm. We also consider them to be arbitrary, nonnegative, problem specific functions, with one constraint: if n is a goal node, then h(n)=0. Following are two ways to use heuristic information to guide search.
Greedy best-first search tries to expand the node that is closest to the goal, on the grounds that it is likely to lead to a solution quickly. Thus, it evaluates nodes by using just the heuristic function; that is, f(n)=h(n).
Let us see how this works for the route-finding problems in Romania; we use the straight-line distance heuristic, which we will call hSLD. If the goal is Bucharest, we need to know the straight-line distances to Bucharest, which are shown in Figure ISS-1:
Notice that the values of hSLD cannot be computed from the problem description itself. Moreover, it takes a certain amount of experience to know that hSLD is correlated with actual road distances and is, therefore, a useful heuristic.
Figure ISS-2 shows the progress of a greedy best-first search using hSLD to find a path from Arad to Bucharest:
The first node to be expanded from Arad will be Sibiu because it is closer to Bucharest then either Zerind or Timisoara. The next node to be expanded will be Fagaras because it is closest. Fagaras, in turn, generates Bucharest, which is the goal. For this particular problem, greedy best-first search using hSLD finds a solution without ever expanding a node that is not on the solution path; hence, its search cost is minimal. It is not optimal, however: the path via Sibiu and Fagaras to Bucharest is 32 kilometers longer than the path through Rimnicu Vilcea and Pitesti. This shows why the algorithm is called "Greedy" - at each step it tries to get as close to the goal as it can.
Greedy best-first tree search is also incomplete even in a finite state space, much like depth-first search. Consider the problem of getting from Iasi to Fagaras. The heuristic suggests that Neamt will be expanded first because it is closest to Fagaras, but it is a dead end street. The solution is to go first to Vaslui - a step that is actually farther from the goal according to the heuristic - and then continue to Urziceni, Bucharest, and Fagaras. The algorithm will never find this solution, however, because expanding neamt puts Iasi back into the frontier, Iasi is closer to Fagaras than Valusi is, and so Iasi will be expanded again, leading to an infinite loop. (The graph search version is complete in finite spaces, but not in infinite ones.) The worst case time and space complexity for the tree version is O(bm), where m is the maximum depth fo the search space. With a good heuristic function, however, the complexity can be reduced substantially. The amount of reduction depends on the particular problem and on the quality of the heuristic.
The most widely known form of best-first search is called A* search (pronounced "A-star search"). It evaluates nodes by combining g(n), the cost to reach the node, and h(n), the cost to get from the node to the goal:
Since g(n) gives the path cost from the start node to node n, the goal node, and h(n) is the estimated cost of the cheapest path from n to the goal, we have:
f(n) = estimated cost of the cheapest solution through n.
Thus, if we are trying to find the cheapest solution, a reasonable thing to try first is the node with the lowest value of g(n)+h(n). As it turns out, this strategy is more than just reasonable: provide that the heuristic function, h(n), satisfies certain conditions, A* search is both complete and optimal. The algorithm is identical to Uniform-Cost Search except that A* uses g+h instead of g.
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