Discrete Mathsfor Engineers

3. The IDA* Algorithm

IDA* combines two ideas: heuristic evaluation through f(n) = g(n) + h(n) and depth-first exploration under a cost bound.

The algorithm repeatedly invokes a bounded recursive search, increasing the threshold only when necessary.

3.1 Global Control Structure

At the top level, IDA* maintains a current threshold and repeatedly launches a depth-first search from the start state.

Each iteration has one of three outcomes:

• the goal is found
• all reachable nodes within the threshold are exhausted
• a new minimum exceeded value is returned

If the goal is not found, that returned value becomes the threshold for the next iteration.

3.2 Recursive Search Procedure

The core of IDA* is a recursive depth-first function that explores successors of the current node.

For each visited node, the algorithm computes:

If this value exceeds the current threshold, the recursion does not continue below that node.

3.3 Cutoff Condition

A node is pruned whenever f(n) > T, where T is the current threshold.

In that case, the function does not simply return failure.

Instead, it returns the value f(n), because that value may become the next threshold.

3.4 Goal Detection

Before expanding successors, the algorithm checks whether the current node is a goal state.

If so, the search terminates successfully, and the solution path can be reconstructed from the current recursive stack or predecessor structure.

Goal detection happens inside the bounded DFS, not outside it.

3.5 Propagating the Next Threshold

During one bounded search, several nodes may exceed the threshold.

The recursive calls propagate upward the smallest exceeded f-value encountered.

This value is the minimum threshold that allows progress beyond the current iteration.

3.6 Path-Based Cycle Avoidance

Since IDA* relies on depth-first exploration, it must avoid trivial cycles along the current path.

A common strategy is to forbid recursion into a state already present in the current path.

This is weaker than maintaining a full global closed set, but it preserves the memory-efficient character of the algorithm.

3.7 Canonical IDA* Template

The general structure of IDA* can be expressed as follows:

IDA*(start):

    threshold = h(start)

    while true:
        result = SEARCH(start, g=0, threshold)

        if result is FOUND:
            return solution

        if result is ∞:
            return failure

        threshold = result


SEARCH(node, g, threshold):

    f = g + h(node)

    if f > threshold:
        return f

    if node is goal:
        return FOUND

    min_exceeded = ∞

    for each successor s of node:
        temp = SEARCH(s, g + cost(node, s), threshold)

        if temp is FOUND:
            return FOUND

        if temp < min_exceeded:
            min_exceeded = temp

    return min_exceeded

3.8 How to Interpret the Algorithm

Each iteration answers the question:

If the answer is no, the algorithm computes the smallest threshold that would make further exploration possible.

In this sense, IDA* alternates between bounded DFS and threshold revision.

3.9 Operational Summary

• initialize the threshold with the start evaluation
• run a depth-first search bounded by that threshold
• prune nodes whose f-value is too large
• record the minimum exceeded value
• repeat until the goal is found or no solution exists

This structure gives IDA* its characteristic balance: low memory consumption at the cost of repeated search effort.