The A* Algorithm

Overview

A* is a graph traversal and pathfinding algorithm widely used in computer science for finding the shortest path from a source node to a target node. It is an enhancement of Dijkstra's algorithm that incorporates heuristics to optimise the search process, making it more efficient in certain scenarios.

How A Algorithm Works*

• Inputs:

  • A weighted graph or grid.
  • A source node (start) and a target node (goal).

• Outputs:

  • The shortest path from the source to the target, if it exists. A* uses a combination of:

• g(n): The cost from the start node to the current node.

• h(n): A heuristic estimate of the cost from the current node to the target node.

• f(n) = g(n) + h(n): The total estimated cost of the cheapest path through the current node. Steps:

1. Initialise the open set (nodes to be evaluated) with the start node.
2. Track the costs and previous nodes for backtracking the path.
3. While the open set is not empty:

• Select the node with the lowest f(n) value.
• If this node is the target, reconstruct and return the path.
• Otherwise, evaluate its neighbours:
• Update g(n) for each neighbour.
• Recalculate f(n).
• If a shorter path to a neighbour is found, update it.
• Move the current node to the closed set (evaluated nodes).

4. Repeat until the target is reached or all nodes are evaluated.

Heuristic Function

The heuristic h(n) plays a critical role in guiding the algorithm:

Manhattan Distance: Used in grids where movement is restricted to horizontal and vertical.

$h(n) = |x_1 - x_2| + |y_1 - y_2|$

Euclidean Distance: Used when diagonal movement is allowed.

$h(n) = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$

The heuristic must be admissible (never overestimates the actual cost) and ideally consistent for optimal performance.

Pseudocode for A* Algorithm

METHOD AStar(graph, start, goal)
    openSet ← PRIORITY_QUEUE containing start
    cameFrom ← EMPTY_MAP
    gScore ← MAP with default value ∞
    gScore[start] ← 0
    fScore ← MAP with default value ∞
    fScore[start] ← heuristic(start, goal)

    WHILE openSet IS NOT EMPTY
        current ← node in openSet with lowest fScore
        IF current = goal
            RETURN ReconstructPath(cameFrom, current)

        REMOVE current FROM openSet
        FOR each neighbor of current
            tentative_gScore ← gScore[current] + distance(current, neighbor)
            IF tentative_gScore < gScore[neighbor]
                cameFrom[neighbor] ← current
                gScore[neighbor] ← tentative_gScore
                fScore[neighbor] ← gScore[neighbor] + heuristic(neighbor, goal)
                IF neighbor NOT IN openSet
                    ADD neighbor TO openSet
    RETURN "No Path Found"

Python Implementation

import heapq

def a_star(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]

    while open_set:
        _, current = heapq.heappop(open_set)

        if current == goal:
            return reconstruct_path(came_from, current)

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

    return "No Path Found"

def reconstruct_path(came_from, current):
    path = []
    while current in came_from:
        path.append(current)
        current = came_from[current]
    path.reverse()
    return path

Note Summary