This set of Artificial Intelligence MCQs covers informed (heuristic) search and local search. It tests greedy best-first search and A*, admissibility and consistency of heuristics, heuristic dominance and effective branching factor, plus hill climbing, simulated annealing, local beam search and genetic algorithms. Several questions ask you to trace A* or compute heuristic values, which is common in GATE, UGC NET and university exams as well as in algorithm-heavy interview rounds.
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
- Greedy best-first search and A*
- Admissible and consistent heuristics
- Heuristic dominance and effective branching factor
- Hill climbing and its failure modes
- Simulated annealing
- Local beam search and genetic algorithms
Artificial Intelligence MCQs with answers and explanations
Q1. Greedy best-first search evaluates a node n using which function?
a) f(n) = g(n)
b) f(n) = g(n) + h(n)
c) f(n) = h(n)
d) f(n) = g(n) - h(n)
Q2. A heuristic h(n) is called admissible if:
a) it never overestimates the true cost of reaching the goal from n
b) it never underestimates the true cost of reaching the goal from n
c) it is always equal to zero
d) it decreases by exactly 1 along every edge
Q3. A heuristic is consistent (monotonic) if, for every node n and every successor n' reached by action a:
a) h(n) >= c(n, a, n') + h(n')
b) h(n) = h(n') for all n'
c) h(n') <= h(n) - 1
d) h(n) <= c(n, a, n') + h(n')
Q4. What is the relationship between consistency and admissibility of a heuristic with h(goal) = 0?
a) Every admissible heuristic is consistent
b) Every consistent heuristic is admissible, but not every admissible heuristic is consistent
c) The two properties are equivalent
d) The two properties are mutually exclusive
Q5. A* graph search that never re-opens closed nodes is guaranteed to find an optimal solution when the heuristic is:
a) merely admissible
b) greater than the true cost
c) consistent
d) constant for all nodes
Q6. A* search is run from S to G on the graph below. Which path is returned and what is its cost?
Edges: S->A (1), S->B (4), A->C (2), C->G (7), B->G (5) Heuristic: h(S)=6, h(A)=5, h(B)=4, h(C)=3, h(G)=0
a) S-A-C-G with cost 10
b) S-B-G with cost 9
c) S-A-C-G with cost 9
d) S-B-G with cost 8
Q7. For the 8-puzzle configuration below, what is the value of the Manhattan distance heuristic (sum of distances of tiles from their goal positions, blank excluded)?
Current state Goal state 2 8 3 1 2 3 1 6 4 8 _ 4 7 _ 5 7 6 5
a) 4
b) 6
c) 7
d) 5
Q8. Steepest-ascent hill climbing can get stuck without reaching the global optimum because of:
a) local maxima, plateaux and ridges
b) an inadmissible heuristic
c) using too much memory
d) exploring too many random moves
Q9. In simulated annealing, a move that worsens the objective by 2 (delta E = -2) is proposed when the temperature T = 4. What is the approximate probability of accepting it?
a) 0.14
b) 0.37
c) 0.61
d) 0.88
Q10. What happens to simulated annealing as the temperature T approaches zero?
a) It accepts every move with equal probability
b) It becomes a random walk
c) It turns into breadth-first search
d) It behaves like hill climbing, accepting only improving moves
Q11. Single-point crossover is applied to the two parent strings below. What is the offspring formed from the first 3 bits of Parent 1 and the remaining bits of Parent 2?
Parent 1: 11001010 Parent 2: 00110110 Crossover point: after bit 3
a) 11010110
b) 00101010
c) 11000110
d) 11110110
Q12. In fitness-proportionate (roulette wheel) selection, four individuals have fitness values 2, 3, 5 and 10. What is the probability of selecting the individual with fitness 5 in one spin?
a) 0.20
b) 0.25
c) 0.50
d) 0.05
Q13. How does local beam search with k states differ from running k independent random-restart hill climbs?
a) It keeps only the single best state at each step
b) It guarantees the global optimum
c) It uses backtracking when stuck
d) It selects the k best successors from the combined pool of all states' successors, sharing information
Q14. If the heuristic h(n) = 0 for every node, A* search becomes equivalent to:
a) uniform cost search
b) greedy best-first search
c) depth-first search
d) hill climbing
Q15. Random-restart hill climbing is described as complete with probability approaching 1 because:
a) it keeps every visited state in memory
b) it uses an admissible heuristic
c) with enough restarts from random states it eventually starts in the basin of a global optimum
d) it accepts downhill moves with a decreasing probability
Q16. Which statement about greedy best-first tree search is correct?
a) It is complete and optimal
b) It is neither complete nor optimal in general
c) It is optimal but not complete
d) It is complete in infinite spaces but not optimal
Q17. A* finds a solution at depth 2 after generating N = 6 nodes. Using N + 1 = 1 + b* + (b*)^2, what is the effective branching factor b*?
a) 2
b) 3
c) 1.5
d) 2.5
Q18. If h1 and h2 are both admissible heuristics for the same problem, which combination is guaranteed to be admissible and at least as informed as each?
a) h1 + h2
b) h1 * h2
c) max(h1, h2)
d) 2 * h1
Quick revision notes
- Greedy best-first: f = h; A*: f = g + h; UCS: f = g.
- Admissible: h(n) <= h*(n). Consistent: h(n) <= c(n, a, n') + h(n').
- Consistent implies admissible; A* tree search optimal if admissible, graph search optimal if consistent.
- h2 dominates h1 if h2(n) >= h1(n) for all n; Manhattan distance dominates misplaced tiles for the 8-puzzle.
- max of admissible heuristics is admissible; effective branching factor b* from N + 1 = 1 + b* + ... + (b*)^d.
- Simulated annealing accepts worse moves with probability e^(delta E / T).
- Genetic algorithm: selection, crossover, mutation; roulette wheel probability = fitness / total fitness.
Frequently asked questions
Why does an admissible heuristic make A* optimal?
Because h never overestimates, the f value of any node on the optimal path is at most the optimal cost C*. A suboptimal goal has f greater than C*, so A* will always expand the optimal path nodes before selecting a suboptimal goal.
What is the difference between hill climbing and simulated annealing?
Hill climbing only accepts improving moves and stops at local optima. Simulated annealing also accepts worse moves with a probability that shrinks as the temperature falls, which helps it escape local optima.
What does it mean for one heuristic to dominate another?
h2 dominates h1 if h2(n) >= h1(n) for every node and both are admissible. A* with the dominating heuristic never expands more nodes, so it is usually faster.
Comments
Post a Comment