A* Search

search

Definition

A* Search

A* search is a heuristic search strategy that uses an evaluation function $f(n)=g(n)+h(n)$, where:

• $g(n)$ is the path cost from start to $n$
• $h(n)$ is the estimated cost to goal from $n$ (must be admissible to be optimal)
• $f(x)$ is the estimated total cost of path through $n$ to goal

Expansion

Note that $A^{\ast }$ expands:

• all nodes with $f(n)\le C^{\ast }$
• some nodes with $f(n)=C^{\ast }$
• no nodes with $f(n)>C^{\ast }$
• fewest nodes safely possible, if $h$ is consistent

Properties

Completeness

Yes, unless there are infinitely many nodes $n$ with $f(n)\le f(G)$.

Time Complexity

Exponential complexity in $\epsilon \times d$, where:

$$\begin{array}{rl}\epsilon & =\frac{h(n_0)-h^{\ast }(n_0)}{h^{\ast }(n_0)}\dots \text{ relative error }(h^{\ast }(n_0)=C^{\ast })\\ d& =\text{solution depth (= path length)}\end{array}$$

Space Complexity

Exponential complexity since it keeps all nodes in memory.

Optimality

If $h$ is admissible, then $A^{\ast }$ 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 $C$
  • generate and keep nodes $n$ with $f(n)\le C$
  • use smallest value $f(n)>C$ as next limit $C^{\prime }$, and repeat

$⟹$ exhaustively search an $f$-contour, and expand minimally to the next $f$-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 $f\_limit$: $f$-value of the best alternative path from any ancestor of the current node $n$
  • If $f(n)$ exceeds $f\_limit⟹$ unwind back to alternative path
  • In unwinding, change the $f$-values of nodes to the best (lowest) $f$-value of their children
  • $⟹$ remember lowest $f$-value in the subtree

RFBS is optimal if $h(n)$ is admissible.