A* Search Algorithm - Detailed Explanation with Python Example

 What is A* Search Algorithm?

A* Search (pronounced "A-star") is one of the most popular and powerful pathfinding and graph traversal algorithms. It finds the shortest path between nodes using both the cost to reach a node and a heuristic estimation of the remaining cost to the goal.

Key Concepts

• g(n): The actual cost from the start node to the current node $n$.
• h(n): The heuristic estimated cost from node $n$ to the goal.
• f(n): The total estimated cost of the cheapest solution through node $n$, calculated as:$f(n) = g(n) + h(n)$

A* Algorithm Steps

1. Initialize the open set with the start node.
2. Initialize a map to record the lowest cost to reach each node ($g$ value).
3. While the open set is not empty:
   • Pick the node with the lowest $f(n)$ value.
   • If the node is the goal, reconstruct and return the path.
   • Else, for each neighbor:
     • Calculate tentative $g$ score.
     • If this score is better than previously recorded, update it.
     • Set neighbor's parent to the current node.
     • If the neighbor is not in the open set, add it.

Python Example Code

import heapq

def a_star_search(graph, start, goal, heuristic):
    open_set = []
    heapq.heappush(open_set, (0, start))
    
    came_from = {}
    g_score = {node: float('inf') for node in graph}
    g_score[start] = 0

    f_score = {node: float('inf') for node in graph}
    f_score[start] = heuristic(start, goal)

    while open_set:
        current = heapq.heappop(open_set)[1]

        if current == goal:
            path = []
            while current in came_from:
                path.append(current)
                current = came_from[current]
            path.append(start)
            return path[::-1]

        for neighbor, cost in graph[current]:
            tentative_g_score = g_score[current] + cost
            if tentative_g_score < g_score[neighbor]:
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g_score
                f_score[neighbor] = tentative_g_score + heuristic(neighbor, goal)
                heapq.heappush(open_set, (f_score[neighbor], neighbor))

    return None

# Example heuristic: straight-line distance (mocked)
def heuristic(n, goal):
    h_values = {
        'A': 6, 'B': 4, 'C': 4, 'D': 2, 'E': 0
    }
    return h_values.get(n, 0)

# Example graph
graph = {
    'A': [('B', 1), ('C', 3)],
    'B': [('D', 1)],
    'C': [('D', 1), ('E', 5)],
    'D': [('E', 2)],
    'E': []
}

# Usage
path = a_star_search(graph, 'A', 'E', heuristic)
print("Path found:", path)

Output:

Path found: ['A', 'B', 'D', 'E']

Complexity Analysis

Time Complexity

• In the worst case (when the heuristic function is poor), the time complexity can degrade to that of Dijkstra's Algorithm:$O((V + E) \log V)$ where $V$ is the number of vertices and $E$ is the number of edges.
• If the heuristic is perfect (always estimates the real cost exactly), A* can explore only the optimal path.

Space Complexity

• Similar to the time complexity, A* stores all generated nodes in memory, so space complexity is:$O(V)$

Best, Average, and Worst Cases

• Best Case: When $h(n)$ exactly predicts the true cost. Only optimal nodes are expanded.
• Average Case: A reasonably good heuristic reduces unnecessary exploration.
• Worst Case: A poor heuristic behaves like Uniform Cost Search (no pruning).

Conclusion

A* Search is widely used in AI, robotics, and game development due to its balance between optimality and efficiency. Choosing a good heuristic function is critical to unlocking A*'s full potential.

References

• Wikipedia - A* Search Algorithm
• GeeksforGeeks - A* Search Algorithm