Lecture 04.2: A* Search and Extensions

Greedy Best-First Search is fast but not optimal, because it only looks at the estimated distance to the goal ($h(n)$) and ignores the cost of the path accumulated so far.

To achieve optimal search, we want to minimize the overall length of the path. We introduce $g(n)$ as the exact cost of the best path found so far from the initial node to node $n$.

A* Search

A Search* combines the uniform-cost search with greedy best-first search. The idea is to avoid expanding paths that are already expensive.

The evaluation function for A* is: $f(n) = g(n) + h(n)$

• $g(n)$ = exact cost so far to reach $n$
• $h(n)$ = estimated cost from $n$ to goal
• $f(n)$ = estimated total cost of path through $n$ to goal

Admissible Heuristics

For A* to guarantee an optimal path, the heuristic function $h(n)$ must be admissible.

Let $h^*(n)$ be the true cost of the optimal path from $n$ to a goal node. A heuristic is admissible if it never overestimates the cost to reach the goal: $0 \le h(n) \le h^*(n)$ An admissible heuristic is always optimistic. If the heuristic never overestimates the remaining distance, A* will never confidently skip over a potentially better path.

Visualizing A* Search Expansion

Let's return to the route from Arad to Bucharest. This time, we use $f(n) = g(n) + h(n)$.

Notice that after expanding Sibiu, A* evaluates all leaves. Even though Fagaras is physically closer to Bucharest ($h=176$), the path through Rimnicu Vilcea actually yields a lower total estimated cost ($f=413$ vs $f=415$). A* correctly pivots its attention to Rimnicu Vilcea!

---

The Effect of the Heuristic Function

The choice of evaluation function drastically changes how the algorithm behaves:

• Dijkstra’s Algorithm: Expands states in the order of $f = g$ values (equivalent to A* with $h(n) = 0$). It explores evenly in all directions like a ripple.
• A Search:* Expands states in the order of $f = g + h$. It is pulled toward the goal, minimizing useless exploration.
• Weighted A Search:* Expands states in the order of $f = g + W \cdot h$, where $W > 1$. This heavily biases the search toward states closer to the goal. It finds a solution much faster but sacrifices the guarantee of optimality.

Even with a good heuristic, A* still needs to explore many near-optimal paths to be sure it isn't missing anything better. A* keeps all generated nodes in memory to reconstruct the path and avoid revisits ($O(n)$ memory), which can lead to it running out of memory on very large problems.

---

Advanced Extensions of A*

To combat memory limitations or speed up search times, several extensions of A* exist:

1. Bidirectional A*

• Idea: Runs two simultaneous A* searches, one from the start node and the other from the goal, meeting in the middle.
• Use: Significantly reduces search time but requires a well-designed heuristic that works effectively in both directions.

2. Iterative Deepening A* (IDA*)

• Idea: Combines A* with the concept of iterative deepening. Instead of a depth limit, the search is performed repeatedly with an increasing cost limit (f-value threshold).
• Use: Ideal for memory-constrained environments, as it uses only linear space (like DFS) while retaining A*'s optimality.

3. Beam A*

• Idea: Combines A* and beam search, limiting the number of nodes expanded at each level to a fixed "beam width." Only the $k$ most promising nodes are kept in the queue.
• Use: Useful in scenarios where memory is extremely limited or when a fast, albeit non-optimal, solution is acceptable.