Q19Principles of Artificial Intelligence

A is the absolute pinnacle of informed pathfinding algorithms. Breadth-First Search is blind. Greedy Best-First Search is fast but mathematically flawed (it gets trapped). A aggressively merges the absolute optimality of Dijkstra's Algorithm (tracking past costs) with the explosive speed of Greedy Search (predicting future costs) to violently navigate massive state-space graphs.

At every node, A* calculates a strict mathematical score: $$f(n)=g(n)+h(n)$$

• $g(n)$: The exact, absolute physical cost to travel from the Start node to the current Node $n$. (Known data).
• $h(n)$ (The Heuristic): The mathematically estimated cost to travel from Node $n$ to the final Goal. (Predicted data).
• $f(n)$: The estimated total cost of the absolute cheapest solution path that physically passes through Node $n$.

The algorithm maintains an "Open List" (a priority queue) of discovered nodes, violently sorting them by $f(n)$. It always pops and expands the node with the absolute lowest $f(n)$ score.

A* is mathematically guaranteed to find the absolute shortest path (Optimal) and guaranteed to find a path if one exists (Complete), strictly under one condition: The Heuristic function $h(n)$ must be Admissible.

What is an Admissible Heuristic?

An admissible heuristic NEVER mathematically overestimates the true cost to reach the goal. $h(n)\le h^{\ast }(n)$ (where $h^{\ast }$ is the actual physical true cost).

Example: In a maze, a straight Euclidean line between $n$ and the Goal is perfectly admissible because the true physical path (dodging walls) will always be mathematically greater than or equal to the straight line. It is physically impossible to travel shorter than a straight line.

The Mathematical Proof of Optimality

Assume A* is flawed and it selects a suboptimal Goal $G_2$ instead of the true optimal Goal $G_1$.

• Because $G_2$ is suboptimal, its true cost is higher: $f(G_2)>f(G_1)$.
• Because $G_2$ is a Goal node, its heuristic is zero: $h(G_2)=0$. Thus, $f(G_2)=g(G_2)$.
• Consider a node $n$ that is currently on the Open List and is physically on the correct path to $G_1$.
• Because $h(n)$ is Admissible, it does not overestimate. Therefore: $f(n)=g(n)+h(n)\le f(G_1)$.
• Since we established $f(G_1)<f(G_2)$, it mathematically proves that $f(n)<f(G_2)$.

The Contradiction: A always expands the node with the absolute lowest $f$ score. Therefore, A will mathematically be forced to expand node $n$ BEFORE it is ever allowed to expand the suboptimal goal $G_2$. A will relentlessly follow $n$ all the way to $G_1$. It is mathematically impossible for A to terminate on a suboptimal goal if $h(n)$ is admissible.