Informed (Heuristic) Search Strategies (Russell Norvig)

A summary of section 3.5 in Russell Norvig Chapter 03: Solving Problems by Searching

Definition

Informed search methods have access to a heuristic function h(n) that estimates the cost of a solution from n. They may have access to additional information such as pattern databases with solution costs. (p. 123)

h(n) = the estimated cost of the cheapest path from the state at node n to a goal state.

For example, in a route finding problem, we might estimate the distance from the current state to the goal by drawing a straight line between them.

Summaries and Comparisons

RN present the following informed search strategies:

• Greedy Best-First Search

• A* Search

Memory Management

The main issue with A* search is its use of memory. RN present some implementation tricks on p. 110 to mitigate this. They then describe several variations of informed search strategies that are designed to minimize memory requirements:

Iterative-deepening A* search (or IDA*) is to A* what iterative-deepening search is to depth-first. It is a very important algorithm where problems do not fit in memory. In IDA* the cutoff is the f-cost. At each iteration, the cutoff value is the smallest f-cost of any node that exceeded the prior iteration’s cutoff. As such the only thing remembered between iterations is this cutoff value.

Recursive best-first search (or RBFS) mimics best-first search in linear space. It uses a f-limit variable to track the f-value of the best alternative path to the one being explored. If the current path exceeds that, it winds back to try the other path. Pseudocode is presented on p. 111 and the online repository.

Memory-bounded A* (MA*) and Simplified MA* (SMA*) determine how much memory is available. When memory is full, and a new leaf cannot be added to the search tree, we drop the worst leaf node (the one with the highest f-value). For the subtleties see p. 113 and the online code repository.

RN make the point that:

memory limitations can make a problem intractable from the point of view of computation time. Although no current theory explains the tradeoff between time and memory, it seems that this is an inescapable problem. The only way out is to drop the optimality requirement. (p. 113)