GATE DA 2024 Set 1 — Question 44
Go beyond PYQs with Success TrackerAI-powered personalised practice and doubt support. Unlimited practice on eligible plans; AI usage limits apply.MCQ+2 / -0.67MediumBreadth-First Search (BFS)Uninformed SearchArtificial IntelligenceDepth-First Search (DFS)
Artificial Intelligence → Uninformed Search → Breadth-First Search (BFS)
Last updated
Question
Consider a state space where the start state is number 1. The successor function for the state numbered returns two states numbered and . Assume that the states in the unexpanded state list are expanded in the ascending order of numbers and the previously expanded states are not added to the unexpanded state list.Which ONE of the following statements about breadth-first search (BFS) and depth-first search (DFS) is true, when reaching the goal state number 6?
Correct answer
(C) Both BFS and DFS expand equal number of states.
Solution
The problem specifies a strict expansion order: "states in the unexpanded state list are expanded in the ascending order of numbers". This constraint overrides the standard LIFO (Stack) behavior of DFS and FIFO (Queue) behavior of BFS regarding tie-breaking or node selection.Successors of : .
Start: 1. Goal: 6.Expansion Process (Ascending Order):
Start: 1. Goal: 6.Expansion Process (Ascending Order):
1.Start with {1}. Expand 1. Successors: {2, 3}.
2.Unexpanded list: {2, 3}. Smallest is 2. Expand 2. Successors: {3, 4}.
3.Unexpanded list: {3, 4} (3 is already present/generated, duplicates handled or set used). Smallest is 3. Expand 3. Successors: {4, 5}.
4.Unexpanded list: {4, 5}. Smallest is 4. Expand 4. Successors: {5, 6}.
5.Unexpanded list: {5, 6}. Smallest is 5. Expand 5. Successors: {6, 7}.
6.Unexpanded list: {6, 7}. Smallest is 6. Goal reached.
Since the expansion choice is determined solely by the state number (ascending), both BFS and DFS will follow the exact same sequence of expansions: 1, 2, 3, 4, 5, 6. Thus, they expand an equal number of states.Continue learning with Success Tracker
A step still unclear? Work through it with support
Use Success Tracker to ask about the reasoning, then try another GATE DA question to check your understanding.
AI-powered practice· Unlimited practice on eligible plans
- PYQs with solutions
- Attempt available previous-year questions, then compare your reasoning with the worked solution. Coverage varies by stream.
- Practice that adapts
- Choose a topic, work on weaker areas and bookmark questions to revisit. Your attempts feed your progress tracking.
- AI doubt support
- Ask follow-up questions about a step or concept while practising, instead of stopping at the final answer.
Unlimited practice is available on eligible plans. Free practice and AI usage have limits; check the current plan allowances before choosing.
This page stays readable without an account. AI responses can be wrong; check them against the solution and source material.
More questions on Uninformed Search
2026 Set 1 Q13Which of the following algorithms is NOT an example of uninformed search?2026 Set 1 Q14Which of the following statements is NOT true? (The names of the predicates are intuitive.)2026 Set 1 Q23In the following table, the
Task column lists a few tasks related to machine learning. The…2026 Set 1 Q24Sentence is said to entail Sentence if whenever is TRUE, also must hold TRUE. Which…2026 Set 1 Q30Consider the game tree for a two-player turn-taking minimax game as shown in the figure. The value…