UGC NET CSE | October 2020 | Part 2 | Question: 73

Question

Match $\text{List I}$ with $\text{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}$

Answer 1

Greedy Best-First Search its greedy  so choose local best ,  soln not guaranteed hence incomplete

hence A-II

A* is optimal & complete   but Computation and space complexity too high

hence B-IV

 RBFS retains more information in memory, but only uses O (bd ) memory

C-I

Simplified Memory Bounded A* ( like A* Optimal if optimal solution is reachable else  since bounded by memory,

                                                               returns the best reachable optimal solution)

D-III

 

hence  right ans is option A

https://pages.mtu.edu/~nilufer/classes/cs5811/2012-fall/lecture-slides/cs5811-ch03-search-b-informed-v2.pdf