A-Star Search

search

Definition

A* Search

A* search is a heuristic search strategy that uses an evaluation function , where:

• is the path cost from start to
• is the estimated cost to goal from (must be admissible to be optimal)
• is the estimated total cost of path through to goal

Expansion

Note that expands:

• all nodes with
• some nodes with
• no nodes with
• fewest nodes safely possible, if is consistent

Properties

Completeness

Yes, unless there are infinitely many nodes with .

Time Complexity

Exponential complexity in , where:

Space Complexity

Exponential complexity since it keeps all nodes in memory.

Optimality

If is admissible, then using tree search is optimal.

Memory-Bounded Search

Iterative Deepening Search A* (IDFA)

A big issue of A* search is its memory consumption. Remedy:

• Pruning of reached set, avoid duplication in reached, frontier
• Iterative-deepening search A* (IDA*): akin to IDS
  • initialise limit cost
  • generate and keep nodes with
  • use smallest value as next limit , and repeat

exhaustively search an -contour, and expand minimally to the next -contour. It avoids storage of nodes beyond optimal cost and works well for the 8-puzzle.

Recursive First-Best Search (RFBS)

An alternative approach is to mimic first-best search, using only linear space:

• Recursive first-best search (RFBS):
  • variable : -value of the best alternative path from any ancestor of the current node
  • If exceeds unwind back to alternative path
  • In unwinding, change the -values of nodes to the best (lowest) -value of their children
  • remember lowest -value in the subtree

RFBS is optimal if is admissible.