Hot-Link Menu in Right-Side Column

Last Updated 6-29-2010


Informed Search Strategies

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

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:

City Distance City Distance City Distance City Distance
Arad 366 Bucharest 0 Craiova 160 Drobeta 242
Eforie 161 Fagaras 176 Giurgiu 77 Hirsova 151
Iasi 226 Lugoj 244 Mehadia 241 Neamt 234
Oradea 380 Pitesti 100 Rimnicu Vilcea 193 Sibiu 253
Timisoara 329 Urziceni 80 Valusi 199 Zerind 374

Figure ISS-1: Values of hSLD - straight line distances to Bucharest


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:

Greedy Expansion

Figure ISS-2: Stages in Greedy Best-First Search for 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.

Romania map

Figure ISS-3: Data Source for C++ A* Search Code Example


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.

A* Search: Minimizing the total estimated solution cost

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:

f(n)=g(n)+h(n).

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.

In order to continue with this guide, and start the discussion of Conditions for Optimality: Admissability and Consistency: 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