Discrete Mathsfor Engineers

4. Optimality & Complexity

IDA* is attractive because it combines heuristic guidance with a memory-efficient depth-first strategy.

However, these benefits come with theoretical conditions and computational trade-offs that must be understood clearly.

4.1 What Optimality Means

IDA* is optimal if it returns a minimum-cost solution whenever one exists.

If C* denotes the optimal solution cost, then the path returned by IDA* must also have cost C*.

The main question is under what conditions this guarantee holds.

4.2 Admissible Heuristics

The correctness of IDA* depends fundamentally on the heuristic not overestimating the remaining cost.

This means the heuristic is admissible.

With an admissible heuristic, the threshold sequence progresses in a way that does not skip the optimal solution cost.

4.3 Why Threshold Progression Works

In each iteration, IDA* explores all nodes whose estimated total cost satisfies the current threshold.

If no solution is found, the next threshold becomes the smallest exceeded f-value.

Because thresholds increase in this disciplined way, the optimal cost layer is eventually reached.

4.4 Completeness

IDA* is also complete under the usual assumptions for state-space search.

If a solution exists, edge costs are positive, and the branching process is well-behaved, the algorithm will eventually find a solution.

This property is important because optimality is meaningful only if the search is guaranteed to terminate successfully whenever a solution exists.

4.5 Time Complexity

In the worst case, IDA* may still require exponential time.

Its worst-case time complexity is exponential in the depth of the optimal solution.

This happens because the algorithm may revisit the same states many times across successive thresholds.

4.6 Re-expansion Overhead

The main source of extra work in IDA* is repeated re-expansion of prefixes.

Nodes that lie near the root of the search tree may be generated again in many iterations.

This is the computational price paid for avoiding a large stored frontier.

4.7 Space Complexity

The major strength of IDA* is its memory usage.

Because the search is depth-first, the algorithm stores mainly the current path and a small amount of additional information.

Space complexity is therefore typically linear in the search depth.

4.8 Influence of Heuristic Quality

Just as in A*, better heuristics improve performance.

• weak heuristic → more iterations and more re-expansion
• strong heuristic → fewer thresholds and less redundant work

A more informative admissible heuristic can significantly reduce practical running time.

4.9 IDA* vs A*: The Core Trade-off

A* reduces re-expansion by storing a large frontier in memory.

IDA* reduces memory consumption by accepting repeated search effort.

In short: A* saves time using memory, while IDA* saves memory using time.

4.10 Extreme Cases

• h(n) = 0 → IDA* behaves like iterative deepening on path cost
• h(n) = h*(n) → threshold progression becomes highly efficient

These cases illustrate how heuristic accuracy directly affects the amount of repeated work.