Discrete Mathsfor Engineers

2. Cost Threshold & Iterative Deepening

The central idea of IDA* is to replace A*’s global priority-based frontier with repeated depth-first searches bounded by cost.

Instead of storing all frontier nodes, the algorithm explores only paths whose estimated total cost remains within a current threshold.

2.1 The Meaning of the Threshold

In IDA*, each iteration is controlled by a scalar bound called the cost threshold.

A node n is expanded only if f(n) = g(n) + h(n) ≤ T, where T is the current threshold.

Thus, the threshold determines which part of the search space is accessible in the current iteration.

2.2 Cost-Based Pruning

Whenever the estimated total cost of a node exceeds the threshold, the branch is cut immediately.

This pruning rule makes the search selective without requiring a global ordering of all frontier nodes.

Nodes are not discarded forever; they may be reconsidered in later iterations with larger thresholds.

2.3 Initial Threshold

The first threshold is usually chosen as the evaluation of the start state.

Since the initial accumulated cost is zero, this is equivalent to:

The search then begins with the smallest meaningful cost bound.

2.4 One Iteration of IDA*

For a fixed threshold, IDA* performs a depth-first traversal of the search space.

During this traversal:

• nodes within the threshold are explored recursively
• nodes beyond the threshold are pruned
• the smallest exceeded value is recorded

If the goal is not found, that smallest exceeded value becomes the next threshold.

2.5 Updating the Threshold

IDA* does not increase the threshold arbitrarily.

The next threshold is chosen as the minimum value of f(n) among all pruned nodes in the current iteration.

This makes the increase as small as possible while guaranteeing progress.

2.6 Why Repeated Search Is Necessary

Because the threshold restricts exploration, a single depth-first pass is not enough in general.

Some relevant nodes lie just beyond the current bound and can only be explored after the threshold increases.

IDA* therefore revisits the search multiple times, gradually expanding the region of admissible nodes.

2.7 Memory Advantage

The main advantage of this strategy is memory efficiency.

Since each iteration is depth-first, the algorithm stores only the current recursive path plus a small amount of auxiliary information.

In contrast to A*, IDA* does not need to keep the full frontier in memory.

2.8 The Main Trade-off

The price of low memory consumption is repeated work.

• memory usage decreases
• state revisitation increases

IDA* may explore the same prefixes many times across different threshold values.

This is the fundamental trade-off between A* and IDA*.