Iterative-Deepening A* (IDA*)

The idea

IDA* is A*'s memory-light cousin. It runs plain depth-first search, but with a rule: never go past a "budget" measured by f = g + h, where g is the cost so far and h is a guess of the cost still to go. Each round it tries again with the smallest budget that was too tight last time. This keeps A*'s smart, goal-directed guidance while using almost no memory.

How it works

1. Set the starting budget (the threshold) to f(start) = h(start), since g is 0 at the start.
2. Begin a depth-first search from the start node, tracking g (cost accumulated on the current path).
3. At each node, compute f = g + h. If f is greater than the current threshold, do NOT expand it — instead remember this f as a candidate for the next threshold and back up.
4. If a node is the goal, stop and return the path — this is your answer.
5. Otherwise keep diving depth-first into children, exactly like DFS, so only the current path sits in memory.
6. When the whole search finishes without a goal, look at all the f values that exceeded the threshold and take the smallest one.
7. Raise the threshold to that smallest exceeding f and run the entire depth-first search again from scratch.
8. Repeat until the goal is found; because the threshold climbs in small steps, the first goal found is the cheapest.

OPEN, CLOSED & the data structures

The recursion stack itself (holding only the current root-to-node path) plus a single number: the current f-threshold. During each round it also tracks the minimum f value seen that exceeded the threshold, which becomes the next round's threshold. Unlike A*, there is no big OPEN priority queue and no CLOSED set of all visited nodes.

Pseudocode

function IDA_STAR(start):
    threshold = h(start)                 # f = g + h, and g(start) = 0
    loop:
        next_threshold = INFINITY
        found = DFS(start, g=0, threshold)   # returns FOUND or the min exceeding f
        if found is a goal path: return found
        if next_threshold == INFINITY: return FAILURE   # no nodes left to try
        threshold = next_threshold           # raise to smallest f that overshot

function DFS(node, g, threshold):
    f = g + h(node)
    if f > threshold:
        next_threshold = min(next_threshold, f)   # remember for next round
        return NOT_FOUND
    if node is goal: return path-to(node)
    for each child of node:
        result = DFS(child, g + cost(node, child), threshold)
        if result is a goal path: return result
    return NOT_FOUND

At a glance