Informed Search

It is not difficult to see that uninformed search will pursue options that lead away from the goal as easily as it pursues options that lead to wards the goal. For any but the smallest problems this leads to searches that take unacceptable amounts of time and/or space. Informed search tries to reduce the amount of search that must be done by making intelligent choices for the nodes that are selected for expansion. This implies the existence of some way of evaluating the likelyhood that a given node is on the solution path. In general this is done using a heuristic function.

Best First Searches

Suppose that one has an evaluation function h(n) defined at each node n that estimates the cost of reaching the goal from that node. A search that chooses the node on the agenda for which this function is smallest is called a greedy search. Greedy searches need not be complete, and they do not necessarily detect the shortest path. Its worst case performance is no better than breadth first search.

Examples

In a route finding problem that 'straight line' distance form the node to the goal can be used to evaluate each node.
In the case of missionaries and cannibals one can compute the number of boat trips required to transport everybody to the other side ignoring the anthropophagous tendencies of the cannibals.

A * search

Another way to evaluate the nodes on the agenda is to use the function f(n) given as the sum of the cost g(n) to reach the node on the current path plus h(n), the estimated cost of reaching the goal from n. The algorithm that chooses the node on the agenda for which this fucntion is minimal is called A*. It is considered important because

It is actually useable, provided one has an h(n) and
Under certain conditions it is guaranteed to terminate and prduce the shortest path.

Admissible Heuristics

A heuristic function h(n) is called admissible if for all nodes one has h(n) < k(n) where k(n) is the actual distance to the goal from n. Both of the heuristics given above are admissible.
If all the costs are positive and the heuristic is admissible then A* terminates and finds the shortest path. Like breadth first search A* can use a lot of memory. If we combine the iterative deeepening idea with A* one gets an algorithm called IDA* (for iterative deepening A*). The space is searched depth first for successively larger bounds on the heurisitic function f(n).
Code

A * search 1 This version makes the agenda quite explicit.
A* search 2 This version is taken from the book of Ivan Bratko.
IDA* search This is such a procedural search that I was unalbe to avoid using assert and retract.

Return to UG AI home page
Last Changed: 2 October 1995