Match List - I with List - II : List - I List - II (A) Greedy Best first…
2023
Match List - I with List - II :
List - I List - II
(A) Greedy Best first search (I) The space complexity as O(d) where d = depth of the deepest optimal solution
(B) A* (II) Incomplete even if the search space is finite
(C) Recursive best first search (III) Optimal if optimal solution is reachable otherwise return the best rechable optimal solution
(D) SMA* (IV) Computation and space complexity is two light
Choose the correct answer from the options given below:
- A.
(A)-(II),(B)-(IV),(C)-(I),(D)-(III)
- B.
(A)-(II),(B)-(III),(C)-(I),(D)-(IV)
- C.
(A)-(III),(B)-(II),(C)-(IV),(D)-(I)
- D.
(A)-(III),(B)-(IV),(C)-(II),(D)-(I)
Attempted by 91 students.
Show answer & explanation
Correct answer: A
Correct match: Greedy Best-First → Incomplete in finite spaces; A* → High computation and space complexity; Recursive Best-First Search → Space O(d); SMA* → Returns best reachable when memory is insufficient (optimal if reachable).
Greedy Best-First Search: It uses only the heuristic to choose the next node and can be led away from the goal or get stuck; therefore it can be incomplete even when the search space is finite.
A*: Combines actual cost and heuristic (g + h) and is optimal with an admissible heuristic, but it typically consumes a lot of time and memory because it stores many generated nodes, so its computation and space costs are high.
Recursive Best-First Search (RBFS): A memory-efficient version that uses linear space proportional to the depth of the deepest solution O(d) while attempting to find an optimal path.
SMA*: A memory-bounded variant of A*. If enough memory is available it finds an optimal solution; if memory is insufficient it returns the best solution reachable within the memory limits.
A video solution is available for this question — log in and enroll to watch it.