Discrete Mathsfor Engineers

3. The A* Algorithm

Once the problem model and heuristic function are defined, the next step is to understand how A* actually executes the search.

At its core, A* repeatedly selects the most promising node, expands it, and updates the frontier using exact costs and heuristic estimates.

3.1 Frontier and Explored States

A* maintains two conceptual sets during execution:

• open set: nodes discovered but not yet fully explored
• closed set: nodes already expanded

The open set stores the current frontier of the search.

The closed set prevents redundant expansion of states already processed.

3.2 Node Selection Rule

At each step, A* selects the node with minimum value of f(n) = g(n) + h(n).

This choice balances the exact path cost accumulated so far with the estimated cost remaining to the goal.

In practice, this is usually implemented with a priority queue.

3.3 Expanding a Node

When a node is expanded, the algorithm examines all its outgoing neighbors.

For each neighbor, A* computes a tentative new cost:

This represents the cost of reaching neighbor m through the current node n.

3.4 Updating a Neighbor

If the new path to a neighbor is better than any previously known path, the algorithm updates:

• its parent reference
• its value of g(n)
• its value of f(n)

The node is then inserted into the open set or reprioritized if it was already there.

3.5 Goal Detection

The search stops when the goal node is selected for expansion.

At that point, the optimal path can be reconstructed by following parent pointers backward from the goal to the start.

Path reconstruction is therefore a backward traversal over predecessor references.

3.6 Canonical A* Template

The generic structure of A* can be written as follows:

A*(start, goal):

    open_set = priority queue ordered by f
    closed_set = empty set

    g(start) = 0
    f(start) = h(start)
    insert start into open_set

    while open_set is not empty:

        n = extract node with minimum f

        if n is goal:
            return reconstructed path

        move n to closed_set

        for each neighbor m of n:

            tentative_g = g(n) + c(n, m)

            if m is in closed_set and tentative_g is not better:
                continue

            if m is new or tentative_g is better:
                parent(m) = n
                g(m) = tentative_g
                f(m) = g(m) + h(m)

                insert or update m in open_set

    return failure

3.7 Why a Priority Queue Matters

The efficiency of A* depends strongly on how the open set is managed.

Since the algorithm repeatedly extracts the node with minimum estimated total cost, the natural data structure is a min-priority queue.

• binary heap
• Fibonacci heap
• other efficient priority structures

3.8 Operational Summary

The algorithm alternates between three operations:

• select the most promising frontier node
• expand its neighbors
• update costs and predecessor structure

This process continues until the goal is reached or the frontier becomes empty.