Informed (Heuristic) Search and the A* Algorithm in AI

While uninformed search algorithms stumble blindly through state spaces without knowing if a step brings them closer to the destination, Informed Search (also known as Heuristic Search) incorporates problem-specific knowledge via a mathematical heuristic evaluation function ( h(n) ). This guides the agent toward the goal with vastly superior computational efficiency.

Figure 5.1: The A* Search Frontier — Evaluating ( f(n) = g(n) + h(n) ) to guarantee complete, optimal pathfinding with minimal node expansions.

What is a Heuristic Function ( h(n) )?

A heuristic function ( h(n) ) estimates the cheapest path cost from state ( n ) to the nearest goal state:

• ( h(n) ge 0 ) for all valid states.
• If ( n ) is already a goal state, then ( h(n) = 0 ).
• ( h(n) ) is calculated quickly without performing an exhaustive search.

1. Greedy Best-First Search

Greedy Best-First Search expands the node that appears closest to the goal according to the heuristic alone: ( f(n) = h(n) ). It uses a priority queue ordered strictly by ascending ( h(n) ).

Limitations: Like Depth-First Search, greedy search can be easily fooled by false leads. Because it completely ignores the backward accumulated cost ( g(n) ), it is neither complete on graph cycles nor optimal. A straight-line distance heuristic may lead an agent straight into a dead-end cliff.

2. The A* Search Algorithm: ( f(n) = g(n) + h(n) )

Formulated in 1968 by Peter Hart, Nils Nilsson, and Bertram Raphael, the A* Algorithm is the most widely celebrated search algorithm in computer science and artificial intelligence. A* evaluates nodes by combining the actual cost to reach the node with the estimated cost to reach the goal:

Conditions for A* Optimality: Admissibility & Consistency

For A* to guarantee finding the optimal (lowest-cost) path, the heuristic ( h(n) ) must satisfy two formal mathematical properties:

1. Admissibility (Required for Tree Search A*)

An admissible heuristic is one that never overestimates the true cost to reach the goal. Formally, for every node ( n ):

Because an admissible heuristic is optimistic, A* will never overlook a promising path in favor of a path that appears deceptively cheap.

2. Consistency / Monotonicity (Required for Graph Search A*)

When searching graphs (where states can be reached via multiple paths), A* requires a stronger condition called consistency (or monotonicity). A heuristic ( h(n) ) is consistent if, for every node ( n ) and every successor ( n' ) generated by action ( a ):

Key Consequence: If ( h(n) ) is consistent, the values of ( f(n) ) along any path never decrease. Furthermore, the first time A* expands any node, the path to that node is guaranteed to be optimal; we never need to re-open nodes in the closed/explored set!

Classic Heuristics: The 8-Puzzle Problem

In the classical 8-puzzle game (sliding tiles on a 3x3 grid to match a goal configuration), two standard admissible heuristics are used:

1. ( h_1 ) (Misplaced Tiles): The number of tiles that are not in their goal position. Admissible because each misplaced tile must move at least once.
2. ( h_2 ) (Manhattan / City-Block Distance): The sum of vertical and horizontal distances each tile is from its goal position: ( |x_1 - x_2| + |y_1 - y_2| ).

Heuristic Dominance: Notice that for any state ( n ), ( h_2(n) ge h_1(n) ). We say that ( h_2 ) dominates ( h_1 ). A dominating heuristic is always superior because its estimates are closer to the true cost ( h^* ), causing A* to expand significantly fewer nodes.

import heapq

# Roadmap with edge costs: g(n)
road_graph = {
    'Arad': {'Zerind': 75, 'Sibiu': 140, 'Timisoara': 118},
    'Zerind': {'Arad': 75, 'Oradea': 71},
    'Oradea': {'Zerind': 71, 'Sibiu': 151},
    'Sibiu': {'Arad': 140, 'Oradea': 151, 'Fagaras': 99, 'Rimnicu Vilcea': 80},
    'Timisoara': {'Arad': 118, 'Lugoj': 111},
    'Lugoj': {'Timisoara': 111, 'Mehadia': 70},
    'Mehadia': {'Lugoj': 70, 'Drobeta': 75},
    'Drobeta': {'Mehadia': 75, 'Craiova': 120},
    'Craiova': {'Drobeta': 120, 'Rimnicu Vilcea': 146, 'Pitesti': 138},
    'Rimnicu Vilcea': {'Sibiu': 80, 'Craiova': 146, 'Pitesti': 97},
    'Fagaras': {'Sibiu': 99, 'Bucharest': 211},
    'Pitesti': {'Rimnicu Vilcea': 97, 'Craiova': 138, 'Bucharest': 101},
    'Bucharest': {'Fagaras': 211, 'Pitesti': 101}
}

# Straight-line distance heuristic to Bucharest: h(n)
h_bucharest = {
    'Arad': 366, 'Zerind': 374, 'Oradea': 380, 'Sibiu': 253,
    'Timisoara': 329, 'Lugoj': 244, 'Mehadia': 241, 'Drobeta': 242,
    'Craiova': 160, 'Rimnicu Vilcea': 193, 'Fagaras': 176,
    'Pitesti': 100, 'Bucharest': 0
}

def a_star_search(start, goal):
    # Priority Queue stores tuples: (f_score, g_cost, current_node, path)
    frontier = []
    heapq.heappush(frontier, (h_bucharest[start], 0, start, [start]))
    lowest_g_cost = {start: 0}

    while frontier:
        f, g, current, path = heapq.pop(frontier)

        if current == goal:
            return path, g

        for neighbor, step_cost in road_graph[current].items():
            new_g = g + step_cost
            if neighbor not in lowest_g_cost or new_g < lowest_g_cost[neighbor]:
                lowest_g_cost[neighbor] = new_g
                f_score = new_g + h_bucharest[neighbor]
                heapq.heappush(frontier, (f_score, new_g, neighbor, path + [neighbor]))
    return None, float('inf')

optimal_path, total_km = a_star_search('Arad', 'Bucharest')
print(f"A* Optimal Route: {' -> '.join(optimal_path)}")
print(f"Total Optimal Driving Distance: {total_km} km")