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:

The correct answer is option 1.

Key Points

• 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(b^m).
  • Space Complexity: The worst-case space complexity of the greedy best-first search is O(b^m). 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.