Given below are two statements Statement I: Breadth‐First Search is optimal…
2021
Given below are two statements
Statement I: Breadth‐First Search is optimal when all the step costs are equal whereas uniform‐cost search is optimal with any step‐cost.
Statement II: When all the step costs are same uniform‐cost search expends more nodes at depth d than the Breadth‐First Search.
In light of the above statements, choose the correct answer from the options given below
- A.
Both Statement I and Statement II are false
- B.
Both Statement I and Statement II are true
- C.
Statement I is false but Statement II is true
- D.
Statement I is true but Statement II is false
Attempted by 133 students.
Show answer & explanation
Correct answer: B
Conclusion: Both Statement I and Statement II are true.
Statement I Explanation: Breadth-First Search (BFS) only finds the shallowest node, which is optimal only if all step costs are the same. Uniform-Cost Search (UCS) expands nodes with the lowest path cost, making it optimal even if costs are unequal (provided costs are non-negative).
Statement II Explanation: When all costs are equal, UCS and BFS are functionally similar. However, UCS expands nodes by total cost (\(g(n)\)), whereas BFS expands by depth. Because UCS can explore paths deeper than the current optimal depth before finishing, it may expand more nodes. [1, 2, 3]
A video solution is available for this question — log in and enroll to watch it.