Solution

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.