Local search questions often turn on one reversed definition or a small difference between hill climbing variants. Five of the ten questions below are previous-year questions, from ISRO 2025, HTET 2023 and three UGC NET Paper 2 papers, and every one of them is decided by a definition rather than a calculation.
Attempt each question before reading its explanation. The three UGC NET questions link to their solved pages, and the rest of the subtopic sits in the Unit 10 Artificial Intelligence learn module. To place local search inside the wider paper first, start with UGC NET Computer Science Syllabus Areas.
What local search is, and where exams put it
Classical searches such as BFS, DFS and A* remember paths. Local search keeps one current state and moves to a neighbour, so it uses little memory and suits optimization problems such as n-queens, timetabling and TSP. Hill climbing generates and tests a move, then uses feedback to choose a direction. Exams file the topic under artificial intelligence rather than data structures: in UGC NET Paper 2 it sits in Unit 10, Artificial Intelligence, beside the classical search algorithms, and ISRO and HTET papers test the same definitions. The questions stay short and definitional, so one reversed word decides the mark. If that contrast is unclear, revise Graph Algorithms: BFS, DFS and Shortest Paths.
Q1. AI search and optimization method (ISRO 2025)
Which of the following algorithms is used for search/optimization in AI?
(a) Greedy Algorithm
(b) Recursive Algorithm
(c) Hill Climbing Algorithm
(d) Hot Potato Algorithm
Answer: (c) Hill Climbing Algorithm. Hill climbing is the named AI search and optimization method here. Greedy and recursive are general algorithm-design styles, while hot potato is a packet-routing heuristic.
Q2. Generate-and-test with feedback (HTET 2023)
It is a variant of generate and test in which feedback from test procedure is used to help the generator decide which direction to move in search space?
(a) Hill climbing
(b) Best first search
(c) Constraint satisfaction
(d) Problem reduction
Answer: (a) Hill climbing. This is the Rich and Knight definition: generate a move, test it, and let its score steer the next move. Best first search keeps a frontier, constraint satisfaction prunes assignments, and problem reduction divides a goal into subgoals.
The hill climbing loop, walked on real numbers
Hill climbing keeps one current state, evaluates neighbouring states, and moves only when a neighbour improves the objective. It stops when no neighbour is better.
Take nine states in a line with values P1 to P9 = 2, 4, 6, 8, 5, 5, 5, 9, 3. From P1, the walk is P1(2) -> P2(4) -> P3(6) -> P4(8). P4's neighbours are worse: P3 is 6 and P5 is 5. The climb stops at local maximum P4, although P8 is the global maximum at 9. Moving uphill does not guarantee the best state.
Q3. Identify the iterative uphill algorithm
_______________ is an iterative algorithm, a loop that continually moves in the direction of increasing value, that is, uphill, to find a better solution.
(a) Up-Hill Search
(b) Reverse-Down-Hill search
(c) Hill algorithm
(d) Hill-Climbing
Answer: (d) Hill-Climbing. Moving repeatedly toward an increasing value is the defining hill climbing loop, just as P1 moves to P4 above. The other names are not standard AI algorithms.
Simple, steepest-ascent and stochastic hill climbing
Suppose the current value is 5 and neighbours are examined as N1=6, N2=9, N3=7. Simple takes N1, the first improvement. Steepest-ascent evaluates all three and selects N2, the best. Stochastic randomly chooses among the uphill moves. Simple is cheapest per step, steepest-ascent is best-informed, and stochastic reduces dependence on order.
Q4. Behaviour of steepest-ascent hill climbing
The steepest-ascent hill climbing search algorithm:
(a) Among all neighbours selects the first one that optimizes the current cost to be the next node
(b) This evaluates all neighbouring nodes at a time and selects the one closest to the solution state
(c) This selects a neighbouring node at random, evaluates it and decides whether to move to it or examine another
(d) None of the Above
Answer: (b) It evaluates all neighbouring nodes and selects the one closest to the solution state. On the worked values, steepest-ascent compares 6, 9 and 7, then chooses 9. Option (a) describes simple hill climbing, while option (c) describes stochastic hill climbing.
Q5. Name the all-neighbours variant
____________ Hill Climbing Search algorithm evaluates all neighbouring nodes at a time and selects the one closest to the solution state.
(a) Simple Hill Climbing
(b) Steepest Ascent Hill Climbing
(c) Stochastic Hill Climbing
(d) None of the above
Answer: (b) Steepest Ascent Hill Climbing. The phrase "evaluates all neighbouring nodes" identifies steepest-ascent. Remember: simple means first better, steepest means best of all, and stochastic means random among better moves.
Q6. Randomized hill climbing move (UGC NET June 2016)
How does randomized hill-climbing choose the next move each time?
(a) It generates a random move from the moveset, and accepts this move.
(b) It generates a random move from the whole state space, and accepts this move.
(c) It generates a random move from the moveset, and accepts this move only if this move improves the evaluation function.
(d) It generates a random move from the whole state space, and accepts this move only if this move improves the evaluation function.
Answer: (c). The move must come from the current state's moveset, not the whole state space, and it is accepted only if it improves the evaluation. In the example, pick N1, N2 or N3 at random and retain it only if it beats 5. Options (a) and (b) accept the move without testing it, and (b) and (d) draw it from the whole state space instead of the moveset.
Where hill climbing gets stuck
A local maximum beats its neighbours but is worse than the global best, like P4=8 against P8=9. A plateau, like P5=P6=P7=5, has no gradient. On a ridge, each single-step move looks downhill although the crest rises farther away. At a local maximum, remember that every neighbour is worse, not better.
Q7. Local maximum and plateau statements
Consider the following statements
(S1) At a local maximum all neighboring states have a value that is better than the current state.
(S2) On plateau all neighbours have the same value. Hence, it is not possible to select the best direction.
Which of the following is true?
(a) Only S1
(b) Only S2
(c) Both S1 and S2
(d) None of the above
Answer: (b) Only S2. S1 reverses the definition. At P4, the current value 8 beats neighbour values 6 and 5. S2 correctly describes the plateau: from P6, both adjacent neighbours have value 5, so there is no best direction.
Q8. Canonical shortcomings (UGC NET December 2019)
Consider the following:
(A) Trapping at local maxima
(B) Reaching a plateau
(C) Traversal along the ridge
Which of the following option represents shortcomings of the hill climbing algorithm?
(a) (A) and (B) only
(b) (A) and (C) only
(c) (B) and (C) only
(d) (A), (B) and (C)
Answer: (d). Local maxima, plateaus and ridges are all standard shortcomings. They correspond to a better state hidden beyond a local peak, no useful gradient across a flat, and progress that cannot be reached through a single improving move.
Escape moves for local search
Pair each failure with its classic fix. Backtrack from a local maximum, make a big jump from a plateau, and test several directions on a ridge. Random-restart hill climbing and simulated annealing develop these ideas further.
Q9. Big jump escape
In hill climbing, making a big jump (randomly selecting a state far away from the current state) is the solution for:
(a) Plateau
(b) Local maximum
(c) Ridge
(d) None of the Above
Answer: (a) Plateau. At P6, both adjacent moves stay on the flat region at value 5, so local probing gives no direction. A large jump can leave the plateau and find a useful gradient. Backtracking addresses a local maximum, while testing several directions addresses a ridge.
Space complexity of local search
Hill climbing retains one current state and its evaluation, so its space complexity is O(1). Path-remembering methods store more: best first search has an O(b^d) frontier, depth first search uses O(bd) stack space, and A* can retain O(b^m) states in the worst case.
Q10. Match each search with its space complexity (UGC NET December 2023)
Match List - I with List - II:
List I | List II |
|---|---|
(A) Hill climbing | (I) O(b^d) |
(B) Best first search | (II) O(bd) |
(C) A* Search | (III) O(1) |
(D) Depth first search | (IV) O(b^m) |
Choose the correct answer from the options given below:
(a) (A)-(III),(B)-(I),(C)-(IV),(D)-(II)
(b) (A)-(II),(B)-(I),(C)-(IV),(D)-(III)
(c) (A)-(II),(B)-(IV),(C)-(I),(D)-(III)
(d) (A)-(I),(B)-(III),(C)-(II),(D)-(I)
Answer: (a). Start with the certain pair: hill climbing stores one current state, so (A)-(III), O(1). Only option (a) contains it. The remaining pairs confirm the key: best first search is O(b^d), A* is O(b^m), and depth first search is O(bd).
The short version and your next step
Local search keeps one current state, uses constant space, and optimizes configurations rather than paths.
Hill climbing is generate-and-test with feedback, and it moves only uphill.
Simple takes the first better neighbour, steepest-ascent takes the best, and stochastic chooses randomly among better moves.
Local maxima, plateaus and ridges pair with backtracking, a big jump and multi-direction testing.
O(1) is the anchor pair for hill climbing in a complexity match-list.
Local search rewards exact wording, so re-read S1 in Q7 until the reversal is obvious. Work the solved UGC NET PYQs inside the NTA-UGC-NET Paper 2 course, then browse the wider UGC NET preparation options when you are ready to plan the rest of the paper.
