Next: Example Previous: Analysis

RBFS

Note: This material is also optional (not covered in lecture)

Recursive Best-First Search is a linear space version of Best-First Search

Perform best-first search (using f value) but discard subtrees when perform recursion, so linear memory.

Keep track of the runner-up sibling (upper bound on cost of node).

Expand subtree until f value is greater than bound.

Backtrack and expand lowest-valued node, propagating new f value to parents of expanded node.