What Are the Two Types of Memory-Bounded Heuristic Algorithms?

Memory-bounded heuristic search algorithms are designed for cases where classic best-first methods (notably $A^*$) can require exponential memory due to their maintenance of frontier structures like OPEN/CLOSED. A common framing is that memory-bounded heuristic algorithms come in two broad types:

1. Frontier/graph-style memory bounding (best-first with pruning or node deletion), where the algorithm still behaves like best-first search but enforces a hard cap on stored nodes and deletes “least promising” nodes when memory is full (often described via OPEN/CLOSED limits and pruning from OPEN). This family includes approaches related to SMA* and other memory-bounded variants that “prune the OPEN list by removing the leaf-node with highest $f$-cost” when space is exhausted. 2

2. Depth-first with iterative deepening / linear-space bounds (recursive or repeated deepening strategies), where the algorithm limits memory by re-running depth-first searches under a growing cutoff (e.g., cutoff based on $f=g+h$), so memory stays linear in the search depth. This family includes IDA*, which performs depth-first search and “cuts off a branch when its total cost $f(n)=g(n)+h(n)$ exceeds a given threshold,” increasing the threshold across iterations.

These two types reflect a fundamental design choice:

• Type A: keep best-first guidance but truncate the stored frontier. 2
• Type B: keep depth-first memory usage but re-explore under a changing bound/cutoff. 2

To reason precisely about the “two types,” it helps to connect them to what each algorithm chooses not to keep:

keyword
The set of generated-but-not-fully-expanded states (or nodes) waiting to be processed—commonly represented by OPEN (and sometimes CLOSED) in best-first and $A^*$-like algorithms. In memory-bounded best-first methods, the frontier is intentionally truncated when it exceeds a limit.

keyword
The data structure holding candidate nodes for expansion in best-first search; memory-bounded variants delete nodes from OPEN when storage runs out.

keyword
In iterative deepening variants like IDA*, a bound on $f(n)=g(n)+h(n)$ that determines whether to prune a branch during depth-first traversal.

keyword
Memory that grows proportionally to depth rather than frontier size; achieved by depth-first/cutoff methods like IDA*. 2

Type 1: Memory-bounded best-first search (bounded OPEN/CLOSED; pruning/deletion)

In a best-first search view, each iteration selects the node with lowest (best) $f$-value from OPEN, expands it, and updates OPEN/CLOSED. A memory-bounded variant introduces a maximum storage limit for OPEN (and sometimes CLOSED), such that when the limit is reached, node deletion must be performed on OPEN.

A representative description appears in memory-bounded A*-like methods: when OPEN/CLOSED hits a preset limit, the algorithm “begins to prune the OPEN list by removing the leaf-node with highest $f$-cost.”

This design yields a spectrum of behaviors:

• With sufficiently large memory, the algorithm can emulate $A^*$-like behavior.
• With smaller memory, it behaves like best-first search over a partially remembered frontier, relying on pruning to fit into memory.

[CalloutBlock] type="tip" title="Key mental model (Type 1)" content="If you remember only the “most useful” frontier nodes, you can keep best-first guidance—but you must delete nodes when memory is full."

[CalloutBlock] type="warning" title="Key risk (Type 1)" content="Deleting nodes from OPEN can remove information required to guarantee completeness/optimality under tight memory, because the algorithm no longer has the full frontier it would otherwise need to backtrack/reconstruct the best path."

Type 2: Depth-first iterative deepening / recursive bounds (linear-space)

Iterative deepening A* (IDA*) is a standard example of the second type. It uses a depth-first traversal, but replaces the “fixed depth” cutoff of IDDFS with a heuristic-informed cutoff on $f(n)=g(n)+h(n)$.

Concretely, IDA* works by:

• performing DFS,
• cutting off a branch when $f(n)=g(n)+h(n)$ exceeds the current threshold,
• starting with a threshold and increasing it for subsequent iterations.

This achieves bounded memory because DFS keeps only the current path (plus recursion state), not the entire frontier. A key consequence is that time can increase due to re-exploration across increasing thresholds (nodes may be revisited under different thresholds). 2

keyword
IDA* is a depth-first iterative-deepening variant that prunes using $f(n)=g(n)+h(n)$ thresholds.

[CalloutBlock] type="tip" title="Key mental model (Type 2)" content="You trade memory for repeated work: keep only a DFS stack, and refine the allowed $f$-cost range over iterations."