Discrete Mathsfor Engineers

4. Optimality & Complexity

A* is not only a practical search algorithm, but also one with strong theoretical guarantees.

These guarantees depend directly on the properties of the heuristic and the structure of the search space.

4.1 What Optimality Means

A* is optimal if it always returns a path of minimum cost from the start node to the goal.

If C* is the optimal path cost, then the solution returned by A* has cost C*.

The key question is: under what conditions is this guaranteed?

4.2 Admissibility

A heuristic is admissible if it never overestimates the true remaining cost.

This ensures that f(n) = g(n) + h(n) is never an optimistic underestimate of the true solution cost.

With admissible heuristics, A* (in tree search) is guaranteed to find an optimal solution.

4.3 Consistency

Consistency is a stronger condition than admissibility.

for every edge (n, n').

This enforces a triangle-inequality-like property over the heuristic.

With consistency, the values of f(n) are non-decreasing along paths.

4.4 Tree Search vs Graph Search

In tree search, states may be revisited multiple times.

In graph search, a closed set is used to prevent redundant expansions.

Consistency ensures that once a node is expanded with minimal f, its optimal cost has already been found.

4.5 Completeness

A* is also complete under standard assumptions.

This means that if a solution exists, the algorithm will eventually find it.

This typically holds in finite graphs with positive edge costs.

4.6 Time Complexity

In the worst case, A* may explore an exponential number of nodes.

Thus, worst-case time complexity remains exponential in the depth of the solution.

However, good heuristics drastically reduce the number of explored states in practice.

4.7 Space Complexity

A* has significant memory requirements.

It stores the frontier, costs, predecessors, and often the explored set.

Therefore, space complexity is also typically exponential.

4.8 Heuristic Quality

The efficiency of A* depends heavily on how informative the heuristic is.

• weak heuristic → more exploration
• strong heuristic → less exploration

Ideally, the heuristic should be as close as possible to the true cost while remaining admissible.

4.9 Extreme Cases

• h(n) = 0 → A* becomes Dijkstra
• h(n) = h*(n) → perfect heuristic

These cases illustrate the spectrum between uninformed and perfectly informed search.