Which property ensures that A* Graph Search (with a closed list) never needs to re-open closed nodes?
Consistency (h(n) <= c(n, a, n') + h(n')) guarantees non-decreasing f(n) along any path, preventing re-opening.
What is the space complexity of Depth-First Search (DFS) on a state space with branching factor b and maximum depth m?
DFS only stores nodes along the current path plus unvisited siblings at each level, requiring O(b * m) space.
If two admissible heuristics h1(n) and h2(n) are given, which combined heuristic h(n) is guaranteed to be admissible AND dominate both?
Taking the pointwise maximum of two admissible heuristics gives an admissible heuristic that dominates both.
Under optimal move ordering, $\Alpha-\Beta pruning reduces$ the effective branching factor of Minimax search to:
With perfect move ordering, $\Alpha-\Beta examines O(b^{m/2}) leaf nodes, effectively reducing$ the branching factor to sqrt(b).
Greedy Best-First Search expands nodes based strictly on:
Greedy Best-First Search uses f(n) = h(n) to expand the node that appears closest to the goal.