GATE DA

Search

Uninformed, informed and adversarial

Search is how an agent finds a sequence of actions from a start state to a goal, and how it picks a move against an opponent. These notes give, for each algorithm, its completeness, optimality and complexity with the conditions they need, the exact procedure for tracing the order of expansion, the tests for admissible and consistent heuristics, and how to find the root value and the pruned branches in minimax and alpha-beta. Conventions (tie-breaking, when the goal test is applied, the alpha-beta cut-off) are stated so a trace can be reproduced exactly.

7 previous-year questions · 7 solved · 5 practice questions

Problem formulation and how algorithms are judged

A search problem is defined by five things: an initial state, the actions available in each state, a transition model (the state an action leads to), a goal test, and a path cost that adds up step costs. A solution is a path from the initial state to a goal state; an optimal solution has the least path cost. The search builds a tree of nodes from the initial state. Expanding a node means generating all its children; the set of generated but not yet expanded nodes is the frontier. The strategies below differ in which frontier node they expand next.

Symbols used for complexity

$b$ = branching factor (maximum number of children of a node)
$d$ = depth of the shallowest goal node (root has depth 0)
$m$ = maximum depth of the search tree (may be infinite)
$ℓ$ = depth limit in depth-limited search
$C^{*}$ = cost of an optimal solution, $ε$ = smallest step cost (assumed greater than 0)

The four properties asked about

Completeness: is a solution always found when one exists?
Optimality: is the first solution returned a least-cost one?
Time complexity: number of nodes generated.
Space complexity: maximum number of nodes held in memory at once.

Conventions used in these notes. Step costs are non-negative. Heuristic values are non-negative and $h (goal) = 0$ . Ties between frontier nodes are broken alphabetically (by node label) unless a question says otherwise. For uniform-cost search, greedy best-first search and A* the goal test is applied when a node is expanded (removed from the frontier), not when it is generated; for uniform-cost search and A* this is what makes them optimal. For breadth-first search both rules are in use, so its complexity is given for each. In alpha-beta, the remaining children are pruned as soon as $α \geq β$ . If a question uses a different rule, follow the question.

Uninformed search

Uninformed (blind) strategies use only the problem definition. They differ in the data structure that holds the frontier: a queue (FIFO) gives breadth-first search, a stack (LIFO) gives depth-first search, and a priority queue ordered by path cost $g (n)$ gives uniform-cost search.

Procedure for tracing breadth-first and depth-first search

Put the start node on the frontier.
Remove the next node: the oldest one for BFS, the newest one for DFS.
With the goal test at expansion, test the removed node and stop if it is a goal. Otherwise generate its children in the stated order (alphabetical unless told otherwise).
With the goal test at generation (the early test), test each child as it is generated and stop as soon as a goal appears. The order in which nodes are expanded is the same under both rules; only the point where the search stops, and so the count of nodes, changes.
For BFS append the children at the back; for DFS push them so that the first child in the order is popped first (so push in reverse order on a stack).
Do not add a state that is already on the current path (or already visited, in graph search) if the question says so.

Algorithm	Complete?	Optimal?	Time	Space
Breadth-first	Yes, if $b$ is finite	Yes, if all step costs are equal	$O (b^{d})$ with the goal test at generation; $O (b^{d + 1})$ at expansion	Same as time
Uniform-cost	Yes, if every step cost is at least $ε > 0$ and $b$ is finite	Yes	$O (b^{1 + ⌊ C^{*} / ε ⌋})$	$O (b^{1 + ⌊ C^{*} / ε ⌋})$
Depth-first	No in tree search (infinite depth or loops); yes in graph search on a finite state space, or tree search on a finite tree	No	$O (b^{m})$	$O (bm)$ (tree search)
Depth-limited (limit $ℓ$ )	Yes if $ℓ \geq d$ (finite $b$ ); no if $ℓ < d$	No	$O (b^{ℓ})$	$O (b ℓ)$
Iterative deepening	Yes, if $b$ is finite	Yes, if all step costs are equal	$O (b^{d})$	$O (b d)$
Bidirectional (BFS from both ends)	Yes, if $b$ is finite	Yes, if all step costs are equal	$O (b^{d /2})$	$O (b^{d /2})$

