6. Memory-Bounded Search

Source: AIMA 4th Ed., Chapter 3 (Section 3.5.5) Status: Complete

Overview

A* is both complete and cost-optimal, but its space complexity is O(b^d) — it keeps all generated nodes in memory. For large search problems, A* runs out of memory long before it runs out of time. Memory-bounded search algorithms sacrifice some time efficiency to operate within a fixed memory budget.

Beam Search

Core idea: Keep only the k best nodes in the frontier at each step (where k is the “beam width”). Discard all others.

Evaluation function: typically h(n) or f(n); keep the k lowest-scoring nodes.

Properties

When to use: large search spaces where finding any good solution quickly matters more than guaranteed optimality. Common in NLP (translation, speech recognition), protein folding prediction, and other applications where the state space is huge.

Failure mode: if the optimal path passes through a node that was pruned, beam search cannot recover. Increasing k improves quality but reduces the speed advantage.

IDA* (Iterative Deepening A*)

Core idea: Like iterative deepening search, but the cutoff is based on f-cost (g + h) rather than depth.

Run depth-first search with a threshold on f-cost. At each iteration, expand all nodes with f(n) <= threshold. If no solution is found, increase threshold to the minimum f-value of any node that was cut off in the previous iteration.

function IDA*(problem) returns solution or failure
    threshold <- h(problem.INITIAL)
    while true do
        result, threshold <- DFS-CONTOUR(NODE(problem.INITIAL), threshold)
        if result = solution then return result
        if threshold = infinity then return failure

function DFS-CONTOUR(node, threshold) returns (result, new_threshold)
    f <- g(node) + h(node)
    if f > threshold then return failure, f      -- exceeded: report f for next iteration
    if problem.IS-GOAL(node.STATE) then return node, threshold
    min_exceeded <- infinity
    for each child in EXPAND(problem, node) do
        if not IS-CYCLE(child) then
            result, t <- DFS-CONTOUR(child, threshold)
            if result != failure then return result, threshold
            min_exceeded <- min(min_exceeded, t)
    return failure, min_exceeded

Key properties

Advantage over A: linear space instead of exponential. For 15-puzzle, IDA with Manhattan distance is the practical method of choice.

Disadvantage: IDA* suffers from excessive node regeneration (same nodes expanded in multiple iterations). It also struggles with continuous-valued heuristics — if h takes many distinct values, each iteration may increase the threshold by only a tiny amount, causing an enormous number of iterations. A common fix: round h to multiples of some ε.

RBFS (Recursive Best-First Search)

Core idea: Simulate A* search using only linear space by remembering the best alternative f-value encountered so far. When the current best path seems worse than the best alternative, backtrack and track the backed-up f-value so we know when to return to this subtree.

function RECURSIVE-BEST-FIRST-SEARCH(problem) returns solution or failure
    solution, fvalue <- RBFS(problem, NODE(problem.INITIAL), infinity)
    return solution

function RBFS(problem, node, f_limit) returns solution or failure, and new f-cost limit
    if problem.IS-GOAL(node.STATE) then return node, node.f
    successors <- LIST(EXPAND(problem, node))
    if successors is empty then return failure, infinity
    for each s in successors do
        s.f <- max(s.PATH-COST + h(s), node.f)    -- backed-up value
    while true do
        best <- successor in successors with lowest f-value
        if best.f > f_limit then return failure, best.f
        alternative <- second-lowest f-value among successors
        result, best.f <- RBFS(problem, best, min(f_limit, alternative))
        if result != failure then return result, best.f

Key mechanism: backed-up f-values

When RBFS backtracks from a subtree, it saves the best f-value found within that subtree back to the parent node. This means when RBFS later considers returning to that subtree, it uses the realistic (backed-up) f-estimate rather than the original potentially-optimistic h value.

The line s.f <- max(s.PATH-COST + h(s), node.f) ensures f-values are non-decreasing along any path (like consistency), preventing infinite oscillation.

Romania example trace

Start: Arad (f=366) - Expand Arad: successors Sibiu(f=393), Timisoara(f=447), Zerind(f=449) - f_limit = inf; best = Sibiu (f=393); alternative = 447 - Recurse into Sibiu with f_limit = 447 - Expand Sibiu: successors Rimnicu-Vilcea(f=413), Fagaras(f=415), Oradea(f=671), Arad(loop) - best = Rimnicu-Vilcea (f=413); alternative = 415 - Recurse into Rimnicu-Vilcea with f_limit = 415 - Expand: Pitesti(f=415) … all successors have f >= 415 - best has f=415 = f_limit -> return failure, 415 - best.f updated to 415; now best = Fagaras (f=415) = alternative - Continue exploring… - Eventually Bucharest reached via Pitesti with optimal cost 418

Properties

**RBFS vs IDA*:** - RBFS is somewhat more efficient than IDA* (avoids some redundant expansion) - Both suffer from excessive regeneration — every time RBFS changes its mind, it must re-expand the forgotten subtree - RBFS uses too little memory: even if more were available, it cannot use it

SMA* (Simplified Memory-Bounded A*)

Core idea: Use all available memory. Proceed like A*, expanding best leaf nodes, until memory is full. When memory fills, drop the worst leaf node (highest f-value) and back up its f-value to its parent (so the parent knows the quality of the forgotten subtree). Regenerate forgotten subtrees only when all alternatives look worse.

SMA* algorithm outline

1. Expand the best (lowest f) leaf node.
2. If memory is not full, add all successors to the search tree.
3. If memory is full:
   • Drop the worst leaf (highest f) from the search tree.
   • Update the dropped node’s parent: parent.f = max(parent.f, dropped.f).
   • If all descendants of some node are dropped, the node becomes a leaf again.
4. If the only node in memory is the root with no successors, return failure (solution not reachable within memory).

Tie-breaking: expand the newest best leaf; delete the oldest worst leaf. This handles the case where all leaves have the same f-value.

Properties

Thrashing problem: on very hard problems where many paths must be considered simultaneously, SMA* is forced to continuously drop and regenerate nodes. This can make a practically solvable problem (given unlimited memory) become intractable. Memory limitations can make a problem computationally intractable — the time-memory tradeoff has no known theoretical escape except dropping the optimality requirement.

When to use SMA*: when you have limited but nonzero memory and need cost-optimal solutions, particularly when the state space is a graph with nonuniform action costs.

Comparison of Memory-Bounded Methods

*Complete and optimal only if the solution is reachable within memory.

The Time-Memory Tradeoff

The fundamental result from this section: there is an unavoidable tradeoff between memory and computation time for optimal search. Algorithms that use less memory (IDA, RBFS) must re-expand more nodes. Algorithms that use more memory (A) expand each node at most once. The only way out of this tradeoff (when memory is the binding constraint) is to drop the optimality requirement.