In a state space with branching factor $b = 3$, if a goal is located at depth $d = 4$, how many maximum nodes are generated in the worst case by BFS (including root)?
Total nodes = 1 + 3 + $3^2 + 3^3 + 3^4$ = 1 + 3 + 9 + 27 + 81 = 121.
If h1(n) = 5 and h2(n) = 8 for a state n, what is the value of the dominant combined heuristic h(n) = max(h1(n), h2(n))?
$h(n) = max(5, 8) = 8.$
For an 8-puzzle state with current tile positions: [1,2,3; 4,5,6; 8,7,blank] and goal [1,2,3; 4,5,6; 7,8,blank], calculate the Manhattan Distance heuristic value.
Tile 7 is 1 step away from target. Tile 8 is 1 step away from target. Total Manhattan distance = 1 + 1 = 2.
A game tree has branching factor $b = 4$ and depth $m = 4$. Under PERFECT move ordering, using the standard $\Alpha-\Beta leaf-node bound b^{m/2}, how many leaf evaluations$ are performed asymptotically?
Using the standard optimal-ordering bound, leaf evaluations are O($b^{m/2$}) = $4^{4/2$} = $4^2$ = 16.
Attempting to unify P(x, x) and P(y, f(y)) triggers which crucial check in First-Order Unification?
Unifying x with y gives P(y, y) and P(y, f(y)). Unifying y with f(y) fails Occurs Check because y occurs in f(y).