BFS finds the shallowest goal, which is the cheapest only when every step costs the same. Uniform-cost search expands nodes in non-decreasing order of $g (n)$ and so returns the cheapest goal; with zero-cost loops it can run forever, which is why $ε > 0$ is required. For BFS, the goal test at generation gives $O (b^{d})$ and the goal test at expansion gives $O (b^{d + 1})$ , because with the late test every child of the depth- $d$ nodes expanded before the goal is also generated. Check which rule a question uses before counting nodes.

Iterative deepening runs depth-limited DFS with $ℓ = 0, 1, 2, \dots$ until a goal is found. It combines BFS's completeness and optimality (equal step costs) with DFS's linear memory. For $b \geq 2$ the repeated work is small, because most nodes of a uniform tree lie at the deepest level.

NODES GENERATED BY ITERATIVE DEEPENING (WORST CASE)

N_{IDS} = i = 0 \sum d (d + 1 - i) b^{i} = (d + 1) + d b + (d - 1) b^{2} + \dots + 1 \cdot b^{d}

Uniform tree with branching factor $b$ , goal at depth $d$ , the last iteration generating every node to depth $d$ , root counted in every iteration. Nodes at depth $i$ are generated $d + 1 - i$ times.

BOUND ON THE ITERATIVE-DEEPENING OVERHEAD

N_{IDS} < (\frac{b}{b - 1})^{2} b^{d} (b \geq 2)

From the sum above with $k = d - i$ : $N_{IDS} = b^{d} \sum_{k = 0}^{d} (k + 1) b^{- k} < b^{d} (1 - 1/ b)^{- 2}$ . For $b = 2$ the factor is 4; for $b = 10$ it is about 1.23.

Bidirectional search runs two searches, forward from the start and backward from the goal, and stops when their frontiers meet. Each search goes only to about depth $d /2$ , which is where $O (b^{d /2})$ comes from. It needs a single explicit goal state and a way to compute predecessors.

EXAM TIP

DFS on a graph with cycles and no visited check can loop forever, so it is not complete even when a goal is one step away. Depth-limited search is the standard fix, but a limit below $d$ misses the goal, so it is incomplete.

Informed search: greedy best-first and A*

Informed search uses a heuristic $h (n)$ , an estimate of the cheapest cost from node $n$ to a goal, with $h (goal) = 0$ . Write $g (n)$ for the path cost from the start to $n$ found so far, and $h^{*} (n)$ for the true cheapest cost from $n$ to a goal.

A* EVALUATION FUNCTION

f (n) = g (n) + h (n)

A* always expands the frontier node with the smallest $f$ . Greedy best-first search uses $f (n) = h (n)$ alone; uniform-cost search is A* with $h \equiv 0$ .

ADMISSIBLE HEURISTIC

0 \leq h (n) \leq h^{*} (n) for every node n

Never overestimates the true remaining cost. Enough for A* to be optimal in tree search, and in graph search when cheaper paths re-open expanded nodes.

CONSISTENT (MONOTONE) HEURISTIC

