Local Search in Artificial Intelligence: Hill Climbing, Traps and a Worked Example

Local search does not systematically explore paths like BFS or A*. It improves a current candidate, yet the best immediate neighbour can miss the global best. Local search has five parts; hill climbing has identifiable failure modes and escape methods, and exam questions commonly test them.

Local search in AI: the five parts of the problem

Every local-search problem needs five definitions:

1. State: one complete candidate, such as a timetable or queen arrangement.

2. Objective or fitness function: the value used to judge it.

3. Neighbourhood: states reachable by one allowed change.

4. Move rule: how the next neighbour is selected.

5. Stopping rule: when the search returns its current state.

Maximisation moves towards larger objective values. Minimisation moves towards smaller costs or conflict counts. If the current value is 12 and its neighbours score 9, 14 and 11, maximisation prefers 14. If those numbers represent costs, minimisation prefers 9.

For the path-search comparison, review Graph Algorithms: BFS, DFS and Shortest Paths. Local search suits large or continuous spaces, optimisation and cases where the route is irrelevant, such as timetable conflict minimisation, N-queens conflict minimisation and route-quality improvement. An abstract maximisation landscape demonstrates how a local maximum can differ from the global maximum.

Hill climbing: move uphill until no strict improvement exists

Steepest-ascent hill climbing evaluates every neighbour, chooses the highest value and moves only if it is strictly higher than the current value. Otherwise, it stops. Minimisation mirrors the rule. An equal-valued move needs an explicit sideways-move policy.

From value 5, suppose neighbours arrive as 4, 6, 8 and 7. First-choice takes 6, the first improvement. Steepest ascent checks all four and takes 8. Stochastic hill climbing samples among 6, 8 and 7 according to its defined random policy, which has no universal probability rule.

Do not confuse hill climbing with greedy construction. A greedy algorithm commits to attractive pieces while building a solution, as explained in Greedy Algorithms: Strategy and Problems. Hill climbing modifies a complete candidate. Dynamic Programming Explained: 0/1 Knapsack differs from both by reusing solved subproblems.

Local search worked example: steepest ascent stops at value 8

Consider this undirected neighbourhood graph, with each number showing the objective value to maximise:

S(3): A(6), B(5); A(6): S(3), C(8), D(7); B(5): S(3), H(7); C(8): A(6), E(6), F(8); D(7): A(6); E(6): C(8), J(9); F(8): C(8); H(7): B(5), I(10); J(9): E(6), I(10); I(10): H(7), J(9).

I(10) is the global maximum. Starting at S gives this trace:

Recomputing in prose gives 3 → 6 → 8, then stop. The result is C(8), a local maximum, although I(10) is better. The unchosen opening move matters: a restart at B follows B(5) → H(7) → I(10) and reaches the global maximum.

Local maxima, plateaus and ridges: why the stopping test can mislead

C(8) is a local maximum because none of its neighbours exceeds 8. The equal-valued edge between C(8) and F(8) forms a plateau. A sideways move from C to F makes no progress, and F can only send the search back to C. The lower state E(6) is a valley step on a route from C towards J(9) and I(10).

A ridge exposes neighbourhood design. On a grid, (0,0) has value 7. Its permitted moves (1,0) and (0,1) have value 6, while diagonal (1,1) has value 9. Orthogonal-only strict hill climbing stops at 7. Adding the diagonal makes 9 reachable in one improving move.

So, local optimality depends on which moves are allowed. Stopping proves only that there is no allowed improving neighbour under the stated rule. Ordinary hill climbing does not thereby prove completeness or global optimality.

Escaping a local optimum: sideways moves, restarts and simulated annealing

Match the remedy to the failure. Sideways moves can cross a plateau, but C(8) → F(8) cannot escape because F connects only to C. A cap of 2 prevents indefinite cycling. Random restart changes the initial state and keeps the best result. Starting at B gives 5 → 7 → 10; starting at E gives 6 → 9 → 10.

Simulated annealing can sometimes accept a worse move. At C(8), suppose it proposes E(6). For maximisation, delta = 6 - 8 = -2. At temperature T = 4:

p = exp(delta/T) = exp(-2/4) = exp(-0.5) ≈ 0.6065

With random draw u = 0.42, accept because 0.42 < 0.6065. The improving proposals E(6) → J(9) → I(10) are then accepted directly. At T = 0.5, the same proposal gives:

p = exp(-2/0.5) = exp(-4) ≈ 0.0183

Now 0.42 > 0.0183, so reject it. Cooling reduces the willingness to accept worse moves. Beyond these single-state remedies, local beam search retains k current states, while a genetic algorithm maintains a population and applies selection, crossover and mutation.

Local search exam patterns: selection, termination and arithmetic

Recurring conceptual and numerical patterns ask you to:

1. Identify the next state under a stated move rule.

2. Classify a returned state as local or global.

3. Distinguish a plateau from a ridge.

4. Separate first-choice from steepest-ascent hill climbing.

5. Choose a remedy for a named failure mode.

6. Calculate a simulated-annealing acceptance probability.

For a minimisation drill, let the current conflict count be 4 and scan candidates in the order 5, 3, 2 and 2. First-choice minimisation rejects 5 and takes 3, the first strict improvement. Steepest-ascent minimisation evaluates every candidate and takes 2. If the question says ties go to the first-listed state, it selects the first 2. A changed tie rule or neighbourhood can change the answer.

Local-search questions reward tracing the stated rule. Use GATE CS Exam Preparation for wider navigation. The practice bank has about 10 live questions on Local Search Fundamentals, so practise the selection, termination and arithmetic patterns.

Local search short version and the next step

Before solving, ask five questions:

1. What is the state?

2. What value is being maximised or minimised?

3. Which moves define the neighbourhood?

4. Which neighbour-selection and tie rule applies?

5. What exactly triggers termination?

In this example, strict steepest ascent from S returns C(8), while a restart or a permitted downhill move can reach I(10). Hand-trace the graph once, then change the start state, neighbourhood and temperature to see which conclusion changes. For a wider, sequenced CS preparation path, continue with GATE Guidance by Sanchit Sir - Knowledge Gate AI.