Q98.Marks: +2.0UGC NET Paper 2: Computer Science 26th Nov 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
1.Both Statement I and Statement II are true✓ Correct
2.Both Statement I and Statement II are false
3.Statement I is true but Statement II is false
4.Statement I is false but Statement II is true
Solution
Breadth-First Search: It is a graph traversal algorithm that starts traversing the graph from the root node and explores all the neighbouring nodes. Further, it selects the nearest node and explores all the unexplored nodes. While using BFS for traversal, any node in the graph can be considered as the root node.
Breadth-first search is optimal when all step costs are equal, because it always expands the shallowest unexpanded node.
Uniform-Cost Search: It is an uninformed search algorithm that uses the lowest cumulative cost to find a path from the source to the destination. In this algorithm, nodes are first expanded, starting from the root, according to the minimum cumulative cost and then the uniform-cost search is implemented using a Priority Queue.
Uniform cost searches always expands the node with the lowest total path cost from the initial node. Hence, it is always optimal.
Statement I is TRUE.
Statement II is TRUE because at depth d, when we implement breadth first search with same cost at all nodes, it will have to search lesser nodes but uniform cost search will always check for the lowest cumulative cost, hence, will expend more nodes than BFS.