A* ranks every frontier node by f(n) = g(n) + h(n), and exam questions attack the four things that formula can break: whether g is added at all, whether h stays admissible, which nodes are still expanded once f reaches the optimal cost C*, and what happens when the frontier outgrows memory. Nine of the eleven below are UGC NET previous-year questions; Q2 and Q8 are concept questions from the Unit 10 Artificial Intelligence module. For the blind-search baseline A* improves on, revise Graph Algorithms: BFS, DFS and Dijkstra Traced Step by Step.
Warm-up: what A* actually does
A* uses f(n) = g(n) + h(n): paid plus remaining cost. Greedy uses h; uniform-cost uses g.
Q1 (UGC NET 2014 December). An A* algorithm is a heuristic search technique which
(a) is like a depth-first search where most promising child is selected for expansion
(b) generates all successor nodes and computes an estimate of distance (cost) from start node to a goal node through each of the successors. It then chooses the successor with shortest cost.
(c) saves all path lengths (costs) from start node to all generated nodes and chooses shortest path for further expansion.
(d) none of the above
Answer: (b). It states g + h. Option (a) is greedy-style; (c) ignores h.
Q2 (concept). Consider the following statements:
(S1) A* is an informed search algorithm, it aims to find a path to the given goal node having the smallest cost. A* selects the path that minimizes using f(n) = h(n).
(S2) Greedy Best First Search tries to expand the node that is closest to the goal, on the grounds that this is likely to lead to a solution quickly. Thus, it evaluates nodes by using just the heuristic function f(n)=g(n)+h(n)
Which of the above is not true.
(a) Only S1
(b) Only S2
(c) Both
(d) None of the above
Answer: (c). Both formulas are swapped. A* uses g + h; greedy uses h.
A* evaluation function worked end to end
Edges: S->A = 1, S->B = 4, A->B = 2, A->C = 5, B->C = 2, C->G = 3. Heuristics at S, A, B, C, G: 5, 4, 3, 3, 0.
S: g = 0, f = 0 + 5 = 5.
Expand S: A gets g = 1, f = 1 + 4 = 5; B gets g = 4, f = 4 + 3 = 7.
Expand A: B improves to g = 1 + 2 = 3, f = 3 + 3 = 6; C gets g = 1 + 5 = 6, f = 6 + 3 = 9.
Expand B: C improves to g = 3 + 2 = 5, f = 5 + 3 = 8.
Expand C: G gets g = 5 + 3 = 8, f = 8 + 0 = 8. G returns S->A->B->C->G, cost 1 + 2 + 2 + 3 = 8.
Q3 (UGC NET 2019 June). Match List-I with List-II:
List-I | List-II |
|---|---|
(a) Greedy best-first | (i) Minimal cost(p) + h(p) |
(b) Lowest cost-first | (ii) Minimal h(p) |
(c) A* algorithm | (iii) Minimal cost(p) |
(a) (a)-(i); (b)-(ii); (c)-(iii)
(b) (a)-(iii); (b)-(ii); (c)-(i)
(c) (a)-(i); (b)-(iii); (c)-(ii)
(d) (a)-(ii); (b)-(iii); (c)-(i)
Answer: (d). Greedy uses h; lowest-cost-first uses cost(p); A* adds them. In the trace above A* ranked A at f = 1 + 4 = 5 against B at f = 4 + 3 = 7; a greedy ranking would have compared only h(A) = 4 against h(B) = 3 and gone to B.
Q4 (UGC NET 2012 June). A* algorithm uses f' = g + h' to estimate the cost of getting from the initial state to the goal state, where g is a measure of cost getting from initial state to the current node and the function h' is an estimate of the cost of getting from the current node to the goal state. To find a path involving the fewest number of steps, we should test,
(a) g = 1
(b) g = 0
(c) h' = 0
(d) h' = 1
Answer: (a). Unit move cost makes g the step count. Setting g = 0 gives greedy; h' = 0 gives uniform-cost.
A* admissibility: the contract that buys optimality
Admissible means h(n) <= h*(n). True costs from S, A, B, C are 8, 7, 5, 3, so heuristics 5, 4, 3, 3 qualify. Greedy picks B and pays 4 + 2 + 3 = 9; A* finds 1 + 2 + 2 + 3 = 8.
Q5 (UGC NET 2012 December). A* algorithm is guaranteed to find an optimal solution if
(a) h' is always 0.
(b) g is always 1.
(c) h' never overestimates h.
(d) h' never underestimates h.
Answer: (c). Never overestimating is admissibility. Zero is a special case; overestimation can hide the optimum.
Q6 (UGC NET 2022 December). The A* algorithm is optimal when,
(a) It always finds the solution with the lowest total cost if the heuristic 'h' is admissible.
(b) Always finds the solution with the highest total cost if the heuristic 'h' is admissible.
(c) Finds the solution with the lowest total cost if the heuristic 'h' is not admissible.
(d) It always finds the solution with the highest total cost if the heuristic 'h' is not admissible.
Answer: (a). “Lowest” and “admissible” decide it, and dropping admissibility drops optimality with it. Inflate the running example's h(A) from 4 to 9, an overestimate of the true 7, and f(A) becomes 10. A* then expands B at f = 7, reaches G through C at f = 9, and returns S->B->C->G at cost 9, never reopening the cost-8 route through A.
A* node expansion and the C* contour
Here C* = 8. A* expanded S at f = 5, A at f = 5 and B at f = 6, all strictly below C*, then C at f = 8, exactly on the C* contour. The earlier entry for C at f = 9 was superseded before it was ever expanded, and nothing with f above 8 was touched.
Q7 (UGC NET 2018 July). Consider the following sentences regarding A*, an informed search strategy in Artificial Intelligence (AI).
(S1) A* expands all nodes with f(n) < C*.
(S2) A* expands no nodes with f(n) = C*.
(S3) Pruning is integral to A*.
Here, C* is the cost of the optimal solution path. Which of the following is correct with respect to the above statements?
(a) Both S1 and S2 are true.
(b) Both S1 and S3 are true.
(c) Both S2 and S3 are true.
(d) All three statements are true.
Answer: (b). S1 and S3 hold. S2 fails: C was expanded at f = C* = 8 in the trace above, so A* does expand nodes on the C* contour. What it never expands is a node with f strictly greater than C*.
A* among its cousins: completeness and optimality
BFS is complete for finite branching and optimal for unit costs; DFS and greedy guarantee neither. A* needs admissibility for tree search or consistency for graph search. See UGC NET Computer Science High-Yield Topics.
Q8 (concept). Match the following search algorithms in Group I with their corresponding properties in Group II.
Group I: P. Breadth First Search, Q. Depth First Search, R. Best First Search, S. A* Algorithm
Group II:
Selects the most promising nodes based on a heuristic function.
Is complete if the solution is there.
Avoids expanding paths that are already expensive using the function f(n) = g(n) + h(n).
Does not ensure completeness and optimality.
(a) P-2, Q-1, R-3, S-4
(b) P-4, Q-3, R-2, S-1
(c) P-2, Q-4, R-1, S-3
(d) P-4, Q-3, R-1, S-2
Answer: (c). The matches are P-2, Q-4, R-1, S-3. Anchoring R-1 and S-3 isolates (c).
Q9 (UGC NET 2021). Which among the following statement(s) is(are) FALSE?
A. Greedy best-first search is not optimal but is often efficient.
B. A* is complete and optimal provided h(n) is admissible or consistent.
C. Recursive best-first search is efficient in terms of time complexity but poor in terms of space complexity.
D. h(n) = 0 is an admissible heuristic for the 8-puzzle.
(a) A only
(b) A and D only
(c) C only
(d) C and D only
Answer: (c). C reverses RBFS: it uses linear space but may regenerate work. A, B and D are true.
Memory-bounded A* relatives: RBFS, SMA* and IDA*
A* can consume exponential memory: every generated node stays on the frontier. IDA* replaces it with repeated depth-first passes under a rising f-limit, and on the graph traced above those limits run 5, 6, 7, then 8, so S and A are regenerated on every pass before the limit reaches C* = 8. RBFS recurses depth-first, remembering only the current path plus the best alternative f value at each level, so its space is linear in depth. SMA* uses all the memory it is given and drops the worst leaf when the queue is full, backing its f value up to the parent so the branch can be regenerated.
Q10 (UGC NET 2018 December). Match List I with List II and choose the correct answer from the code given below.
List-I (Search technique): (a) Greedy Best-First Search, (b) A* Search, (c) Recursive Best-First Search, (d) Iterative-deepening A* Search.
List-II (Description): (i) Selects a node for expansion if optimal path to that node has been found, (ii) Avoids substantial overhead associated with keeping the sorted queue of nodes, (iii) Suffers from excessive node generation, (iv) Time complexity depends on the quality of heuristic code.
(a) (a)-(i), (b)-(ii), (c)-(iii), (d)-(iv)
(b) (a)-(iv), (b)-(i), (c)-(ii), (d)-(iii)
(c) (a)-(iv), (b)-(iii), (c)-(ii), (d)-(i)
(d) (a)-(i), (b)-(iv), (c)-(iii), (d)-(ii)
Answer: (b). Pair greedy-(iv), A*-(i), RBFS-(ii), IDA*-(iii). RBFS saves space; IDA* regenerates nodes.
Q11 (UGC NET 2020 June). Match List I with List II.
List I | List II |
|---|---|
(A) Greedy Best-First Search | (I) Space complexity is O(d) where d = depth of the deepest optimal solution |
(B) A* | (II) Incomplete even if the search space is finite |
(C) Recursive Best-First Search | (III) Optimal if optimal solution is reachable; otherwise, returns the best reachable optimal solution |
(D) SMA* | (IV) Computation and space complexity is too high |
(a) A-II, B-IV, C-I, D-III
(b) A-II, B-III, C-I, D-IV
(c) A-III, B-II, C-IV, D-I
(d) A-III, B-IV, C-II, D-I
Answer: (a). Match greedy-II, A*-IV, RBFS-I, SMA*-III. Remember “RBFS: linear space” and “SMA*: best within memory”.
A* Search Algorithm MCQs: the short version
f = g + h combines paid and remaining cost.
Admissible h never overestimates; graph search needs consistency.
A* expands every f < C*, and possibly f = C*.
Greedy sets g = 0; uniform-cost sets h = 0.
RBFS, SMA* and IDA* trade work for memory.
Find these PYQs in the NTA UGC NET Paper 2 course. Compare UGC NET Preparation Courses and Test Series for broader revision.
