Artificial Intelligence Multiple Choice Questions on “Uninformed Search and Exploration”.
1. What is the general term of Blind searching?
a) Informed Search
b) Uninformed Search
c) Informed & Unformed Search
d) Heuristic Search
Answer: b
Clarification: In case of uninformed search no additional information except the problem definition is given.
2. Strategies that know whether one non-goal state is “more promising” than another are called ___________
a) Informed & Unformed Search
b) Unformed Search
c) Heuristic & Unformed Search
d) Informed & Heuristic Search
Answer: d
Clarification: Strategies that know whether one non-goal state is “more promising” than another are called informed search or heuristic search strategies.
3. Which of the following is/are Uninformed Search technique/techniques?
a) Breadth First Search (BFS)
b) Depth First Search (DFS)
c) Bidirectional Search
d) All of the mentioned
Answer: d
Clarification: Several uninformed search techniques includes BFS, DFS, Uniform-cost, Depth-limited, Bidirectional search etc.
4. Which data structure conveniently used to implement BFS?
a) Stacks
b) Queues
c) Priority Queues
d) All of the mentioned
Answer: b
Clarification: Queue is the most convenient data structure, but memory used to store nodes can be reduced by using circular queues.
5. Which data structure conveniently used to implement DFS?
a) Stacks
b) Queues
c) Priority Queues
d) All of the mentioned
Answer: a
Clarification: DFS requires node to be expanded the one most recent visited, hence stack is convenient to implement.
6. The time and space complexity of BFS is (For time and space complexity problems consider b as branching factor and d as depth of the search tree.)
a) O(bd+1) and O(bd+1)
b) O(b2) and O(d2)
c) O(d2) and O(b2)
d) O(d2) and O(d2)
Answer: a
Clarification: We consider a hypothetical state space where every state has b successors. The root of the search tree generates b nodes at the first level, each of which generates b more nodes, for a total of b2 at the second level. Each of these generates b more nodes, yielding b3 nodes at the third level, and so on. Now suppose that the solution is at depth d. In the worst case, we would expand all but the last node at level d (since the goal itself is not expanded), generating bd+1- b nodes at level d+1.
7. Breadth-first search is not optimal when all step costs are equal, because it always expands the shallowest unexpanded node.
a) True
b) False
Answer: b
Clarification: Breadth-first search is optimal when all step costs are equal, because it always expands the shallowest unexpanded node. If the solution exists in shallowest node no irrelevant nodes are expanded.
8. uniform-cost search expands the node n with the __________
a) Lowest path cost
b) Heuristic cost
c) Highest path cost
d) Average path cost
Answer: a
Clarification: Uniform-cost search expands the node n with the lowest path cost. Note that if all step costs are equal, this is identical to breadth-first search.
9. Depth-first search always expands the ______ node in the current fringe of the search tree.
a) Shallowest
b) Child node
c) Deepest
d) Minimum cost
Answer: c
Clarification: Depth-first search always expands the deepest/leaf node in the current fringe of the search tree.
10. Breadth-first search always expands the ______ node in the current fringe of the search tree.
a) Shallowest
b) Child node
c) Deepest
d) Minimum cost
Answer: a
Clarification: Breadth-first search always expands the shallowest node in the current fringe of the search tree. Traversal is performed level wise.
11. Optimality of BFS is ___________
a) When there is less number of nodes
b) When all step costs are equal
c) When all step costs are unequal
d) None of the mentioned
Answer: b
Clarification: It always expands the shallowest unexpanded node.
12. LIFO is ______ where as FIFO is ________
a) Stack, Queue
b) Queue, Stack
c) Priority Queue, Stack
d) Stack. Priority Queue
Answer: a
Clarification: LIFO is last in first out – Stack. FIFO is first in first out – Queue.
13. When the environment of an agent is partially observable in search space following problem/problems could occur.
a) Sensorless problems: If the agent has no sensors at all, then (as far as it knows) it could be in one of several possible initial states, and each action might therefore lead to one of several possible successor states
b) Contingency problems: If the environment is partially observable or if actions are uncertain, then the agent’s percepts provide new information after each action. Each possible percept defines a contingency that must be planned for. A problem is called adversarial if the uncertainty is caused by the actions of another agent
c) Exploration problems: When the states and actions of the environment are unknown, the agent must act to discover them. Exploration problems can be viewed as an extreme case of contingency problems
d) All of the mentioned
Answer: d
Clarification: None.
14. For general graph, how one can get rid of repeated states?
a) By maintaining a list of visited vertices
b) By maintaining a list of traversed edges
c) By maintaining a list of non-visited vertices
d) By maintaining a list of non-traversed edges
Answer: a
Clarification: Other techniques are costly.
15. DFS is ______ efficient and BFS is __________ efficient.
a) Space, Time
b) Time, Space
c) Time, Time
d) Space, Space
Answer: a
Clarification: None.
16. The main idea of Bidirectional search is to reduce the time complexity by searching two way simultaneously from start node and another from goal node.
a) True
b) False
Answer: a
Clarification: The idea behind bidirectional search is to run two simultaneous searches-one forward from the initial state and the other backward from the goal, stopping when the two searches meet in the middle. The motivation is that bd/2 + bd/2 is much less than bd.
Global Education & Learning Series – Artificial Intelligence.