This set of Artificial Intelligence MCQs focuses on blind or uninformed search, where the agent has no information beyond the problem definition. You will compare breadth-first, depth-first, uniform cost, depth-limited, iterative deepening and bidirectional search on completeness, optimality, time and space complexity, and trace them on small graphs. It is aimed at GATE and UGC NET candidates, university semester examinations and technical interviews that test search algorithms.
How to practise: read each question and tap the option you think is correct. You will see right away whether you got it, along with a short explanation, and your score is tracked at the bottom of the screen. This set has 18 questions.
Topics covered in this set
- Breadth-first and depth-first search
- Uniform cost search and path costs
- Depth-limited and iterative deepening search
- Bidirectional search
- Completeness, optimality and complexity in terms of b, d and m
- Tree search versus graph search
Artificial Intelligence MCQs with answers and explanations
Q1. Which statement about breadth-first search is correct?
a) It is complete if the branching factor is finite and optimal when all step costs are equal
b) It is optimal for arbitrary positive step costs
c) It uses space linear in the depth of the solution
d) It is incomplete even in finite state spaces
Q2. What is the space complexity of breadth-first search, where b is the branching factor and d is the depth of the shallowest goal?
a) O(bd)
b) O(b^d)
c) O(b^m)
d) O(d)
Q3. What is the space complexity of depth-first tree search, where m is the maximum depth of the search tree?
a) O(b^m)
b) O(b^d)
c) O(bm)
d) O(m^b)
Q4. On what basis does uniform cost search choose the next node to expand?
a) The node with the smallest estimated cost to the goal h(n)
b) The deepest node in the frontier
c) The shallowest node in the frontier
d) The node with the lowest path cost g(n) from the start
Q5. Uniform cost search is guaranteed to be complete and optimal provided that:
a) every step cost is at least some positive constant epsilon
b) the heuristic is admissible
c) the state space is a tree
d) all step costs are equal to 1
Q6. Iterative deepening search is run on a tree with branching factor b = 10 and the goal at depth d = 5. Counting the root as not generated, how many nodes does it generate in the worst case?
a) 111,110
b) 123,450
c) 1,111,111
d) 100,000
Q7. What is the time complexity of bidirectional search when both searches use breadth-first search?
a) O(b^d)
b) O(b^(2d))
c) O(b^(d/2))
d) O(bd)
Q8. If depth-limited search uses a limit l that is smaller than the depth d of the shallowest goal, the search is:
a) complete but not optimal
b) optimal but needs exponential space
c) complete and optimal
d) incomplete
Q9. Depth-first search is applied to the graph below, expanding successors in alphabetical order and testing for the goal when a node is selected for expansion. In what order are nodes selected?
A -> B, C B -> D, E C -> F E -> G (D, F and G have no successors; G is the goal)
a) A, B, D, E, G
b) A, B, C, D, E, F, G
c) A, C, F, B, E, G
d) A, B, E, G
Q10. Uniform cost search is run from S to goal G on the graph below. Which path does it return and with what cost?
S -> A (cost 1) S -> B (cost 4) A -> B (cost 2) A -> G (cost 12) B -> G (cost 5)
a) S-B-G with cost 9
b) S-A-B-G with cost 8
c) S-A-G with cost 13
d) S-A-B-G with cost 7
Q11. Why can depth-first tree search fail to find a solution even when one exists?
a) It needs too much memory
b) It always returns the deepest goal
c) It may follow an infinitely deep path and never backtrack
d) It cannot handle step costs
Q12. Iterative deepening search is often preferred because it combines:
a) the low time cost of DFS with the heuristic guidance of A*
b) the memory of BFS with the speed of DFS
c) the optimality of UCS with the speed of greedy search
d) the modest linear memory of DFS with the completeness of BFS
Q13. For a large search space where the depth of the solution is unknown and step costs are uniform, which uninformed strategy is generally recommended?
a) Iterative deepening search
b) Breadth-first search
c) Depth-first search
d) Depth-limited search with a small limit
Q14. Which condition is required to apply bidirectional search?
a) The heuristic must be consistent
b) Predecessors of states must be computable and the goal state must be explicitly known
c) The branching factor must be exactly 2
d) All step costs must be zero
Q15. BFS is run on a complete binary tree (b = 2) whose shallowest goal is at depth 3. In the worst case, including the root, how many nodes are generated up to depth 3?
a) 8
b) 7
c) 15
d) 31
Q16. When all step costs are equal, uniform cost search expands nodes in essentially the same order as:
a) depth-first search
b) depth-limited search
c) greedy best-first search
d) breadth-first search
Q17. What is the main purpose of the explored (closed) set in graph search?
a) To avoid re-expanding states that have already been reached, preventing redundant paths and loops
b) To store the heuristic values of all nodes
c) To keep the frontier sorted by cost
d) To record the solution path in reverse
Q18. What is the worst-case time complexity of uniform cost search, where C* is the optimal solution cost and epsilon is the minimum step cost?
a) O(b^d)
b) O(b^(1 + floor(C*/epsilon)))
c) O(bm)
d) O(b^(d/2))
Quick revision notes
- BFS: complete (finite b), optimal for equal step costs, time and space O(b^d).
- DFS: not complete in infinite spaces, not optimal, time O(b^m), space O(bm).
- UCS: expands lowest g(n); complete and optimal if step costs >= epsilon > 0; O(b^(1 + floor(C*/epsilon))).
- Depth-limited search: incomplete if l < d, non-optimal if l > d.
- IDS: complete, optimal for unit costs, time O(b^d), space O(bd); nodes generated = d*b + (d-1)*b^2 + ... + 1*b^d.
- Bidirectional search: O(b^(d/2)) time and space; needs computable predecessors and an explicit goal.
- Graph search keeps an explored set to avoid repeated states.
Frequently asked questions
Why is iterative deepening not very wasteful even though it repeats work?
In a tree with branching factor b, most nodes lie at the deepest level, so regenerating the shallower levels adds only a small fraction. For b = 10 the overhead is about 11 percent compared with BFS.
When is BFS not optimal?
BFS returns the shallowest goal, which is the cheapest only if all actions cost the same. With varying step costs a deeper path can be cheaper, and uniform cost search should be used instead.
What do b, d and m mean in search complexity?
b is the branching factor, the maximum number of successors of a node. d is the depth of the shallowest goal and m is the maximum length of any path in the state space, which may be infinite.
Comments
Post a Comment