What is the space complexity of Breadth-First Search (BFS) when searching a tree with branching factor b and optimal goal depth d?
BFS stores all generated nodes in memory at the current frontier depth, leading to exponential memory requirements O($b^d)$.
In Uniform Cost Search (UCS), which node is selected for expansion at each step?
UCS expands frontier nodes in order of non-decreasing path cost g(n), equivalent to Dijkstra's algorithm.
Which condition must a heuristic h(n) satisfy to be consistent (monotonic) for graph search A*?
Consistency enforces the triangle inequality: estimated cost h(n) cannot exceed step cost c(n,a,n') plus successor heuristic h(n').
Which search algorithm expands the node that is closest to the goal according to an evaluation function f(n) = h(n)?
Greedy Best-First Search expands the node with the lowest heuristic value h(n), estimating the remaining cost to the goal.
In a game tree with branching factor b and search depth m, what is the time complexity of the Minimax algorithm without pruning?
Minimax explores the entire game tree down to depth m, generating $b^m$ terminal leaf evaluations.