Heuristic Search

Using Estimated Distance Remaining

Another procedure specific to the problem: estimate, which takes a state and estimates the distance to a goal state
Hill climbing
Sort the new paths by the estimated distance left to the goal (using estimate) and add them to the front of the queue.
- Parameter-oriented hill climbing: each problem state is a setting for a set of parameters
- Problems for hill-climbing: foothills (local maxima), plateaus, ridges
- Nondeterministic search as a way of escaping from local maxima
- Gradient ascent
  For a parameter x and ``goodness'' g which is a smooth function of x, the change in x should be proportional to the speed with which g changes as a function of x, that is,
Best-first search
After adding new paths to the queue, sort all the paths in the queue by the estimated distance left to the goal (using estimate).
Unlike hill climbing, can jump around in the search space.

British Museum procedure: blindly find all paths, selecting best
Branch-and-bound search
After adding new paths to the queue, sort all the paths in the queue by the current path length.
Note: When a goal state is found, it is still necessary to extend partial paths which are shorter than the complete one because they may end up shorter overall.
Using underestimates of distance remaining
After adding new paths to the queue, sort all the paths in the queue by an underestimate of total path length (using estimate).
Underestimates allow you to stop when partial path estimates are longer than the shortest complete path.
Eliminating redundant paths
After adding new paths to the queue, if there are two or more paths reaching a common node, keep only the one with the shortest path length.
A*: branch-and-bound with underestimates and redundant paths eliminated

Last updated: 16 January 1996
URL: http://www.indiana.edu/~gasser/Q351/search3.html
Comments: gasser@salsa.indiana.edu
Copyright 1996, The Trustees of Indiana University