Question

Match List I with List II.

LIST I	LIST II
(A) A* Algorithm	(I) Space complexity is O4, where d = depth of the deepest optimal solution.
(B) Recursive Best First Search	(II) Incomplete even if the search space is finite.
(C) Recursive Best First Search	(III) Optimal, if the optimal solution is reachable, otherwise returns the best reachable optimal solution.
(D) SMA* Algorithm	(IV) Computation and space complexity is too high.

Choose the correct answer from the options given below:

• (A) - (II), (B) - (IV), (C) - (III), (D) - (I)
• (A) - (III), (B) - (II), (C) - (I), (D) - (IV)
• (A) - (II), (B) - (III), (C) - (I), (D) - (IV)
• (A) - (IV), (B) - (I), (C) - (III), (D) - (II)

Hint:

Remember that A* is optimal and complete if the heuristic is admissible and consistent, while greedy search is incomplete in finite spaces.

Answer 1

The Correct Option is C

(A) Greedy best-first search → (II) It is incomplete, even within a finite search space. (B) A* → (III) It is optimal if an optimal solution is reachable; otherwise, it returns the best reachable optimal solution. (C) Recursive best-first search → (I) Its space complexity is o(d), where d is the depth of the deepest optimal solution. (D) SMA* → (IV) It exhibits excessively high computational and space complexity.