AI Search Algorithms for GATE DA 2027: BFS, DFS, A*, Minimax & Alpha-Beta Pruning

By Piyush Wairale — Instructor, BS Data Science program at IIT Madras · IIT Madras alumnus · 10,000+ GATE students mentored · Last updated: August 2026 · Verified against the official IIT Madras GATE 2027 DA syllabus

Search is where the AI section starts, and it is the friendliest scoring territory in it: every algorithm has a fixed behaviour, every property (complete? optimal? how much memory?) has a definite answer, and the numericals — trace this A* expansion, count the pruned nodes — are mechanical once you have done ten of them. You have also already met half of it: the BFS and DFS from the DSA section reappear here wearing agent-and-goal clothing. This guide covers the full syllabus item — search: informed, uninformed, adversarial — and pairs with the GATE DA Artificial Intelligence Course & Test Series and the free playlist below.

Search Problems, Framed the GATE Way

A search problem has five parts: an initial state, a set of actions, a transition model (what each action does), a goal test, and a path cost. The solution is a path from start to goal; an optimal solution is a cheapest one. Every algorithm in this topic is a different rule for which frontier node to expand next — and each rule buys a different combination of four properties GATE asks about constantly: completeness (does it always find a solution when one exists?), optimality (is the solution found the cheapest?), time complexity and space complexity, written in terms of branching factor b, solution depth d and maximum depth m.

Uninformed Search: BFS, DFS, Uniform-Cost and Iterative Deepening

Breadth-first search expands the shallowest node first (a FIFO queue): complete when b is finite, optimal when all step costs are equal, but hungry — O(b^d) time and space, and the memory is what kills it in practice. Depth-first search dives deepest first (a LIFO stack): frugal at O(bm) space, but incomplete on infinite-depth trees and not optimal — it returns the first solution it stumbles into. Depth-limited search caps DFS at depth ℓ, fixing infinite descent but failing if the goal lies deeper. Iterative deepening (IDS) runs depth-limited search with ℓ = 0, 1, 2, … and gets the best of both worlds: BFS’s completeness and shallow-goal optimality with DFS’s O(bd) memory. The repeated re-expansion of upper levels costs surprisingly little — the deepest level dominates — so IDS stays O(b^d) in time; “why is iterative deepening not wasteful?” is a classic conceptual MCQ. Uniform-cost search (UCS) replaces the queue with a priority queue ordered by path cost g(n): it is BFS generalised to weighted graphs, complete and optimal whenever step costs are bounded below by a positive constant — and it is exactly Dijkstra’s algorithm in AI clothing, connecting back to the shortest-path item in the DSA syllabus.

This table is the exam. Memorise it as a story, not a grid: BFS trades memory for guarantees, DFS trades guarantees for memory, IDS refuses the trade, and UCS follows cost instead of depth.

Informed Search: Heuristics, Greedy Best-First and A*

Informed search uses a heuristic h(n) — an estimate of the cheapest cost from n to a goal. Two properties decide everything. Admissibility: h never overestimates the true cost (h(n) ≤ h*(n)); an admissible heuristic is “optimistic”. Consistency (monotonicity): h(n) ≤ c(n, n′) + h(n′) for every successor n′ — a triangle inequality along edges. Consistency implies admissibility; the converse fails. The straight-line distance in a route map is the canonical admissible-and-consistent example.

Greedy best-first search expands the node with the smallest h(n) alone. It can be fast, but it is neither complete (can loop) nor optimal — it chases what looks close. A* repairs it by expanding the node with the smallest f(n) = g(n) + h(n) — cost so far plus estimated cost to go. The theorem GATE tests more than any other in this topic: A* is optimal if h is admissible (tree search) or consistent (graph search). Two more facts worth marks: with h(n) = 0 for all n, A* reduces to uniform-cost search; and among admissible heuristics, a more informed (larger, still admissible) heuristic expands no more nodes — “h₂ dominates h₁” questions come straight from this.

