Which search strategy expands all nodes at depth d before any nodes at depth d+1?
BFS explores level by level, expanding all nodes at depth d before moving to depth d+1.
If a heuristic h(n) is NOT admissible (i.e., h(n) > h*(n) for some n), A* Tree Search:
Inadmissible heuristics overestimate cost, which can cause A* to skip the true optimal path.
In Bidirectional Search, if the branching factor is b and distance between source and goal is d, the overall time complexity is:
Bidirectional search runs simultaneously from start and goal, meeting in the middle at depth d/2.
Which algorithm modifies A* to run using linear memory O(b * d) by using iterative deepening on f-values?
Iterative Deepening A* (IDA*) uses threshold-limited DFS cutoffs based on f(n) = g(n) + h(n).
In Monte Carlo Tree Search (MCTS), the four main phases executed in each iteration are:
MCTS iteratively runs Selection (UCT), Expansion, Simulation (rollout), and Backpropagation.