In Simplified Memory Bounded A* (SMA*), when memory becomes full during search, which node is dropped from memory to free space?
SMA* manages memory by dropping the worst leaf node (highest f-value) when memory limits are reached, backing up its f-value to its parent node.
Recursive Best-First Search (RBFS) achieves linear spatial complexity O(bd) by:
RBFS mimics best-first search using depth-first recursion, keeping track of the f-value of the best alternative path available at ancestors.
A pattern database heuristic for search problems like the 15-puzzle is constructed by:
Pattern databases precompute and store exact optimal costs to solve specific subproblems (patterns) in a database, serving as admissible heuristics.
Which search algorithm expands the node with the lowest path cost g(n) in uninformed search?
Uniform Cost Search (UCS) expands nodes in order of increasing path cost g(n) from the root, guaranteeing an optimal solution when step costs are non-negative.
In local search, Simulated Annealing avoids getting trapped in local maxima by:
Simulated Annealing accepts downhill (worse) moves according to the Boltzmann probability $\exp(\Delta E / T)$, where temperature T gradually cools down.