Match List I with List II \(\begin{array}{llll} & \text{List I} & & \text{List…
2020
Match List I with List II
\(\begin{array}{llll} & \text{List I} & & \text{List II} \\ (A) & \text{Greedy Best-First Search} & (I) & \text{Space complexity is O(d) where} \\ &&& \text{d=depth of the deepest optimal} \\ &&& \text{solution} \\ (B) & A^* & (II) & \text{Incomplete even if the search space is} \\ &&& \text{finite} \\ (C) & \text{Recursive Best-First Search} & (III) & \text{Optimal if optimal solution is} \\ &&& \text{reachable; otherwise, returns the best} \\ &&& \text{reachable optimal solution} \\ (D) & \text{SMA*} & (IV) & \text{Computation and space complexity} \\ &&& \text{is too high} \end{array}\)
Choose the correct answer from the options given below:
- A.
\(\text{A-II, B-IV, C-I, D-III}\) - B.
\(\text{A-II, B-III, C-I, D-IV}\) - C.
\(\text{A-III, B-II, C-IV, D-I}\) - D.
\(\text{A-III, B-IV, C-II, D-I}\)
Attempted by 93 students.
Show answer & explanation
Correct answer: A
Correct matching and brief justification:
Greedy Best-First Search -> Incomplete even if the search space is finite. Greedy uses only the heuristic and can miss goals or loop, so it is not guaranteed complete.
A* -> Computation and space complexity is too high. A* is optimal with an admissible heuristic but may require exponential time and memory in the worst case.
Recursive Best-First Search (RBFS) -> Space complexity is O(d) where d is the depth of the deepest optimal solution. RBFS trades extra time for linear (depth) space usage.
SMA* -> Optimal if the optimal solution is reachable within memory; otherwise returns the best reachable solution. SMA* is a memory-bounded variant of A* that sacrifices optimality only when memory prevents finding the true optimal.