Worked A* trace

Notice what made A* right: it kept comparing total estimated cost, so the cheap-looking direct hop S→B (h=2) lost to the genuinely cheaper route through A. When a GATE question asks “in what order does A* expand nodes?”, build exactly this table of f-values step by step — and watch for ties, which the question’s tie-breaking rule resolves.

Adversarial Search: Game Trees, Minimax and Alpha-Beta Pruning

When the environment contains an opponent, search becomes a game. In a two-player zero-sum game, minimax assigns a value to every node of the game tree: MAX levels take the maximum of their children’s values, MIN levels take the minimum, and leaf values come from a utility (or evaluation) function. The root’s minimax value is the best outcome MAX can guarantee against optimal opposition. Complexity is O(b^m) time for branching factor b and depth m — which is why chess programs cannot minimax to the end of the game and instead cut off at a depth and evaluate.

Alpha-beta pruning computes the exact same root value while skipping provably irrelevant branches. It carries two bounds down the tree: α, the best value MAX can guarantee so far, and β, the best value MIN can guarantee. Whenever α ≥ β at a node, its remaining children cannot influence the root — prune them. The facts GATE tests, in order of frequency: (1) pruning never changes the minimax value, only the work done; (2) with perfect move ordering (best child first), alpha-beta examines about O(b^(m/2)) nodes — it can search roughly twice as deep as plain minimax in the same time; (3) with worst-case ordering it prunes nothing and degenerates to O(b^m); (4) the amount pruned depends on the order children are visited — which is why the same tree gives different pruned-node counts left-to-right versus right-to-left, a favourite 2-mark setup.

Mini worked example. Root is MAX with two children L and R (each a MIN node with two leaves). L’s leaves: 3, 5 → L’s value is min(3,5) = 3, and α at the root becomes 3. Descend into R: its first leaf is 2, so R’s value will be min(2, …) ≤ 2 < α = 3 — the second leaf of R is pruned without being examined, and the root’s value is max(3, ≤2) = 3. One leaf skipped out of four; on deeper trees with good ordering, the savings compound dramatically. Practise marking α and β at every node on 3-level trees until the update rules are automatic.

How GATE Actually Tests Search

• Property MCQ/MSQ (1–2 marks): which algorithms are complete/optimal under which conditions — the uninformed comparison table verbatim.
• Expansion-order traces (2 marks): the order A* (or UCS, or greedy) expands nodes on a small labelled graph; build the f-value table.
• Heuristic checks (1–2 marks): is a given h admissible? consistent? Which of two admissible heuristics expands fewer nodes?
• Alpha-beta counting (2 marks): how many leaves are examined / pruned on a given tree with left-to-right ordering.
• Minimax value computation (1–2 marks): compute the root value of a 2–3 level game tree; occasionally with a twist (a chance node or a changed leaf).
• Reduction facts (1 mark): A* with h=0 is UCS; UCS with unit costs is BFS; alpha-beta equals minimax in value.

The 2-Week Search Study Plan

1. Days 1–3: problem formulation + the uninformed five; reproduce the comparison table from memory; BFS/DFS refreshers from the DSA guide.
2. Days 4–6: heuristics — admissibility and consistency proofs on small examples; greedy’s failure cases.
3. Days 7–9: A* traces daily; dominance questions; the h=0 and unit-cost reductions.
4. Days 10–12: minimax values and alpha-beta marking on 3-level trees; pruned-node counts in both orderings.
5. Days 13–14: mixed PYQs from GATE DA and GATE CS/AI; error-log review; then continue to logic and reasoning under uncertainty to finish the AI section.

FAQs on AI Search for GATE DA

Search rewards the table-and-trace style of preparation: one comparison table, two trace recipes (f-values for A*, α/β marking for pruning), and a handful of reduction facts. Drill those and the search questions in GATE DA become fixed marks. Continue the AI section with our reasoning under uncertainty guide, and see the full GATE DA syllabus breakdown for the complete roadmap.