h (n) \leq c (n, a, n^{'}) + h (n^{'}) for every node n and successor n^{'}, h (goal) = 0

A triangle inequality on estimates. Every consistent heuristic is admissible; the converse is false. Along any path $f$ never decreases when $h$ is consistent.

A* procedure (graph search with re-opening of cheaper paths)

Frontier = {start}, with $g = 0$ and $f = h (start)$ .
Remove the frontier node with the smallest $f$ ; break ties alphabetically. If it is a goal, stop and return its path and cost.
Otherwise expand it. For each successor compute $g = g (parent) + step cost$ and $f = g + h$ .
If the successor is new, add it. If it is already on the frontier with a larger $g$ , replace it with the cheaper path. If it was already expanded with a larger $g$ , re-open it (never needed when $h$ is consistent).
Repeat.

Why A* is optimal (tree search, admissible $h$ ). Suppose the goal first removed from the frontier is a suboptimal goal $G_{2}$ with $f (G_{2}) = g (G_{2}) > C^{*}$ . Some node $n$ on an optimal path is still on the frontier, and $f (n) = g (n) + h (n) \leq g (n) + h^{*} (n) = C^{*}$ because $h$ is admissible. Since $f (n) \leq C^{*} < f (G_{2})$ , $n$ would be removed before $G_{2}$ , a contradiction. With a consistent $h$ , $f$ never decreases along a path, so nodes are expanded in non-decreasing order of $f$ . The first time a node is expanded its $g$ is already the cheapest, so graph-search A* needs no re-opening. A* then expands every node with $f (n) < C^{*}$ , possibly some with $f (n) = C^{*}$ , and none with $f (n) > C^{*}$ . With an admissible but inconsistent $h$ the first of these can fail, because $f$ can drop along a path.

Algorithm	Orders the frontier by	Complete?	Optimal?
Uniform-cost	$g (n)$	Yes ( $ε > 0$ , finite $b$ )	Yes
Greedy best-first	$h (n)$	No in tree search (can loop); yes in finite graph search with a visited set	No
A*	$g (n) + h (n)$	Yes ( $ε > 0$ , finite $b$ )	Yes with admissible $h$ (tree search, or graph search with re-opening); with consistent $h$ (graph search without re-opening)

EXAM TIP

To check admissibility, compare $h$ with the true cheapest remaining cost at every node, not only on the path found. To check consistency, test every edge $(n, n^{'})$ of the graph. One failing edge is enough to make the heuristic inconsistent.

Combining and comparing heuristics

Dominance. If $h_{2} (n) \geq h_{1} (n)$ for every $n$ and both are consistent, every node A* expands with $h_{2}$ and $f < C^{*}$ is also expanded with $h_{1}$ . Differences can arise only among nodes with $f = C^{*}$ , which depend on tie-breaking. So the larger heuristic expands no more nodes, apart from those ties.
If $h_{1}$ and $h_{2}$ are admissible, $max (h_{1}, h_{2})$ is admissible and dominates both. If both are consistent, so is $max (h_{1}, h_{2})$ .
The sum $h_{1} + h_{2}$ of two admissible heuristics need not be admissible.

Tracing the order of expansion

A tracing question gives a small weighted graph and a table of $h$ values, and asks for the order of expansion, the number of nodes expanded, or the cost of the returned path. Keep a table with columns expanded node, frontier with $g$ and $f$ . Write the goal test result when a node is removed. Count the goal itself as expanded if the question says 'including the goal'.

WORKED EXAMPLE · A* AGAINST GREEDY BEST-FIRST ON ONE GRAPH

Directed edges with step costs: S→A 1, S→B 4, S→D 2, A→B 2, A→C 5, B→C 1, C→G 3, D→G 20. Heuristic values: $h (S) = 5$ , $h (A) = 5$ , $h (B) = 3$ , $h (C) = 3$ , $h (D) = 9$ , $h (G) = 0$ . Ties are broken alphabetically and the goal test is applied when a node is removed from the frontier. Give the expansion order and path cost for A* and for greedy best-first search, and say whether $h$ is admissible and consistent.

Solution

True remaining costs: $h^{*} (C) = 3$ , $h^{*} (B) = 4$ , $h^{*} (A) = 6$ , $h^{*} (D) = 20$ , $h^{*} (S) = 7$ . Every $h$ is at most $h^{*}$ , so $h$ is admissible.
Consistency edge by edge: S→A $5 \leq 1 + 5$ ; S→B $5 \leq 4 + 3$ ; S→D $5 \leq 2 + 9$ ; A→B $5 \leq 2 + 3$ ; A→C $5 \leq 5 + 3$ ; B→C $3 \leq 1 + 3$ ; C→G $3 \leq 3 + 0$ ; D→G $9 \leq 20 + 0$ . All hold, so $h$ is consistent.
A*: expand S ( $f = 5$ ). Frontier: A ( $g = 1, f = 6$ ), B ( $g = 4, f = 7$ ), D ( $g = 2, f = 11$ ).
Expand A. B improves to $g = 3$ , $f = 6$ . C enters with $g = 6$ , $f = 9$ . Frontier: B 6, C 9, D 11.
Expand B ( $g = 3$ ). C improves to $g = 4$ , $f = 7$ . Expand C. G enters with $g = 7$ , $f = 7$ . Then expand G, which is the goal.
A* order: S, A, B, C, G. Path S→A→B→C→G with cost $1 + 2 + 1 + 3 = 7$ . D is never expanded because $f (D) = 11 > 7$ .
Greedy uses $h$ only. Expand S; frontier A (5), B (3), D (9). Expand B (smallest $h$ ); frontier gets C (3). Expand C; G (0) enters. Expand G.
Greedy order: S, B, C, G. Path S→B→C→G with cost $4 + 1 + 3 = 8$ , which is not optimal.

Answer: A*: S, A, B, C, G with cost 7. Greedy best-first: S, B, C, G with cost 8. The heuristic is admissible and consistent.

Adversarial search: minimax

In a two-player, turn-taking, zero-sum game with perfect information, one player (MAX) tries to maximise a utility value and the other (MIN) tries to minimise it. The game tree has MAX and MIN levels alternating. Minimax assumes both play optimally: leaf values are given by the utility (or an evaluation function at a depth cut-off), and each internal node takes the maximum (MAX node) or the minimum (MIN node) of its children's values. The value at the root is the best outcome MAX can guarantee.

MINIMAX VALUE

MINIMAX (s) = ⎩ ⎨ ⎧ UTILITY (s) max_{a} MINIMAX (RESULT (s, a)) min_{a} MINIMAX (RESULT (s, a)) if s is terminal if MAX moves at s if MIN moves at s

Two-player zero-sum game, perfect information, finite tree. The value is computed bottom-up.

MINIMAX COMPLEXITY

time O (b^{m}), space O (bm) (depth-first, all actions at once)

$m$ is the maximum depth of the game tree. Minimax is complete on a finite tree and optimal against an optimal opponent.

The minimax value is a guarantee: if MAX follows the minimax strategy, MAX gets at least the minimax value whatever MIN does. Against a weaker MIN, another move might do better for MAX, but the minimax move never gets less than its value.

Games with chance (expectiminimax). When the tree also has chance nodes (for example a dice roll), a chance node takes the probability-weighted average of its children, $\sum_{r} P (r) value (RESULT (s, r))$ . MAX and MIN nodes are evaluated as in minimax. Minimax decisions are unchanged by any order-preserving change of the leaf values, but expectiminimax decisions are guaranteed unchanged only under a positive linear transformation. Plain alpha-beta does not apply to chance nodes as written, because an average cannot be bounded without bounds on the leaf values.

Alpha-beta pruning

Alpha-beta computes exactly the same root value as minimax, and returns a best move of the same value, but skips subtrees that cannot change the answer. It carries two numbers down the tree: $α$ , the best value MAX can already guarantee on the path to the root (starts at $- \infty$ ), and $β$ , the best value MIN can already guarantee (starts at $+ \infty$ ). Children are visited left to right, as drawn, unless the question says otherwise.

ALPHA-BETA CUT-OFF RULE

prune the remaining children of a node as soon as α \geq β

Updates: at a MAX node $α \leftarrow max (α, v)$ ; at a MIN node $β \leftarrow min (β, v)$ , where $v$ is the best child value so far. Pruning when $α = β$ is safe because it cannot change the root value. Some sources prune only when $α > β$ ; that can change the number of pruned leaves but never the root value. These notes use $α \geq β$ .

1  function ALPHABETA(node, alpha, beta, isMax)
2    if node is a leaf: return its value
3    if isMax:
4      v = -infinity
5      for each child c of node, left to right:
6        v = max(v, ALPHABETA(c, alpha, beta, false))
7        alpha = max(alpha, v)
8        if alpha >= beta: break
9      return v
10   else:
11     v = +infinity
12     for each child c of node, left to right:
13       v = min(v, ALPHABETA(c, alpha, beta, true))
14       beta = min(beta, v)
15       if alpha >= beta: break
16     return v

ALPHA-BETA TIME COMPLEXITY

O (b^{m /2}) with best move ordering, O (b^{m}) with worst ordering

With perfect ordering alpha-beta can look about twice as deep as minimax in the same time; with random ordering the cost is roughly $b^{3 m /4}$ . The root value is the same for every ordering; only the number of pruned leaves changes.

LEAVES EVALUATED WITH PERFECT ORDERING

b^{⌈ m /2 ⌉} + b^{⌊ m /2 ⌋} - 1

Uniform game tree with branching factor $b$ , all leaves at depth $m$ , distinct leaf values, children ordered best-first for the player to move. Example: $b = 3$ , $m = 2$ gives $3 + 3 - 1 = 5$ leaves (all three under the first MIN child, then one under each other child).

WORKED EXAMPLE · ALPHA-BETA ON A THREE-LEVEL TREE

A MAX root has three MIN children $P$ , $Q$ , $R$ , each with three leaves, in left-to-right order. $P$ : 7, 9, 4. $Q$ : 3, 10, 12. $R$ : 8, 5, 9. Run alpha-beta left to right. Find the root value and the leaves that are never evaluated.

Solution

Root starts with $α = - \infty$ , $β = + \infty$ . At $P$ : leaves 7, 9, 4 give $β$ of 7, then 7, then 4; $α < β$ throughout, so no cut. $P = 4$ . Root $α = 4$ .
At $Q$ (with $α = 4$ ): the first leaf 3 gives $v = 3$ and $β = 3$ . Now $α = 4 \geq β = 3$ , so the leaves 10 and 12 are pruned. $Q$ is at most 3, so it cannot beat 4.
At $R$ (with $α = 4$ ): leaf 8 gives $β = 8$ ; leaf 5 gives $β = 5$ which is above $α = 4$ ; leaf 9 leaves $v = 5$ . No cut. $R = 5$ . Root $α = 5$ .
Root value $= max (4, at most 3, 5) = 5$ .
Leaves evaluated: 3 + 1 + 3 = 7 of 9.

Answer: Root value 5; the leaves 10 and 12 under Q are not evaluated (2 pruned leaves).

EXAM TIP

$α$ and $β$ are only ever passed down from ancestors. A cut at a MIN node uses an $α$ that some MAX ancestor already holds, and a cut at a MAX node uses a $β$ from a MIN ancestor. In a two-level tree (MAX root, MIN children whose children are leaves), nothing under the first MIN child is pruned, because $α = - \infty$ there. In deeper trees, cuts can occur inside the first subtree: a MAX node below the first MIN child can be cut by that MIN node's $β$ . Never change the order of children unless told to; the number of pruned leaves depends on the order.

PREVIOUS-YEAR QUESTIONS

7 questions from the DA papers

Try each question first, then open the answer. We placed each question under a topic ourselves; the exam paper does not label topics.

See these papers in full: GATE DA 2026 · GATE DA 2025 · GATE DA 2024

GATE 2026 DA Q.13

GATE 2026 · DAQ.13 · 1 mark · MCQ

Which of the following algorithms is NOT an example of uninformed search?

(A)
Breadth First Search
(B)
Depth First Search
(C)
A* Search
(D)
Depth-limited Search

Answer and solution

GATE 2026 DA Q.13: answer and solution

See the question in the paper

Tap to open full size

GATE 2026 DA Q.13: answer and solution

GATE 2026 DA Q.30

GATE 2026 · DAQ.30 · 1 mark · NAT

Consider the game tree for a two-player turn-taking minimax game as shown in the figure. The value of a terminal node represents the utility of the game state if the game ends there. The numbers written next to the edges denote the strategies.

There are two players MAX and MIN. At any particular state of the game, MAX prefers to move to a state of maximum value. On the other hand, MIN prefers to move to a state of minimum value.

Suppose MAX starts the game at the root and has three strategies: 1, 2 and 3. Next, MIN plays and also has three strategies: 1, 2 and 3. The game ends there. Both players always take optimal strategies throughout the game.

At the root, the best strategy for MAX is ____________ . (Answer in integer)

GATE 2026 DA question 30: A three-level game tree. — Figure from the GATE 2026 DA paper. It is part of the question.

Answer and solution

GATE 2026 DA Q.30: answer and solution

GATE 2025 DA Q.43

GATE 2025 · DAQ.43 · 2 marks · MCQ

Consider game trees Tree-1 and Tree-2 as shown. The first level is a MAX agent and the second level is a MIN agent. The value in the square node is the output of the utility function.

For what ranges of $x$ and $y$ , the right child of node $B$ and the right child of node $E$ will be pruned by alpha-beta pruning algorithm?

GATE 2025 DA question 43: Two game trees. — Figure from the GATE 2025 DA paper. It is part of the question.

(A)
$x \in [1, \infty)$ and $y \in (- \infty, 2]$
(B)
$x \in (- \infty, 2]$ and $y \in (- \infty, 5]$
(C)
$x \in (- \infty, 2]$ and $y \in [2, \infty)$
(D)
$x \in [1, \infty)$ and $y \in (- \infty, 5]$

Answer and solution

GATE 2025 DA Q.43: answer and solution

GATE 2025 DA Q.44

GATE 2025 · DAQ.44 · 2 marks · MCQ

The state graph shows the action cost along the edges and the heuristic function h associated with each state. Suppose A* algorithm is applied on this state graph using priority queue to store the frontier. In what sequence are the nodes expanded?

GATE 2025 DA question 44: Directed graph. — Figure from the GATE 2025 DA paper. It is part of the question.

(A)
S,A,E,C,B,D,G
(B)
S,E,A,C,B,D,G
(C)
S,A,E,B,C,D,G
(D)
S,A,B,E,C,D,G

Answer and solution

GATE 2025 DA Q.44: answer and solution

GATE 2024 DA Q.23

GATE 2024 · DAQ.23 · 1 mark · MCQ

Let $h_{1}$ and $h_{2}$ be two admissible heuristics used in $A^{*}$ search.

Which ONE of the following expressions is always an admissible heuristic?

(A)
$h_{1} + h_{2}$
(B)
$h_{1} \times h_{2}$
(C)
$h_{1} / h_{2}, (h_{2} \neq = 0)$
(D)
$∣ h_{1} - h_{2} ∣$

Answer and solution

GATE 2024 DA Q.23: answer and solution

See the question in the paper

Tap to open full size

GATE 2024 DA Q.23: answer and solution

GATE 2024 DA Q.25

GATE 2024 · DAQ.25 · 1 mark · MCQ

Consider the following statement:

In adversarial search, $α$ - $β$ pruning can be applied to game trees of any depth where $α$ is the (m) value choice we have formed so far at any choice point along the path for the MAX player and $β$ is the (n) value choice we have formed so far at any choice point along the path for the MIN player.

Which ONE of the following choices of (m) and (n) makes the above statement valid?

(A)
(m) = highest, (n) = highest
(B)
(m) = lowest, (n) = highest
(C)
(m) = highest, (n) = lowest
(D)
(m) = lowest, (n) = lowest

Answer and solution

GATE 2024 DA Q.25: answer and solution

See the question in the paper

Tap to open full size

GATE 2024 DA Q.25: answer and solution

GATE 2024 DA Q.44

GATE 2024 · DAQ.44 · 2 marks · MCQ

Consider a state space where the start state is number 1. The successor function for the state numbered $n$ returns two states numbered $n + 1$ and $n + 2$ . Assume that the states in the unexpanded state list are expanded in the ascending order of numbers and the previously expanded states are not added to the unexpanded state list.

Which ONE of the following statements about breadth-first search (BFS) and depth-first search (DFS) is true, when reaching the goal state number 6?

(A)
BFS expands more states than DFS.
(B)
DFS expands more states than BFS.
(C)
Both BFS and DFS expand equal number of states.
(D)
Both BFS and DFS do not reach the goal state number 6.

Answer and solution

GATE 2024 DA Q.44: answer and solution

See the question in the paper

Tap to open full size

GATE 2024 DA Q.44: answer and solution

PRACTICE

5 questions to test yourself

PRACTICE 11 mark · MCQ

A tree has finite branching factor $b$ , every step costs 1, and the shallowest goal is at depth $d$ . Which statement about iterative deepening depth-first search on this tree is correct?

(A)
It is complete and optimal, with time $O (b^{d})$ and space $O (b d)$ .
(B)
It is complete but not optimal, because it uses depth-first search.
(C)
It is optimal, but its space requirement is $O (b^{d})$ .
(D)
It is not complete because the depth limit may be too small.

Answer and solution

Answer: (A)

Iterative deepening tries limits $0, 1, 2, \dots$ , so it reaches the limit $d$ eventually and finds a goal: complete.
It finds the goal with the smallest depth first, and with unit step costs the shallowest goal is the cheapest: optimal.
Each iteration is a depth-first search that stores only one path and its siblings, so space is $O (b d)$ .
For fixed $b \geq 2$ the repeated work multiplies the node count by less than $(b / (b - 1))^{2}$ , a constant, so time is $O (b^{d})$ . Hence A.

PRACTICE 21 mark · NAT

In a uniform tree with branching factor 2 the shallowest goal is at depth 3. Iterative deepening runs depth-limited searches with limits 0, 1, 2 and 3. In each iteration count every node of the tree up to the current limit once (the root included), and assume the last iteration generates all nodes up to depth 3. What is the total number of nodes generated over all iterations?

Answer and solution

Answer: $26$

Nodes up to each limit: limit 0 gives 1; limit 1 gives $1 + 2 = 3$ ; limit 2 gives $1 + 2 + 4 = 7$ ; limit 3 gives $1 + 2 + 4 + 8 = 15$ .
Total $= 1 + 3 + 7 + 15 = 26$ .
Check with the formula: $4 \cdot 1 + 3 \cdot 2 + 2 \cdot 4 + 1 \cdot 8 = 4 + 6 + 8 + 8 = 26$ .

PRACTICE 32 marks · MSQ

Which of the following statements about heuristics for A* search are TRUE? Here $h (goal) = 0$ for every heuristic.

(A)
Every consistent heuristic is admissible.
(B)
Every admissible heuristic is consistent.
(C)
If $h$ is consistent, the $f$ -values of the nodes along any path from the start never decrease.
(D)
Greedy best-first search with an admissible heuristic always returns an optimal path.

Answer and solution

Answer: (A), (C)

A is true: apply consistency along an optimal path to a goal and add the inequalities; the sum telescopes to $h (n) \leq h^{*} (n)$ because $h (goal) = 0$ .
B is false. Example: edges $n \to n^{'}$ costing 1 and $n^{'} \to G$ costing 3, with $h (n) = 4$ , $h (n^{'}) = 1$ , $h (G) = 0$ . Then $h^{*} (n) = 4$ and $h^{*} (n^{'}) = 3$ , so $h$ is admissible, but $h (n) = 4 > 1 + h (n^{'}) = 2$ , so it is not consistent.
C is true: $f (n^{'}) = g (n) + c + h (n^{'}) \geq g (n) + h (n) = f (n)$ by the consistency inequality.
D is false: greedy ignores $g$ , so it can return a costlier path even when $h$ is admissible (the worked example gives cost 8 against the optimum 7). Answer A and C.

PRACTICE 42 marks · NAT

Directed edges with step costs: S→A 2, S→B 3, A→C 4, B→C 1, B→G 9, C→G 2. Heuristic values: $h (S) = 4$ , $h (A) = 4$ , $h (B) = 3$ , $h (C) = 2$ , $h (G) = 0$ . A* graph search is run from S to G, replacing a frontier entry when a cheaper path to the same node is found and breaking ties alphabetically. What is the cost of the path that A* returns?

Answer and solution

Answer: $6$

Expand S ( $f = 4$ ): A has $g = 2$ , $f = 6$ ; B has $g = 3$ , $f = 6$ .
Expand A (tie with B, alphabetical): C has $g = 6$ , $f = 8$ .
Expand B ( $g = 3$ ): C improves to $g = 4$ , $f = 6$ ; G enters with $g = 12$ , $f = 12$ .
Expand C ( $f = 6$ ): G improves to $g = 6$ , $f = 6$ .
Expand G, the goal. Its path is S→B→C→G with cost $3 + 1 + 2 = 6$ . The heuristic is admissible and consistent (true costs: $h^{*} (S) = 6$ , $h^{*} (A) = 6$ , $h^{*} (B) = 3$ , $h^{*} (C) = 2$ ; every edge satisfies the consistency inequality), so 6 is optimal.

PRACTICE 52 marks · MCQ

A MAX root has two MIN children, L and R. L has two MAX children $M_{1}$ (leaves 5, 3) and $M_{2}$ (leaves 6, 9). R has two MAX children $M_{3}$ (leaves 3, 4) and $M_{4}$ (leaves 7, 2). Leaves are visited left to right and children are visited in the order given. Using alpha-beta pruning, which pair gives the root value and the number of leaves that are NOT evaluated?

(A)
Root value 5; 3 leaves not evaluated
(B)
Root value 5; 2 leaves not evaluated
(C)
Root value 4; 3 leaves not evaluated
(D)
Root value 6; 1 leaf not evaluated

Answer and solution

Answer: (A)

Left MIN node L, $α = - \infty$ , $β = + \infty$ . $M_{1}$ : leaves 5 and 3 both evaluated, $M_{1} = 5$ , so $β_{L} = 5$ .
$M_{2}$ with $β = 5$ : first leaf 6 gives $v = 6 \geq β = 5$ , so the leaf 9 is pruned (1 leaf). $L = min (5, \geq 6) = 5$ . Root $α = 5$ .
Right MIN node R with $α = 5$ . $M_{3}$ : leaves 3 and 4 are evaluated (a MAX node cuts only when $v \geq β = + \infty$ ), so $M_{3} = 4$ and $β_{R} = 4$ .
Now $α = 5 \geq β = 4$ , so $M_{4}$ is pruned entirely: leaves 7 and 2 (2 leaves).
Root $= max (5, \leq 4) = 5$ . Leaves not evaluated: $1 + 2 = 3$ . Answer A.

OFFICIAL GATE 2027 SYLLABUS WORDING

Copied from the GATE 2027 syllabus; see all 2027 syllabi.

GATE DA

Search: informed, uninformed, adversarial

Preparing in Kolkata? IAE Academy's course for GATE DA.