A* Algorithm — Beginner-Friendly Notes

1. What A* Is (the most important informed search)

Combine actual cost so far $g(n)$ + heuristic estimate to goal $h(n)$:

• $g(n)$ = cheapest cost from start to $n$ found so far.
• $h(n)$ = estimated cost from $n$ to goal (must be admissible — next topic).
• $f(n)$ = estimated total cost through $n$ to goal. A* always expands smallest $f(n)$ first.

A* = UCS ($g$) + Greedy ($h$) — cost-aware and goal-directed.

2. How It Works

Priority queue by $f(n)$. Like UCS but with heuristic guidance.

frontier = priority queue by f(n) = g(n) + h(n)
push initial with f = h(initial)
while frontier not empty:
  node = pop smallest f(n)
  if goal_test(node): return path  # optimal if h is admissible
  for child:
    g(child) = g(node) + step_cost
    f(child) = g(child) + h(child)
    push/update child in frontier

Needs visited/closed set with best $g$ handling.

3. Why Optimal (when h is admissible — see next topic)

If $h(n)$ never overestimates true cost $h*(n)$, $f(n)$ never overestimates total true cost, so first goal popped has optimal $f$ = optimal cost. Formal proof in textbook, but intuition: A* won't skip a cheaper path because its $f$ would still look cheaper.

4. Properties

Property	Value (with admissible $h$)
Complete	Yes (finite branching, positive costs)
Optimal	Yes if $h$ admissible; optimal and optimally efficient (expands fewest nodes among optimal algorithms for same $h$)
Time	$O(b^d)$ worst, but much less with good $h$
Space	$O(b^d)$ — still memory heavy like BFS (main drawback)

5. Heuristic Examples

• 8-puzzle: $h1$ = misplaced tiles, $h2$ = Manhattan distance (sum of tile distances) — $h2$ dominates $h1$.
• Map: straight-line distance.
• Grid pathfinding: Manhattan/Euclidean distance.

6. When to Use

• When you have a good admissible heuristic and need optimal + fast.
• Default choice for pathfinding, puzzles, planning.

7. One-Line Summary

A* expands nodes by $f(n)=g(n)+h(n)$ and is complete and optimal when $h$ is admissible, combining cost-so-far with heuristic guidance to find optimal paths efficiently.

8. Quick Self-Check

1. What is $f(n)$ for a node with $g=5$, $h=3$?
2. Why is A* optimally efficient vs UCS?