A* Search finds the cheapest path fast by keeping every
frontier cell sorted in a priority queue — but that queue is the whole cost: in the worst case it
holds an entry for every cell A* has ever touched, O(V) memory that has to fit
somewhere. Iterative Deepening DFS solves a related memory
problem a different way: repeat a bounded depth-first search, one deeper limit at a time, so peak
memory is only ever the current path, O(d). IDA* borrows IDDFS's entire outer shape —
the same repeated bounded DFS, the same discipline of only ever holding one path in memory — and
swaps its one moving part: the bound is no longer a raw depth, it's A*'s own
f(n) = g(n) + h(n). Instead of depth === limit, the cutoff test becomes
f(n) > threshold, and each failed iteration raises the threshold to the smallest
f-value that overflowed the old one — one cost band deeper, not one edge deeper.
Same wall-maze mechanics as the IDDFS demo — click a cell to toggle a wall, green start and
orange end fixed — with A*'s heuristic-mode toggle layered on top. Step through and watch two
numbers on every visited cell's log line: g (steps taken so far) and h
(Manhattan distance still to go); their sum f is what gets compared against the
current threshold, shown in the stats line above the maze along with the running
total node-visits across every iteration so far — the same redundant-work tally IDDFS's own demo
keeps, just counted against a cost bound instead of a depth bound. Switch the heuristic mode to
inflated to see what an overestimating heuristic does here — see Pitfalls below
for the checked, concrete wrong answer it produces on this exact maze.
A*'s correctness rests on admissibility: as long as h(n) never
overestimates the true remaining cost, f(n) = g(n) + h(n) is a lower bound on the
cost of the cheapest path through n. A*'s priority queue exploits that bound directly
— it always expands the globally smallest f first, so nothing gets finalized before
every cheaper possibility has been tried. IDA* can't sort globally; it has no queue, only a stack.
Instead it fakes the same ordering with thresholds: within one bounded DFS pass, every node with
f ≤ threshold is reachable, and nothing with f > threshold ever gets
expanded — exactly the set A* would have popped by the time its own queue's minimum f
crossed that same value. Raise the threshold to the smallest f-value that got pruned
last time, not by a fixed increment, and the next pass explores exactly one new cost band it
hasn't seen — with no possibility of skipping over a cheaper node sitting at some in-between
f-value, since that value is, by construction, the very next one that matters.
This is the one place IDA*'s bound behaves differently from IDDFS's. IDDFS's threshold is a
depth, so the next value is always exactly limit + 1 — every integer depth gets
tried in order automatically, no bookkeeping required. IDA*'s threshold lives in cost-space, not
step-space, so "add one" isn't meaningful — costs can jump by any amount between neighboring
cells. The algorithm has to explicitly discover the next real threshold from the search itself, by
tracking the smallest f-value it was forced to prune (see the reference
implementation's min variable below). On this page's own demo maze the threshold
happens to climb by a steady +2 each round (a coincidence of this maze's grid parity,
not a rule), but a differently-shaped graph can make it jump by any amount, or stall on the same
value for several rounds if many nodes share an f just past the old bound.
The inner search, bounded by f instead of depth. Note the order of the two checks
at the top — f > threshold is tested before the goal test, not after: if the
path to the goal itself already costs more than the current threshold allows, this iteration must
not accept it, or a later, cheaper iteration would never get the chance to find the real optimum
first.
function search(node, g, threshold, path, onPath, grid, cols, h) {
const f = g + h(node);
if (f > threshold) return f; // pruned — how far over becomes a candidate next threshold
if (node === GOAL) return 'FOUND';
let min = Infinity;
const r = Math.floor(node / cols), c = node % cols;
for (const [dr, dc] of [[-1, 0], [1, 0], [0, -1], [0, 1]]) {
const nr = r + dr, nc = c + dc;
const nk = nr * cols + nc;
if (!inBounds(nr, nc) || grid[nk] === WALL || onPath[nk]) continue;
onPath[nk] = true;
path.push(nk);
const t = search(nk, g + 1, threshold, path, onPath, grid, cols, h);
if (t === 'FOUND') return 'FOUND';
if (t < min) min = t;
path.pop();
onPath[nk] = false; // unmark on the way back out — current-path-only, see Pitfalls
}
return min; // Infinity if every branch dead-ended, otherwise the smallest overflow seen
}The outer loop, identical in shape to IDDFS's own outer loop, with the threshold update as the only real difference:
function idaStar(grid, rows, cols, start, end, h) {
let threshold = h(start);
while (true) {
const path = [start];
const onPath = new Array(rows * cols).fill(false);
onPath[start] = true;
const t = search(start, 0, threshold, path, onPath, grid, cols, h);
if (t === 'FOUND') return { path, cost: threshold }; // first success is provably optimal
if (t === Infinity) return null; // goal unreachable
threshold = t; // smallest f that overflowed — the next real band, not a guess
}
}An inadmissible heuristic breaks IDA* exactly the way it breaks A* — because it rests on
the identical claim about h. Once h can overestimate,
f is no longer a reliable lower bound, and a threshold can succeed on a path that
isn't actually the cheapest one reachable, with nothing to signal that anything went wrong. On this
page's own demo maze — a 5×6 grid with two offset one-cell gaps forcing a real detour — the true
cheapest path costs 15 steps, found correctly at the admissible (Manhattan × 1)
setting in 4 iterations. Switching the heuristic mode to inflated (Manhattan × 2)
makes IDA* converge on a reported cost of 21 instead — 40% more
expensive than optimal — after a different 4 iterations, because an inflated
f(goal) can now clear an early, too-low threshold well before the genuinely cheapest
route ever gets a chance to be tried at that same bound.
Marking a cell visited for the whole iteration, instead of only while it's on the
current path, breaks IDA* for the same underlying reason it breaks IDDFS. The reference
implementation above unmarks onPath[nk] on the way back out of each branch
specifically so a different branch, later in the very same iteration, can reuse that cell if it
needs to. Swap that for a plain "mark and never unmark" visited array — a change that looks like an
obvious, harmless optimization, since revisiting the same cell twice within one DFS pass sounds
wasteful — and on this page's default (admissible) maze, IDA* reports a path costing
17 instead of the true 15, taking a fifth iteration to get
there. It doesn't fail loudly, and it doesn't even look expensive: the buggy version does
less total work to reach the wrong answer, just 76 node-visits against the correct
version's 347, because refusing to ever revisit a cell prunes the search far more aggressively —
it just prunes the one branch that actually mattered along with everything else. An earlier,
ultimately-abandoned branch's claim on a cell survives into a later branch that actually needed it
back, exactly the same failure mode as IDDFS's own version of this bug — DFS's whole ability to
backtrack and try a cell again from a different direction depends on giving cells back once a
branch is done with them, and a version that's both faster and wrong is easy to mistake for an
improvement.
IDA* is not a strictly better A* — it trades A*'s O(V) open-set memory for
real, repeated re-exploration, and the trade is steep on a graph with many alternate routes to the
same node. On this page's own demo maze, A* finalizes 22 cells to find the 15-cost path;
the correct IDA* reference above needs 347 total node-visits across 4 iterations
to reach the identical answer — a 15.8x overhead, almost all of it shallow
ground re-walked once per iteration. That ratio isn't fixed, and it isn't really about maze size:
it's driven by how many different ways the search can reach the same cell, since every one of
those routes gets independently re-tried at every threshold up to the true cost. IDA*'s classic use
case is a state space shaped like a tree, not a graph with many convergent paths — the sliding-tile
puzzle Richard Korf introduced it for in 1985 is a search tree of board configurations where almost
no state is reachable two different ways at comparable cost, so there's little redundant ground to
re-walk. Reach for IDA* when A*'s memory is the actual, felt constraint and the underlying state
space doesn't have many alternate routes to the same place — not as a default drop-in replacement
for A* on an ordinary weighted graph.
Time: the same worst-case bound as A* — in the limit, a heuristic of zero
degenerates IDA* into IDDFS degenerating into plain iterative-deepening search over cost, no better
than exploring everything up to the true cost. What differs from A* is where the cost actually
gets paid: A* pays it once, spread across queue operations; IDA* pays it once per iteration, since
every threshold-band iteration re-walks every node whose f-value fell inside an
already-cleared band before reaching new ground. On this page's own demo maze that shows up as the
measured 15.8x-over-A* figure above; a state space shaped more like a tree, with
few or no repeated routes to the same node, pays far less of this overhead — sometimes negligible,
which is IDA*'s actual sweet spot. Space: O(d) — only the single
root-to-current path, plus one boolean per cell for the current-path check, needs to be held at
once, the same bound as IDDFS and a real improvement over A*'s O(V) open-plus-closed
set, independent of how large the reachable graph is.
For a decision guide across all eleven of this site's Shortest Paths entries, see Choosing a Shortest-Path Algorithm.