A Comprehensive Guide to the A* Search Algorithm

6 min readApr 10, 2024

Introduction:

In the realm of computer science and artificial intelligence, algorithms play a pivotal role in solving complex problems efficiently. One such algorithm that has garnered widespread attention and admiration is the A* search algorithm. Developed in the late 1960s by Peter Hart, Nils Nilsson, and Bertram Raphael, A* has become a cornerstone in pathfinding and optimization tasks. In this article, we delve into the intricacies of the A* search algorithm, exploring its principles, applications, and underlying mechanics.

The A* search algorithm is a widely-used pathfinding method designed to determine the shortest path between a starting point (source) and a destination (target) within a weighted graph. Unlike some other algorithms, A* considers both the actual cost incurred from the starting point to the current node (referred to as “g”), as well as an estimation of the cost required to reach the target node from the current node (known as “h”). By combining these values, A* calculates an overall score (“f”) for each node, with the goal of selecting the node with the lowest f-value as the next step in the pathfinding process. This process continues iteratively until the target node is reached.

It’s worth noting that Dijkstra’s algorithm, a precursor to A*, can be seen as a special case of A* where the heuristic value (h) is set to zero for all nodes. This effectively reduces the A* algorithm to Dijkstra’s approach, prioritizing only the actual cost (g) in the pathfinding process without considering any estimation of future costs.

Understanding the Basics: At its core, the A* search algorithm is a pathfinding algorithm that aims to find the shortest path between two nodes in a graph, while considering both the cost of reaching each node and an estimate of the remaining distance to the goal. This heuristic approach distinguishes A* from other search algorithms, making it particularly efficient in navigating through complex environments.

Key Components:

Nodes and Edges: In A*, the problem space is represented as a graph consisting of interconnected nodes (vertices) and edges (connections between nodes). Each node represents a state or a point in the search space, while edges denote the possible transitions between states.
Heuristic Function: A* relies on a heuristic function, denoted as h(n), which provides an estimate of the cost from a given node to the goal node. This heuristic guides the search process by prioritizing nodes that are closer to the goal, thereby reducing the overall search time.
Cost Functions: Additionally, A* considers two cost functions: g(n), the actual cost of reaching a particular node from the start node, and f(n), the sum of g(n) and h(n). The latter serves as the evaluation function, determining the priority of nodes in the search process.

How this A*Algorithm works ?

The A* algorithm operates by leveraging two key functions: g(n) and h(n). Let’s consider a scenario where we find ourselves at a particular node, denoted as n. The function g(n) provides us with the actual cost incurred from the start node to the current node n. On the other hand, h(n) serves as a heuristic function, offering an estimate of the cost required to reach the target node from the current node n. This estimation is essential for guiding the algorithm towards the goal efficiently.

f(n) = g(n) + h(n)f(n): the estimate of the total cost from start node to target node through node n
g(n): actual cost from start node to node n
h(n): estimated cost from node n to target node

In essence, h(n) represents an educated guess, and its accuracy significantly influences the performance of the A* algorithm. By combining the actual cost (g(n)) and the heuristic estimate (h(n)), we calculate the total cost of reaching the target node from the start node, denoted as f(n). This total cost estimation, f(n), guides the algorithm in selecting the most promising nodes to explore further, ultimately facilitating the determination of the optimal path from the start node to the end node.

Graphical Explanation
Heuristic is crucial to the performance of A* algorithm. The heuristic function we use here just for the demo purpose.

Graph example :

Step 1
- a: Set the distance to the start node itself to 0 and the distance to all other nodes to infinity.
- b: Calculate the f value for the start node and set the previous node to none/nil/null.
- c: Initialize an open list and close list which are empty initially.

Step 2: Place the start node into the open list

Step 3
- a: Find the node with the minimum f-value in the open list and removed from the list. Denote this node as the current node.
- b: Check if the current node is the target node or not
- c: Populate all the current node’s neighboring nodes and do following checks for each neighboring nodes.
- d: Place the current node to the close list because we have expanded this node.

1. Is the neighboring node in the close list?
   - Yes. Skip this node.
   - No. Go to 2.2. Calculate g value for the neighboring node and check if a better  
   path(lower g value) is found?
   - No, Skip this node
   - Yes. Go to 3.3. Calculate g, h and f value for the neighboring node and set  
   the previous node to the current node4. Check if the neighbor node in the open list?
   - Yes. Update g, h and f value of the neighboring node in the  
     open list
   - No. Insert this neighboring node to the open list

Step 4: Repeat Step 3 until reaches the target node

Demo Iteration - 1

Demo Iteration-2

Demo Iteration-3

Demo Iteration-4

Demo Iteration-5

Final Result

At the end, we can backtrack the shortest path using the previous node. In this demo, we use A* algorithm to search the shortest path without necessarily search all the graph.(We haven’t examined node 4 yet, so you can see the node 4 is till on the open list). Unlike Dijkstra’s algorithm, it has to expand all the nodes in the graph.