A Star

The A* algorithm is an extension of Dijkstra’s Algorithm designed to find the shortest path in a graph while using a heuristic to prioritize exploration. It is widely used in navigation systems, games, and robotics for pathfinding.

Key Concepts

1. Cost Function: A* minimizes the cost function: $f(n)=g(n)+h(n)$
   • $g(n)$: The actual cost from the start node to node $n$ (like Dijkstra’s).
   • $h(n)$: The heuristic estimate of the cost from $n$ to the goal.
2. Heuristic:
   • A* uses $h(n)$ to estimate the remaining cost to the goal.
   • $h(n)$ must be admissible (never overestimates the true cost) to guarantee optimality.
   • Examples:
     • Euclidean distance: For geometric graphs in a plane.
     • Manhattan distance: For grid-based systems with horizontal/vertical movement.
3. Priority Queue:
   • Nodes are prioritized by their $f(n)$ value, guiding the search towards the goal.

---

Steps of the Algorithm

1. Initialization:

   • Set $g(\text{start})=0$.
   • Add the start node to the priority queue with $f(\text{start})=h(\text{start})$.

2. Processing Nodes:

   • While the queue is not empty:
     • Pop the node with the lowest $f(n)$ value.
     • If it’s the goal node, return the path.
     • For each neighbor:
       • Compute $g(\text{neighbor})=g(\text{current})+\text{edge cost}$.
       • Update $f(\text{neighbor})$ and add it to the queue if this path is better.

3. Termination:

   • Stop when the goal node is reached or the queue is empty.

---

Python Implementation

import heapq
 
def a_star(graph, start, goal, heuristic):
    priority_queue = []
    heapq.heappush(priority_queue, (0, start))
    
    g_scores = {node: float('inf') for node in graph}
    g_scores[start] = 0
    
    came_from = {}
    
    while priority_queue:
        current_f_score, current = heapq.heappop(priority_queue)
        
        if current == goal:
            return reconstruct_path(came_from, current)
        
        for neighbor, weight in graph[current].items():
            tentative_g_score = g_scores[current] + weight
            if tentative_g_score < g_scores[neighbor]:
                came_from[neighbor] = current
                g_scores[neighbor] = tentative_g_score
                f_score = tentative_g_score + heuristic(neighbor, goal)
                heapq.heappush(priority_queue, (f_score, neighbor))
    
    return None
 
def reconstruct_path(came_from, current):
    path = [current]
    while current in came_from:
        current = came_from[current]
        path.append(current)
    return path[::-1]

---

Comparison with Dijkstra on an example

Without Heuristic Dijkstra’s Algorithm

• ( h(n) = 0 ) for all nodes (no guidance).
• The algorithm relies only on ( g(n) ) (actual cost so far). Steps:

1. Start at A: ( f(A) = g(A) = 0 ).
2. Explore neighbors: B (f = 1), C (f = 4). Pick B.
3. From B: Explore C (f = 3) and D (f = 7). Pick C.
4. From C: Explore D (f = 6). Pick D. Result:

Explored order: A → B → C → D
Path: A → B → C → D

---

With Heuristic (A*)

• ( h(n) ) guides the search:

  h(A) = 7, h(B) = 6, h(C) = 2, h(D) = 0

Steps:

1. Start at A: ( f(A) = g(A) + h(A) = 0 + 7 = 7 ).
2. Explore neighbors: B (f = 1 + 6 = 7), C (f = 4 + 2 = 6). Pick C first (lowest ( f )).
3. From C: Explore D (f = 6 + 0 = 6). Pick D. Result:

Explored order: A → C → D
Path: A → C → D

---

Key Difference:

• Without heuristic: Explores all possible paths, guided only by ( g(n) ).
• With heuristic: Prioritizes nodes closer to the goal (( h(n) )), reducing exploration.

Comparison to Dijkstra

Feature	Dijkstra	A*
Cost Function	$f(n)=g(n)$	$f(n)=g(n)+h(n)$
Heuristic	Not used	Guides the search
Search Scope	Explores all possible paths	Focuses on promising paths
Use Case	Weighted graphs, no heuristic	Shortest path with heuristic