Use app×
Join Bloom Tuition
One on One Online Tuition
JEE MAIN 2025 Foundation Course
NEET 2025 Foundation Course
CLASS 12 FOUNDATION COURSE
CLASS 10 FOUNDATION COURSE
CLASS 9 FOUNDATION COURSE
CLASS 8 FOUNDATION COURSE
0 votes
589 views
in General by (103k points)
closed by

Match List I with List II

List I

List II

(A) Greedy Best-First Search

(I) Space complexity is 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, returns the best reachable optimal solution.

(D) SMA*

(IV) Computation and space complexity is too high.

 

Choose the correct answer from the options given below:


1. A - II, B - IV, C - I, D - III 
2. A - II, B - III, C - I, D - IV
3. A - III, B - II, C - IV, D - I 
4. A - III, B - IV, C - II, D - I

1 Answer

0 votes
by (106k points)
selected by
 
Best answer
Correct Answer - Option 1 : A - II, B - IV, C - I, D - III 

The correct answer is option 1.

  • Greedy best-first search algorithm always selects the path which appears best at that moment. It is the combination of depth-first search and breadth-first search algorithms.
    • Time complexity: The worst-case time complexity of the greedy best-first search is O(bm).
    • Space Complexity: The worst-case space complexity of the greedy best-first search is O(bm). Where m is the maximum depth of the serach space
    • Complete: Greedy best-first search is also incomplete, even if the state space is finite.
    • Optimal: Greedy best-first search algorithm is not optimal.
  • A* is optimal and complete but time complexity and space complexity too high. It requires more computation.
  • Recursive Best-First Search retents more memory knowledge but uses only O(bd) memory
  • Memory Simplified Bound A* such as A* Optimal if you can get optimal solution otherwise as it is memory-bound.

∴ Hence the correct answer is A - II, B - IV, C - I, D - III.

Welcome to Sarthaks eConnect: A unique platform where students can interact with teachers/experts/students to get solutions to their queries. Students (upto class 10+2) preparing for All Government Exams, CBSE Board Exam, ICSE Board Exam, State Board Exam, JEE (Mains+Advance) and NEET can ask questions from any subject and get quick answers by subject teachers/ experts/mentors/students.

Categories

...