Skip to content
Tutorials Center
My learning

Topics

Lesson 12 of 46 ยท Informed Search

IDA*, Beam Search and Weighted A*

Learn memory-bounded and approximate heuristic search: IDA*, beam search, weighted A* and the idea of RBFS, with measured results on the 8-puzzle.

A* is optimal and efficient in the number of nodes it expands, but it has to remember every node it has generated. On the 8-puzzle that is a few thousand entries and nobody notices. On the 15-puzzle, in a large planning problem or on a game map the size of a city, the table of known states grows until the machine runs out of memory, usually after minutes rather than hours. When memory is the bottleneck you have two honest options: give up some memory (and accept more repeated work) or give up some optimality (and accept a worse answer).

This lesson covers both. IDA* and RBFS keep optimality and use memory proportional to the solution depth. Beam search and weighted A* accept answers that may not be the best in exchange for speed and a small footprint. All four are measured on the same 8-puzzles so you can see the trade-offs rather than take them on trust.

IDA*: iterative deepening, guided by f

You already know iterative deepening: repeat a depth-limited depth-first search with a growing limit, so memory stays small. IDA* does the same, but the cutoff is not depth. It is the value of f = g + h.

  1. Set the bound to f(start) = h(start).
  2. Run a depth-first search that refuses to enter any node whose f exceeds the bound. Remember the smallest f value that was rejected.
  3. If the goal was reached, stop. Otherwise raise the bound to that smallest rejected value and repeat.

Because the bound is always the cheapest f that the previous round could not afford, IDA* never skips over a better solution: with an admissible heuristic the first solution it finds is optimal. Its memory is just the current path, O(d), and it needs no priority queue and no explored table.

flowchart TD
    A["bound = h(start)"] --> B["Depth-first search<br/>prune nodes with f above bound"]
    B --> C{"Goal found?"}
    C -- yes --> D["Return the path"]
    C -- no --> E["bound = smallest f<br/>that was pruned"]
    E --> B

IDA* is iterative deepening whose depth limit is replaced by an f-cost limit.

The price is repeated work: shallow nodes are re-expanded in every round, and without a table IDA* can visit the same state many times through different paths. On puzzles with few distinct f values (like the 8-puzzle, where f only changes in steps of 2) the number of rounds is small and the repetition is tolerable. On problems with real-valued costs, each round may add just one new node, which is a known weakness.

The program compares A* with IDA* on five scrambled puzzles. "Stored" is how many states A* had to keep in its table; "path" is the deepest path IDA* ever held.

Python A* versus IDA*: time and memory

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both algorithms return the same optimal length (the assert would fail otherwise). The work is similar, from about a hundred to about three thousand nodes either way, and sometimes IDA* even visits fewer nodes, because it skips the heap bookkeeping and cuts off hopeless branches early. The memory difference is the point: A* remembered up to 3,337 states, while IDA* never held more than a path of 27. Scale that gap to a puzzle with a billion reachable states and it decides whether the program runs at all.

RBFS in one paragraph

Recursive best-first search (RBFS) is another memory-bounded optimal algorithm. It runs like best-first search but only through recursion, so it stores only the current path and its siblings. Each recursive call is given an f-limit equal to the best alternative f in the tree above it. When the current subtree's best f exceeds that limit, the call unwinds and backs up the best f it found, remembering how promising the abandoned subtree was. If it later turns out to be the best option, the search returns to it. That memory of forgotten subtrees avoids some of the repetition of IDA*. It is shown read-only here, because it is rarely a better choice than IDA* in practice and the code is easiest to follow by reading.

Python
import math

def rbfs(state, g, f, f_limit, path):
    """Returns (solution path or None, backed-up f value of this subtree)."""
    if state == GOAL:
        return path, f
    successors = []
    for t in neighbours(state):
        if t in path:
            continue
        # a child never looks better than its parent did, which keeps f monotone
        successors.append([max(g + 1 + manhattan(t), f), g + 1, t])
    if not successors:
        return None, math.inf
    while True:
        successors.sort(key=lambda x: x[0])
        best = successors[0]
        if best[0] > f_limit:
            return None, best[0]                   # unwind, reporting the best f seen
        alternative = successors[1][0] if len(successors) > 1 else math.inf
        result, best[0] = rbfs(best[2], best[1], best[0],
                               min(f_limit, alternative), path + [best[2]])
        if result is not None:
            return result, best[0]

