Match List I with List II and choose the correct answer from the code given…
2018
Match List I with List II and choose the correct answer from the code given below.
List–I (Search technique) | List–II (Description) |
|---|---|
(a) Greedy Best-First Search | (i) Selects a node for expansion if optimal path to that node has been found. |
(b) A* Search | (ii) Avoids substantial overhead associated with keeping the sorted queue of nodes. |
(c) Recursive Best-First Search | (iii) Suffers from excessive node generation. |
(d) Iterative-deepening A* Search | (iv) Time complexity depends on the quality of heuristic code. |
- A.
(a) – (i), (b)-(ii), (c)-(iii), (d)-(iv)
- B.
(a) – (iv), (b)-(i), (c)-(ii), (d)-(iii)
- C.
(a) – (iv), (b)-(iii), (c)-(ii), (d)-(i)
- D.
(a) – (i), (b)-(iv), (c)-(iii), (d)-(ii)
Attempted by 84 students.
Show answer & explanation
Correct answer: B
Correct matching and explanation:
Greedy Best-First Search → Time complexity depends on the quality of the heuristic (the algorithm uses only h(n); a more informative heuristic reduces search effort, while a poor heuristic can make it explore many nodes).
A* Search → Selects a node for expansion if an optimal path to that node has been found (with an admissible and consistent heuristic, when A* removes a node from the open list to expand it, the path to that node is optimal).
Recursive Best-First Search → Avoids substantial overhead associated with keeping the sorted queue of nodes (RBFS is a memory-bounded variant that uses recursion and limited bookkeeping instead of a large sorted open list).
Iterative-deepening A* Search → Suffers from excessive node generation (IDA* repeatedly explores paths with increasing f-cost thresholds, which causes many nodes to be regenerated across iterations).
Thus the correct mapping is: (a) Greedy Best-First Search – (iv); (b) A* Search – (i); (c) Recursive Best-First Search – (ii); (d) Iterative-deepening A* Search – (iii).
This corresponds to the option that lists: (a) – (iv), (b) – (i), (c) – (ii), (d) – (iii).