Search Algorithm — A* Search, with Python

Exploring A* Heuristic Search with Hands-On Python Examples

Photo by Arto Marttinen on Unsplash

*A Search (A-star) is a widely used and highly effective algorithm for finding the shortest path in a graph. It is popular because it combines efficiency, accuracy, and conceptual simplicity**.

Whether you are learning algorithms, preparing for technical interviews, or building navigation and optimization systems, A* is one of the most important search techniques to understand.

This article explains the intuition behind A*, its relationship with classical search algorithms, and demonstrates a practical Python implementation using the Romania map problem.

Background: Where A* Comes From

A* Search is built by combining two classical search strategies:

1. Uniform-Cost Search (UCS)

Uniform-Cost Search uses the path-cost function g(n), which represents the cost accumulated so far to reach node n (past experience).

• Optimal and complete, i.e., always finds the best solution if one exists.
• However, it can be inefficient, as it explores widely without guidance.

2. Greedy Best-First Search (GBFS)

Greedy Best-First Search uses a heuristic function h(n), which estimates the cost from node n to the goal (future prediction).

• Fast and space-efficient, as it prioritizes nodes closer to the goal
• However, it is neither optimal nor complete, and may lead to dead ends or suboptimal paths

A* Search: Combining Both Approaches

A* combines the strengths of both methods by using: f(n) = g(n) + h(n)

where:

• g(n) = cost from start to current node (past)
• h(n) = estimated cost to goal (future)
• f(n) = estimated total cost of the full path through n

At each step, A expands the node with the lowest f(n), balancing actual cost and estimated future cost. A can also be viewed as a best-first search algorithm guided by the evaluation function f(n).

Special cases:

• If g(n) = 0, A* reduces to Greedy Best-First Search
• If h(n) = 0, A* reduces to Uniform-Cost Search

Optimality conditions

A* guarantees the optimal path as long as the heuristic satisfies two conditions:

• Admissible: never overestimates the true cost to reach the goal
• Consistent (monotonic): ensures the estimated cost does not decrease along a path, avoiding unnecessary node re-expansion

Route Finding using A*

This article demonstrates the *A algorithm using the classic Romania map example, the same scenario previously used to illustrate Greedy Best-First Search**, as shown in Image 1.

• Each city represents a node.
• Roads are weighted edges (distance in km).
• A heuristic function h(n) estimates the straight-line distance from each city to the goal city, Bucharest.

Image 1. Romania map example with path cost g(n) in km (Russell & Norvig, 2016, p. 68).

Image 2. h(n) straight line / estimated distance from each city to Bucharest (Russell & Norvig, 2016, p. 93).

A* evaluates nodes using both travel cost and estimated remaining distance, ensuring efficient and optimal path selection. This balanced approach guides the search efficiently toward the destination while still considering the cost already incurred, often leading to an optimal path more effectively than purely uninformed or heuristic-only searches.

Image 3. Stages in an A search for Bucharest from Arad. Nodes are labeled with f(n) = g(n) + h(n). (Russell & Norvig, 2016, p. 96).*

Step-by-Step Example: Starting from Arad

Evaluate neighbors using the evaluation function f(n)=g(n)+h(n).

[embed]

[embed]Choose Sibiu (lowest f = 393)

[embed]Choose Rimnicu Vilcea (lowest f = 413) and Arad is visited neighbor city. Table by Author.

[embed]Choose Fagaras (lowest f = 415) and Sibiu is visited neighbor city. Table by Author.

[embed]Choose Pitesti (f = 417) and Sibiu is visited neighbor city. Table by Author.

[embed]Choose Bucharest (f = 418) and the goal is reach. Table by Author.

The path selected by A* algorithm is Arad → Sibiu → Rimnicu Vilcea → Pitesti → Bucharest.

In this case:

• The A* path Arad → Sibiu → Rimnicu Vilcea → Pitesti → Bucharest has a total cost of g(n) = 418 km.
• A more intuitive but costlier route, such as Arad → Sibiu → Fagaras → Bucharest, has a total cost of g(n) = 450 km.

Although Fagaras appears more attractive early because of a lower heuristic value h(n), A eventually discovers that taking Rimnicu Vilcea and Pitesti yields a cheaper overall route. This shows how A corrects early heuristic bias by continuously accounting for accumulated cost.

The difference between the two routes is 32 km, demonstrating that A* successfully avoids locally attractive but globally suboptimal choices.

Now, let’s evaluate this algorithm:

1. Time and Space Complexity: O(bᵐ), m is the maximum depth of the search space
2. Completeness: Does it always find a solution if one exists? Yes — A* is complete.
3. Optimality: Does it always find the best (least-cost) solution? Yes — A* is optimal with an admissible and consistent heuristic.

Code Implementation

Let’s use the above example to implement the A* algorithm using Python.

1. Creating a function that takes in weighted edges of the GRAPH, which outputs the undirected weighted graph

[embed]

The output of the code. Image by Author.

2. This function performs A search using the graph, heuristic values, starting vertex, and destination vertex. It explores nodes based on the smallest f(n) = g(n) + h (n), where g(n) is the path cost and h(n) is the heuristic estimate. The algorithm updates the frontier with better paths when found and continues until the goal is reached. A guarantees an optimal solution when the heuristic is admissible and consistent.

[embed]

The output of the code. Image by Author.

Conclusion

A* Search is an informed search algorithm that evaluates nodes using f(n)=g(n)+h(n), combining actual cost and heuristic estimation. This allows it to efficiently guide the search while still considering the true path cost.

Unlike Greedy Best-First Search, A* is both complete and optimal, provided the heuristic is admissible and consistent. As a result, it guarantees the shortest path while still being efficient in practice.

Although it may require more computation than heuristic-only methods, A* is widely used due to its reliability and optimality, making it a fundamental algorithm in pathfinding and AI search problems.

Recommended Reading

[embed]Search Algorithm — Breadth-first search, with Python Python Implementation from scratchmedium.com

[embed]Search Algorithm — Depth-first search, with Python Python implementation from scratchmedium.com

[embed]Search Algorithm — Dijkstra’s Algorithm & Uniform Cost Search, with Python Introducing one of the foundational search algorithms called Dijkstra’s Algorithm and a variant of it, Uniform-Cost…medium.com

[embed]Search Algorithm - Greedy Best-First Search, with Python Search Algorithm - Greedy Best-First Search, with Python Exploring Heuristic-Driven Search with Greedy Best-First…levelup.gitconnected.com

Reference

[1] Russell, S. J., Norvig, P. (2016). Artificial Intelligence: A Modern Approach. England: Pearson Education. ISBN: 9781292153964