# solution, _ = rbfs(start, 0, manhattan(start), math.inf, [start])

Weighted A*: trading quality for speed

Sometimes you don't need the best answer; you need a good answer now. Weighted A* changes the priority to

f(n) = g(n) + w ยท h(n), with w โ‰ฅ 1.

When w = 1 you have ordinary A*. When w is huge, the g term barely matters and you get greedy best-first search. In between, the search is pulled toward the goal more strongly. There is a clean guarantee: with an admissible h, the solution cost is at most w times the optimal cost. You choose the quality bound you can live with, and the algorithm usually delivers much better than the bound.

Beam search: keep only the best few

Beam search limits memory in a different way. It expands the search level by level, like breadth-first search, but after generating all the children of the current level it keeps only the k best according to the heuristic (k is the beam width) and throws the rest away. Memory is O(k) per level and time is predictable.

Beam width Behaviour
k = 1 Hill climbing: follows one path, easily trapped
Small k Very fast, short on memory, often fails or returns long paths
Large k Approaches breadth-first search with a heuristic filter
k = โˆž Plain breadth-first search

Beam search is incomplete (the pruned states may have been the only way forward) and not optimal. It is popular in places where an approximate answer is perfectly fine: speech recognition and machine translation both use it to pick likely word sequences.

The program below runs weighted A* with different weights and beam search with different widths on the same ten puzzles.

Python Weighted A* and beam search on the 8-puzzle

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the weighted A* rows. Going from w = 1 to w = 1.5 cuts the average expansions from 1,343 to 390, while the average solution grows only from 21.8 to 22.4 moves. That is the sweet spot of weighted A*: a small push toward greedy behaviour removes most of the work. At w = 5 the solutions have become noticeably worse (32.0 moves). The "worst ratio" column shows that the guarantee holds: no solution ever exceeds w times the optimum.

Beam search shows the opposite risk. With width 1 only 2 of the 10 puzzles are solved, because one wrong turn leaves the beam with nothing to expand. Width 3 solves them all but with long, wandering paths (67.6 moves on average), so quality does not improve smoothly with width. Widths 10, 50 and 200 solve everything, with average lengths of 33.6, 23.2 and 21.8; the widest beam is nearly optimal but also stores nearly the whole frontier, so you are back where you started.

Beam search with a seen set, as written here, can fail by running out of candidates. Real systems keep the beam from collapsing by allowing some diversity or by restarting with a wider beam when it fails.

Choosing a method

Situation Reasonable choice
Memory is plentiful, you need the optimum A*
Memory is tight, you need the optimum IDA* (or RBFS)
You need a fast answer with a quality bound Weighted A*
You need a fast answer, any quality will do Greedy best-first
A rough answer is fine and memory must be fixed Beam search

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the cutoff used by IDA* in each round?

    IDA* prunes nodes whose f exceeds the bound, then sets the next bound to the smallest rejected f, so no cheaper solution can be skipped.
  2. 2. Why does IDA* use so little memory compared with A*?

    IDA* keeps just the path from the start to the current node (O(d) memory), at the price of re-expanding nodes in later rounds.
  3. 3. Weighted A* uses f = g + w*h with w = 2 and an admissible h. What does it guarantee?

    The guarantee is on solution quality: cost <= w times the optimum. It usually does much better than the bound and expands far fewer nodes.
  4. 4. Which statement about beam search is true?

    Dropping all but the k best states per level bounds memory, but it can throw away the only route to the goal, as the width-1 run showed.
  5. 5. What does RBFS remember that IDA* forgets?

    RBFS backs up the best f found in a subtree before unwinding, so it knows how promising the abandoned subtree was and can return to it.

Summary

  • A* is limited by memory, since it stores every generated state; memory-bounded and approximate variants address that.
  • IDA* runs depth-first searches bounded by f = g + h, raising the bound to the smallest pruned f; it is optimal with an admissible heuristic and uses O(d) memory.
  • RBFS also uses linear memory, remembering the best f of abandoned subtrees by backing it up as it unwinds.
  • Weighted A* (f = g + wยทh) trades quality for speed with a guaranteed bound of w times the optimal cost.
  • Beam search keeps only the k best states per level: bounded memory, but incomplete and not optimal.

Next, leave paths behind and search for good states directly in Local Search and Hill Climbing.