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:

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: Correct Answer A - II, B - IV, C - I, D - III 

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.