GATE CS & DA Preparation Guide Module 9 – Machine learning and AI (DA sections 6-7)
AI search: uninformed, informed and adversarial
Search for GATE DA: BFS, DFS, uniform-cost, iterative deepening, greedy and A* traced on one graph, heuristic tests, and minimax with alpha-beta pruning.
What you will learn
- Trace BFS, DFS, uniform-cost, depth-limited and iterative-deepening search, including the expansion order
- Run greedy best-first and A* search and test heuristics for admissibility and consistency
- Explain how tree or graph search and the timing of the goal test change what a question counts
- Evaluate game trees with minimax and alpha-beta pruning and count the pruned leaves
Before you start
What you’ll learn · Before you start
What you will learn
- Trace BFS, DFS, uniform-cost, depth-limited and iterative-deepening search, including the expansion order
- Run greedy best-first and A* search and test heuristics for admissibility and consistency
- Explain how tree or graph search and the timing of the goal test change what a question counts
- Evaluate game trees with minimax and alpha-beta pruning and count the pruned leaves
Before you start
On this page
From S to the goal G on one small graph, breadth-first search returns a route of cost 13, while A* returns one of cost 9 after expanding only six nodes. Section 7 of the GATE DA syllabus starts with search in three kinds: uninformed, informed and adversarial. Uninformed search uses only the graph and its edge costs. Breadth-first search (BFS) expands the shallowest node first, depth-first search (DFS) the deepest, uniform-cost search (UCS) the node with the cheapest path so far, and iterative deepening search (IDS) runs depth-limited DFS with growing limits. Informed search adds a heuristic h(n), an estimate of the cost left to the goal. Greedy best-first search expands the node with the smallest h, and A* the node with the smallest f = g + h. Adversarial search scores game trees: minimax backs values up from the leaves, and alpha-beta pruning skips branches that cannot change the answer.
Not affiliated
MySmartCoPilot is a separate site from IIT Madras, IISc and the IITs, which alone decide what GATE asks.
The frontier decides the algorithm
Read the three tables row by row. The searches differ only in how their frontier: The nodes a search has generated but not yet expanded. Its order decides the search: a queue gives BFS, a stack DFS, and a priority queue on g, h or g + h gives UCS, greedy search or A*. orders the nodes waiting to be expanded, and that order decides whether each one is complete and optimal, and what it costs.
| Criterion | BFS | DFS |
|---|---|---|
| Frontier | First in, first out: a queue | Last in, first out: a stack |
| Complete | Yes, if b is finite | On finite graphs that check repeats |
| Optimal | When all steps cost the same | No |
| Time, space | O(b^d), O(b^d) | O(b^m), O(bm) |
| Criterion | IDS | UCS |
|---|---|---|
| Frontier | DFS with limits 0, 1, 2 … | A priority queue on g |
| Complete | Yes | Yes, with step costs above 0 |
| Optimal | When all steps cost the same | Yes |
| Time, space | O(b^d), O(bd) | Grows with C*/ε |
| Criterion | Greedy | A* |
|---|---|---|
| Frontier | A priority queue on h | A priority queue on g + h |
| Complete | On finite graphs that check repeats | Yes, with step costs above 0 |
| Optimal | No | Yes, if h is admissible (tree search) |
| Time, space | O(b^m) at worst | As UCS at worst, when h = 0 |
Here b is the branching factor: b, the number of children each node of a search tree has (the largest number, when it varies). A uniform tree has 1 + b + b² + … + b^d nodes down to depth d., d the depth of the shallowest goal, m the maximum depth, C* the cheapest cost and ε the smallest step cost. Tree search may expand the same state many times, while graph search: A search that keeps a set of the states it has expanded and expands each at most once. Tree search keeps no such set, so it may expand the same state again through another path. keeps a set of expanded states and expands each at most once. Questions count expanded or generated nodes, with the goal tested on generation or on expansion.
Checkpoint
Check: The frontier and tree or graph search
Uninformed searches differ in what they minimise
The graph that all six searches run on
Text description of the diagram
Eight nodes with their heuristic values: S (h = 8), A (h = 9), B (h = 5), C (h = 4), D (h = 6), E (h = 3), F (h = 1) and the goal G (h = 0).
Undirected edges with their costs: S–A 1, S–B 4, S–C 5, A–D 3, A–E 6, B–E 2, C–G 8, D–G 7, E–F 2 and F–G 1.
Three routes matter. S–C–G has the fewest edges, 2, but costs 13. S–A–D–G costs 11. S–B–E–F–G has 4 edges and costs 9, the cheapest path.
Every search below runs from S to G with the same conventions, which any exam answer should state: neighbours in alphabetical order, ties broken alphabetically, the goal tested when a node is expanded, and graph search.
| Search | Expanded, in order | Path | Cost |
|---|---|---|---|
| BFS | S A B C D E G | S–C–G | 13 |
| DFS | S A D G | S–A–D–G | 11 |
| UCS | S A B D C E F G | S–B–E–F–G | 9 |
| IDS | 13 expansions over limits 0, 1 and 2 | S–C–G | 13 |
BFS and IDS return the path with the fewest edges, which is not the cheapest. DFS dives through A and D and pays 11. Step through BFS, then UCS, which is Dijkstra’s algorithm run from S. Both figures run until every node is reached:
- being compared or looked at
- being moved or written
- in its final place
- the key, pivot or target
- visited or ruled out
Pseudo-code
-
queue ← [start]; seen ← {start}; dist(start) ← 0 -
while the queue is not empty: -
u ← dequeue -
for each neighbour v of u: -
if v is not seen: seen ← seen + v; dist(v) ← dist(u) + 1; enqueue v
Breadth-first search from S: visit the nodes in order of distance (in edges) from S, using a queue. d is that distance.
When it finishes: Visit order: S A B C D E G F.
Try your own input
- being compared or looked at
- being moved or written
- in its final place
- the key, pivot or target
- visited or ruled out
Pseudo-code
-
dist(start) ← 0; dist(v) ← ∞ for every other v; add start to the queue -
while the queue is not empty: -
u ← the queued node with the smallest dist; settle u -
for each edge u → v with weight w: -
if dist(u) + w < dist(v): dist(v) ← dist(u) + w; prev(v) ← u; queue v
| Node | dist | prev |
|---|---|---|
| A | ∞ | — |
| B | ∞ | — |
| C | ∞ | — |
| D | ∞ | — |
| E | ∞ | — |
| F | ∞ | — |
| G | ∞ | — |
| S | 0 | — |
Shortest distances from S. Every node starts at ∞ except S at 0. Each round settles the queued node with the smallest distance: with no negative weights, no later path can beat it.
When it finishes: A: 1, B: 4, C: 5, D: 4, E: 6, F: 8, G: 9, S: 0.
Try your own input
Checkpoint
Check: BFS, DFS, uniform-cost and iterative deepening
Greedy search and A* add a heuristic
The same graph carries h1, the h beside each node in the figure above:
| Search | Expanded, in order | Path | Cost |
|---|---|---|---|
| Greedy | S C G | S–C–G | 13 |
| A* | S B C E F G | S–B–E–F–G | 9 |
Greedy search is drawn to C, whose h of 4 looks closest to the goal, and pays 13 for S–C–G, whose last edge alone costs 8. UCS and A* both return the cheapest path, cost 9, but A* expands 6 nodes against 8: A’s f of 1 + 9 = 10 exceeds the cost 9, so A* never expands A, nor D behind it. Step through A*:
The drawing shows the whole scene; its 6 steps are listed below.
Every step as text
- Expand S. S has g = 0 and h = 8. Its neighbours enter the frontier with f = g + h, A at 1 + 9 = 10, B at 4 + 5 = 9 and C at 5 + 4 = 9.
- Expand B. B and C tie at f = 9, and the tie goes to B, alphabetically first. B adds E at g = 4 + 2 = 6, f = 6 + 3 = 9.
- Expand C. C and E tie at 9, and C goes first. C adds G through its costly edge, g = 5 + 8 = 13 and f = 13, which waits in the frontier.
- Expand E. E is next at f = 9. It adds F at g = 6 + 2 = 8, f = 8 + 1 = 9, and A again at g = 12, far worse than A's entry at 10.
- Expand F. F, at f = 9, adds G at g = 8 + 1 = 9 and f = 9 + 0 = 9, better than the entry of 13 through C.
- Expand the goal. G at f = 9 comes out next and passes the goal test, so A* returns S–B–E–F–G at cost 9 after six expansions. A, at f = 10, was never expanded, nor D behind it.
Of two admissible heuristics, the one that is at least as large everywhere dominates the other and never needs more expansions.
# Six searches on one invented graph from S to G: BFS, DFS, uniform-cost, iterative deepening, greedy best-first and A*.
# Conventions (state them in any exam answer): undirected edges; neighbours in alphabetical order; ties go to the
# alphabetically earlier node; the goal test happens when a node is expanded; graph search (no node is expanded twice).
import heapq
from collections import deque
edges = {("S", "A"): 1, ("S", "B"): 4, ("S", "C"): 5, ("A", "D"): 3, ("A", "E"): 6,
("B", "E"): 2, ("C", "G"): 8, ("D", "G"): 7, ("E", "F"): 2, ("F", "G"): 1}
h = {"S": 8, "A": 9, "B": 5, "C": 4, "D": 6, "E": 3, "F": 1, "G": 0}
graph = {}
for (u, v), c in edges.items():
graph.setdefault(u, {})[v] = c
graph.setdefault(v, {})[u] = c
def cost(path):
return sum(graph[a][b] for a, b in zip(path, path[1:]))
def report(name, order, path):
print(f"{name:<9} expanded {' '.join(order):<17} path {'-'.join(path)}, cost {cost(path)}, {len(path) - 1} edges")
def bfs(start, goal):
frontier, reached, order = deque([[start]]), {start}, []
while frontier:
path = frontier.popleft()
order.append(path[-1])
if path[-1] == goal:
return order, path
for n in sorted(graph[path[-1]]):
if n not in reached:
reached.add(n)
frontier.append(path + [n])
def dfs(start, goal):
frontier, expanded, order = [[start]], set(), []
while frontier:
path = frontier.pop()
if path[-1] in expanded:
continue
expanded.add(path[-1])
order.append(path[-1])
if path[-1] == goal:
return order, path
for n in sorted(graph[path[-1]], reverse=True): # pushed in reverse, so the first in order is popped first
if n not in expanded:
frontier.append(path + [n])
def best_first(start, goal, priority):
frontier, expanded, order = [(priority(0, start), start, [start], 0)], set(), []
while frontier:
_, node, path, g = heapq.heappop(frontier)
if node in expanded:
continue
expanded.add(node)
order.append(node)
if node == goal:
return order, path
for n in sorted(graph[node]):
if n not in expanded:
g2 = g + graph[node][n]
heapq.heappush(frontier, (priority(g2, n), n, path + [n], g2))
def ids(start, goal):
order = []
for limit in range(len(graph)):
def dls(path, depth):
order.append(path[-1])
if path[-1] == goal:
return path
if depth == limit:
return None
for n in sorted(graph[path[-1]]):
if n not in path: # no cycles along the current path
found = dls(path + [n], depth + 1)
if found:
return found
return None
found = dls([start], 0)
if found:
return order, found, limit
report("BFS", *bfs("S", "G"))
report("DFS", *dfs("S", "G"))
report("UCS", *best_first("S", "G", lambda g, n: g))
order, path, limit = ids("S", "G")
report("IDS", order, path)
print(f" (found at depth limit {limit}; {len(order)} expansions over all the iterations)")
report("Greedy", *best_first("S", "G", lambda g, n: h[n]))
report("A*", *best_first("S", "G", lambda g, n: g + h[n]))Output
BFS expanded S A B C D E G path S-C-G, cost 13, 2 edges
DFS expanded S A D G path S-A-D-G, cost 11, 3 edges
UCS expanded S A B D C E F G path S-B-E-F-G, cost 9, 4 edges
IDS expanded S S A B C S A D E B E C G path S-C-G, cost 13, 2 edges
(found at depth limit 2; 13 expansions over all the iterations)
Greedy expanded S C G path S-C-G, cost 13, 2 edges
A* expanded S B C E F G path S-B-E-F-G, cost 9, 4 edges
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 search_trace.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
It prints every expansion of all six searches.
Checkpoint
Check: Greedy best-first search and A*
A heuristic must never overestimate
A heuristic is admissible heuristic: A heuristic that never overestimates: h(n) is at most the true cheapest cost from n to a goal, at every node. h = 0 is admissible but gives no guidance. when it never exceeds the true cost to the goal. At A, h = 9 and the cheapest route A–E–F–G costs 6 + 2 + 1 = 9, so the bound holds with equality. A heuristic is consistent heuristic: A heuristic with h(u) ≤ c(u, v) + h(v) on every edge and h = 0 at goals. Every consistent heuristic is admissible, but an admissible one can break the inequality on some edge. when h(u) ≤ c(u, v) + h(v) on every edge, which is stronger than admissible: h1 is consistent on the edge A–D because 9 ≤ 3 + h(D) = 3 + 6. Step through the tests:
The drawing shows the whole scene; its 6 steps are listed below.
Every step as text
- The heuristic h1. These five nodes of the graph carry h1, the estimate of the cost still to go. A heuristic is admissible when it never exceeds the true cheapest cost to G.
- Admissible at A. From A, the cheapest route to G is A–E–F–G, 6 + 2 + 1 = 9; A–D–G costs 10. h(A) = 9 is not above 9, so h1 is admissible at A, with equality.
- Consistent on A–D. Consistency asks h(u) ≤ c(u, v) + h(v) on every edge. On A–D, 9 ≤ 3 + 6, so it holds.
- Consistent on E–F. On E–F, h(E) = 3 ≤ 2 + h(F) = 3. It holds with equality.
- Consistent on F–G. On F–G, h(F) = 1 ≤ 1 + 0, and h(G) = 0 at the goal, which consistency needs as well.
- Why consistency is stronger. Adding the inequalities along A–E–F–G gives h(A) ≤ 6 + 2 + 1 + h(G) = 9, the true cost. A consistent heuristic therefore never overestimates; an admissible one can still break the triangle on some edge.
A* tree search returns a cheapest path whenever h is admissible; A* graph search, which never expands a node twice, needs a consistent heuristic for the same guarantee.
Checkpoint
Check: Admissible and consistent heuristics
Minimax backs values up, and alpha-beta skips what cannot matter
In a game tree, MAX moves at the root and MIN replies. Take two MIN nodes with the leaves 4 and 6, and 1 and 7. Minimax gives them the values 4 and 1, and MAX picks 4. alpha-beta pruning: Minimax search that keeps two bounds, α for MAX and β for MIN, and stops exploring a node once they cross. It returns the minimax value while skipping branches that cannot change it. search reaches the same 4 without looking at the leaf 7: once the second MIN node has seen 1, it is worth at most 1, and MAX already has 4. Step through it:
The drawing shows the whole scene; its 7 steps are listed below.
Every step as text
- The tree. MAX moves at the root and MIN replies; the leaves are scores for MAX. Alpha-beta reads the leaves from left to right and keeps α, the value MAX can already be sure of.
- First leaf. MIN 1 reads its first leaf, 4. MIN takes the smallest value, so MIN 1 is worth at most 4.
- Second leaf. The second leaf is 6, and MIN prefers 4, so MIN 1 is worth exactly 4.
- α rises to 4. By choosing MIN 1, MAX is sure of 4, so α = 4 at the root.
- MIN 2 reads 1. MIN 2 reads its first leaf, 1, so MIN 2 is worth at most 1, which is below α = 4.
- The last leaf is skipped. Whatever the last leaf holds, MIN 2 is worth at most 1, and MAX will not choose it over 4. The leaf 7 is never read.
- The value. MAX picks MIN 1, and the root's value is 4, the minimax value, after reading three of the four leaves.
Alpha-beta pruning keeps two bounds, α for MAX and β for MIN, and stops exploring a node once they cross. Move ordering decides how much alpha-beta prunes. Expectimax replaces MIN nodes by chance nodes that average their outcomes.
Checkpoint
Check: Minimax and alpha-beta on a small tree
Practise: search in GATE’s formats
Practise the five ideas, starting with the one you know least.
Practice that adapts to you
Practise this lesson
12 questions about 11 ideas of this lesson. Each answer is explained at once, and what you get right is kept in this browser.
Expansion counts, heuristic tests and A* failures, worked Pro: opens with a Pro, Premium or Ultimate pass
The same graph gives different counts under different conventions, and a heuristic can quietly break A*. This part counts both ways, tests three heuristics against the true costs and reproduces the two ways A* returns a worse path.
In this part:
- Tree search or graph search, and when the goal is tested
- Iterative deepening, expansion by expansion
- Testing heuristics against true costs
- Two ways A* returns a worse path, reproduced
- Time and space in numbers: b = 10 and d = 5
- Your turn: trace A* graph search
- Trace A* graph search, expansion by expansion
1 diagram · 2 runnable examples (Python) · 1 exercise with sample tests · about 10 minutes
Opening this part with your pass…
This part opens with any MySmartCoPilot pass.
- Pro pass · 1 week₹79$2.99
- 30 days₹179$5.99
- 1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so this part can’t be opened at the moment. The free part above stands on its own. If you have a pass, enter your licence key.
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
Minimax and alpha-beta on a 27-leaf tree, leaf by leaf Pro: opens with a Pro, Premium or Ultimate pass
Game-tree questions ask for a value, the best move and how many leaves alpha-beta skips. This part works one tree of depth 3 and branching factor 3 in full, then shows what move ordering and chance nodes change.
In this part:
- Minimax values backed up level by level
- Alpha-beta traced with α and β at every node
- Move ordering: from 17 leaves to 11, with Knuth and Moore’s count
- Expectimax for chance nodes
- A ten-minute set, with answers
1 diagram · 1 runnable example (Python) · about 8 minutes
Opening this part with your pass…
This part opens with any MySmartCoPilot pass.
- Pro pass · 1 week₹79$2.99
- 30 days₹179$5.99
- 1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so this part can’t be opened at the moment. The free part above stands on its own. If you have a pass, enter your licence key.
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
Interview questions
-
Fresher · Warm-up
What is the difference between an admissible and a consistent heuristic, and which does A* graph search need?
An admissible heuristic never overestimates: at every node, h(n) is at most h*(n), the true cheapest cost from n to a goal. A consistent heuristic obeys a triangle inequality on every edge, h(u) ≤ c(u, v) + h(v), with h = 0 at goals. Consistency is the stronger condition: adding the inequality up along a cheapest path shows that a consistent heuristic is admissible, but an admissible one can break the inequality on some edge. A* tree search returns a cheapest path whenever h is admissible. A* graph search, which never expands a node twice, needs a consistent heuristic for the same guarantee. In the lesson's graph, h(A) = 9 equals the true cost from A, and the edge A–D satisfies 9 ≤ 3 + 6.
-
Fresher to mid
On a road map, breadth-first search and uniform-cost search return different routes between two towns. Explain why with a small example, say when the two always agree, and say which one you would use in a route planner.
-
Fresher to mid
Your A* route planner returns a route of cost 12 although the cheapest route costs 10. List the possible causes, show how the trace tells them apart, and fix each one.
-
Fresher to mid
Alpha-beta search on your game tree prunes almost nothing. Why can that happen, how many leaves can perfect move ordering save for branching factor b and depth d, and how do game programs order moves in practice?
Key takeaways
- The frontier decides the search: a queue gives BFS, a stack DFS, g gives UCS, h greedy search and g + h A*.
- BFS and IDS find the path with the fewest edges; UCS finds the cheapest path, and so does A* with a consistent heuristic.
- Admissible means never overestimating; consistent means h(u) ≤ c(u, v) + h(v) on every edge.
- Minimax backs values up from the leaves, and alpha-beta returns the same value while skipping branches.
Terms in this lesson
- admissible heuristic
- A heuristic that never overestimates: h(n) is at most the true cheapest cost from n to a goal, at every node. h = 0 is admissible but gives no guidance.
- alpha-beta pruning
- Minimax search that keeps two bounds, α for MAX and β for MIN, and stops exploring a node once they cross. It returns the minimax value while skipping branches that cannot change it.
- branching factor
- b, the number of children each node of a search tree has (the largest number, when it varies). A uniform tree has 1 + b + b² + … + b^d nodes down to depth d.
- consistent heuristic
- A heuristic with h(u) ≤ c(u, v) + h(v) on every edge and h = 0 at goals. Every consistent heuristic is admissible, but an admissible one can break the inequality on some edge.
- frontier
- The nodes a search has generated but not yet expanded. Its order decides the search: a queue gives BFS, a stack DFS, and a priority queue on g, h or g + h gives UCS, greedy search or A*.
- graph search
- A search that keeps a set of the states it has expanded and expands each at most once. Tree search keeps no such set, so it may expand the same state again through another path.
References
- GATE 2027 syllabus, Data Science and Artificial Intelligence (section 7, AI) (Indian Institute of Technology Madras (GATE 2027))
- A formal basis for the heuristic determination of minimum cost paths (Hart, Nilsson and Raphael) (IEEE Transactions on Systems Science and Cybernetics)
- An analysis of alpha-beta pruning (Knuth and Moore) (Artificial Intelligence (Elsevier))
- Depth-first iterative-deepening: an optimal admissible tree search (Korf) (Artificial Intelligence (Elsevier))
- A note on two problems in connexion with graphs (Dijkstra) (Numerische Mathematik (Springer))
- heapq: heap queue algorithm (Python Software Foundation)
- collections: deque objects (Python Software Foundation)
Related tools
Report a problem with this lesson
Kept only in this browser. Your Learn progress