Q9.Marks: +2.0UGC NET Paper 2: Computer Science 7th Dec 2023 Shift 2
Match List-I with List-II
List I
List II
A.
Hill climbing
I.
O(b^d)
B.
Best first search
II.
O(bd)
C.
A* Search
III.
O(1)
D.
Depth first search
IV.
O(b^m)
Choose the correct answer from the options given below :
1.A - III, B - I, C - IV, D - II✓ Correct
2.A - II, B - I, C - IV, D - III
3.A - II, B - IV, C - I, D - III
4.A - I, B - III, C - II, D - IV
Solution
The correct answer is A - III, B - I, C - IV, D - II
EXPLANATION:
A. Hill Climbing - III. O(1)
Hill climbing is a local search algorithm that focuses on finding a solution in the immediate neighborhood of the current state. The time complexity is often constant (O(1)) because it explores only one path at a time.
B. Best First Search - I. O(bd)
Best-first search is a graph search algorithm that uses a heuristic to determine the most promising path to explore first. The time complexity is generally exponential, O(bd), where b is the branching factor and d is the depth of the shallowest goal.
C. A* Search - IV. O(bm)
A* search is an informed search algorithm that uses a heuristic to guide the search process. The time complexity is typically exponential but is often more efficient than a naive best-first search. O(bm) represents the complexity, where b is the branching factor, and m is the maximum depth of the search.
D. Depth First Search - II. O(bd)
The time complexity of depth-first search is O(bd) where b is the branching factor (2 for the binary trees below) and m is the maximum depth of the tree. Its space complexity is only bd.
So, the correct match is A - III, B - I, C - IV, D - II.