Course contentsShow
← Computer Science
Lesson 2752 of 2,87261. AI and Search AlgorithmsFree lesson

A* Search Algorithm

Master A* search, which combines path cost and heuristic to find optimal solutions efficiently.

A* Search Algorithm

What you'll learn: How A* combines actual path cost and heuristic estimates to find optimal solutions more efficiently than uninformed or purely greedy search.

The Core Idea

A* (pronounced "A-star") is the gold standard for informed search. While Greedy Best-First Search uses only the heuristic to guide exploration (ignoring path cost), A* balances both considerations. It evaluates each state using:

f(n) = g(n) + h(n)

Where:

  • g(n) = actual cost from start to node n (like Uniform-Cost Search tracks)
  • h(n) = heuristic estimate from n to goal (like Greedy Best-First uses)
  • f(n) = estimated total cost of the cheapest solution through n

Why This Works

Think of planning a road trip. Uniform-Cost Search picks the route that's gotten you farthest cheaply so far, ignoring where you're headed. Greedy Best-First picks whatever looks closest to your destination right now, ignoring how far you've already driven. A* considers both: how much you've spent getting here AND how much farther you likely need to go.

A* expands nodes from the frontier in order of increasing f(n). It always explores the most promising complete path first.

Optimality Guarantee

When your heuristic is admissible (never overestimates true cost) and consistent (satisfies the triangle inequality), A* guarantees finding the optimal solution. The heuristic guides search toward the goal while g(n) prevents shortcuts that looked good but actually cost more.

Key Takeaway: A* Search combines actual path cost g(n) and heuristic estimate h(n) to efficiently find optimal solutions by always expanding the node with lowest f(n) = g(n) + h(n).