A* (A-Star) Search Algorithm

In the previous lesson, we studied modern optimization techniques like ADAM and RMSProp, which intelligently guide learning.

Now we shift focus to a powerful search algorithm used in pathfinding, AI navigation, robotics, and games — the A* (A-Star) Search Algorithm.

A* is considered one of the most practical and efficient search algorithms ever designed.

Why Do We Need A* Search?

Simple search algorithms like BFS and DFS do not consider the actual cost of reaching a goal.

They either explore blindly or waste time searching unnecessary paths.

A* improves this by being both:

• Cost-aware
• Goal-directed

The Core Idea Behind A*

A* uses a smart evaluation function:

f(n) = g(n) + h(n)

Where:

• g(n) = actual cost from start to node n
• h(n) = estimated cost from n to goal (heuristic)

The algorithm always expands the node with the smallest estimated total cost.

Understanding the Heuristic (h)

The heuristic is the “intelligence” of A*.

It estimates how far a node is from the goal without actually exploring that path.

Common heuristics include:

• Manhattan distance
• Euclidean distance
• Straight-line distance

Real-World Example

Imagine using Google Maps.

The app does not try every road randomly. Instead, it estimates:

• Distance already traveled
• Estimated distance remaining

This is exactly how A* works.

High-Level Steps of A*

Conceptually, A* follows these steps:

1. Start from the initial node
2. Calculate f(n) for neighboring nodes
3. Choose the node with the lowest f(n)
4. Repeat until the goal is reached

Pseudocode for A*

open_set = {start}
g[start] = 0
f[start] = h(start)

while open_set is not empty:
    current = node with lowest f in open_set

    if current is goal:
        return path

    remove current from open_set

    for each neighbor of current:
        tentative_g = g[current] + cost(current, neighbor)

        if tentative_g < g[neighbor]:
            parent[neighbor] = current
            g[neighbor] = tentative_g
            f[neighbor] = g[neighbor] + h(neighbor)
            add neighbor to open_set

Why A* Is Optimal

If the heuristic function never overestimates the true cost, A* guarantees the shortest path.

Such heuristics are called admissible heuristics.

Where A* Is Used

A* is widely used in:

• Video game pathfinding
• Robot navigation
• GPS and map routing
• AI planning systems

Exercises

Quick Quiz

In the next lesson, we will explore Uniform Cost Search and compare it directly with A*.