A* looks simple until you implement it.
Then one question appears:
Why does this algorithm find good paths without checking every possible path?
The answer is its scoring structure.
A* does not only ask, “How far have I moved?”
It also asks, “How far do I probably still need to go?”
Core Idea
A* is a shortest-path search algorithm.
But it is not blind search.
It combines:
- the real cost so far
- the estimated cost to the goal
That combination makes A* useful in pathfinding, games, maps, robotics, and graph search problems.
The Key Structure
A* is built around one simple score:
f(n) = g(n) + h(n)
Where:
- g(n) = actual cost from the start node to node n
- h(n) = estimated cost from node n to the goal
- f(n) = total estimated path cost
So A* chooses the node with the lowest f(n).
Not the closest node.
Not the cheapest node so far.
The node that looks best overall.
Implementation View
At a high level, A* works like this:
start with the start node
put it into an open set
while the open set is not empty:
choose the node with the lowest f(n)
if this node is the goal:
return the path
expand its neighbors
for each neighbor:
calculate g(n)
estimate h(n)
update f(n) = g(n) + h(n)
if no path is found:
return failure
This is why the heuristic matters.
The heuristic controls where the search wants to go next.
A Concrete Example
Imagine a grid map.
You are moving from Start to Goal.
A normal search may expand many nearby cells.
A* gives every candidate cell a score.
Example:
Node A:
- g(n) = 4
- h(n) = 6
- f(n) = 10
Node B:
- g(n) = 7
- h(n) = 2
- f(n) = 9
Node B has a higher cost so far.
But it looks closer to the goal.
So A* may choose Node B first.
That is the core intuition.
A* does not only care about the past.
It also estimates the future.
Naive Search vs A*
Naive search explores broadly.
It does not know which direction is promising.
A* uses the heuristic to guide the search.
Naive search:
- checks many paths
- has no goal direction
- can waste work
A* search:
- uses goal direction
- prioritizes promising nodes
- can still guarantee the shortest path under the right conditions
That is why A* is so practical.
It is not just faster by accident.
It is faster because it has a better search priority.
Greedy Search vs A*
This is the comparison that makes A* clear.
Greedy Search uses only:
f(n) = h(n)
A* uses:
f(n) = g(n) + h(n)
Greedy Search asks:
“Which node looks closest to the goal?”
A* asks:
“Which node gives the best estimated total path?”
That difference is huge.
Greedy Search can move quickly.
But it can be fooled.
A* is more careful because it includes the real cost already paid.
Why Admissibility Matters
A* can guarantee the shortest path only when the heuristic behaves correctly.
The first important condition is admissibility.
A heuristic is admissible if it never overestimates the true remaining cost.
In simple terms:
h(n) must be less than or equal to the real cost to the goal.
If the heuristic overestimates, A* may skip the real shortest path.
That breaks optimality.
So admissibility keeps A* safe.
It lets the algorithm move efficiently without lying about the remaining cost.
Why Consistency Matters
Consistency is also called monotonicity.
It is a stronger and cleaner condition.
A heuristic is consistent if its estimates do not contradict the cost of moving between nodes.
The idea is simple:
As you move from one node to the next, the heuristic should change smoothly.
If consistency holds, A* behaves more predictably during expansion.
In many implementations, this means already processed nodes do not need to be reopened.
So:
- admissibility protects optimality
- consistency helps search behavior stay clean
They are related.
But they are not the same.
Recommended Learning Order
If you are learning A* for the first time, do not start with the conditions.
Start with the structure.
A good order is:
- A* Algorithm
- Heuristic Function
- Admissibility
- Monotonicity / Consistency
- Greedy Search comparison
- Informed Search as the broader category
This order avoids confusion.
You first understand what A* does.
Then you understand why the conditions matter.
Takeaway
A* is not just “search with a heuristic.”
It is a shortest-path strategy built around balance.
The formula is simple:
f(n) = g(n) + h(n)
But the meaning is powerful.
g(n) keeps track of what you already paid.
h(n) estimates what remains.
Together, they let A* search efficiently while still aiming for the optimal path.
If you remember one sentence, remember this:
A* finds shortest paths by combining actual cost so far with estimated cost still remaining.
Discussion
When you implement A*, do you usually use a simple heuristic like Manhattan distance, or do you design a custom heuristic for the problem domain?
Originally published at zeromathai.com.
Original article: https://zeromathai.com/en/a-star-algorithm-complete-hub-en/
Top comments (0)