DEV Community

shangkyu shin
shangkyu shin

Posted on • Originally published at zeromathai.com

Why A* Search Works — Heuristics, Shortest Paths, and Optimality

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
Enter fullscreen mode Exit fullscreen mode

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:

  1. A* Algorithm
  2. Heuristic Function
  3. Admissibility
  4. Monotonicity / Consistency
  5. Greedy Search comparison
  6. 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)