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) Incomplete even if the search space is finite. (B) A* → (III) Optimal, if the optimal solution is reachable, otherwise returns the best reachable optimal solution. (C) Recursive best first search → (I) Space complexity is o(d) where d is the depth of the deepest optimal solution. (D) SMA* → (IV) Computation and space complexity is too high.