Skip to content
Tutorials Center
My learning

Topics

Lesson 13 of 46 ยท Informed Search

Local Search and Hill Climbing

Learn local search in AI: hill climbing, local maxima and plateaus, random restarts and the min-conflicts method that solves n-queens, with seeded Python runs.

Every algorithm so far has searched for a path: a sequence of actions from a start state to a goal. For many problems the path is irrelevant, and only the final state matters. Where do eight queens go so that none attacks another? Which timetable has no clashes? What layout of a chip has the shortest wires? You don't need to know how you got to the answer, only that you have one.

Local search is built for those problems. It keeps a single current state (not a tree of paths), looks at its neighbours, and moves to a better one. It remembers nothing about where it came from, so it uses a tiny, constant amount of memory, and it can find good states in enormous spaces where systematic search would never finish. The price is that it usually gives no guarantee: it may stop at a mediocre state and it can never prove that none better exists.

The landscape picture

Imagine every state as a point on a landscape whose height is how good the state is (the objective function). Local search is a hiker in fog who can see only the squares next to them. Hill climbing walks uphill. The shape of the terrain decides everything:

graph LR
    A["Local maximum<br/>higher than all neighbours,<br/>lower than the best"] --- B["Plateau<br/>all neighbours<br/>equal height"]
    B --- C["Ridge<br/>narrow path uphill that<br/>single steps can't follow"]
    C --- D["Global maximum<br/>the best state"]

Four landmarks on a search landscape. Hill climbing is good at reaching the first three and not always the last.

  • A local maximum is a peak that is higher than all its neighbours but lower than the global maximum. Hill climbing stops there.
  • A plateau is a flat region. If no neighbour is strictly better, the climber stops, even though better states may lie just beyond the flat area.
  • A ridge is a narrow crest whose neighbouring moves all go down, although a sequence of moves would climb it.

Hill climbing

Steepest-ascent hill climbing is simply:

  1. Start at some state.
  2. Look at all neighbours and pick the best one.
  3. If it's better than the current state, move there and repeat. Otherwise stop.

The program below builds a small one-dimensional landscape with a low peak around position 4, a plateau of height 5 in the middle, and a tall peak at position 27. It runs hill climbing from several starting points, shows what happens on the plateau with and without sideways moves (accepting equally good neighbours for a limited number of steps), and finally uses random restarts: repeat the climb from random starting points and keep the best result.

Python Hill climbing, plateaus and random restarts

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The outcome depends entirely on where you start. From 30 the climber walks to the tall peak at 27. From 2 or 8 it gets stuck at the low peak at 4 (height 9). From 41 it stops on the minor bump at 38 (height 21). Position 14 is on the plateau, where no neighbour is strictly better so the strict climber doesn't move at all. Allowing up to 60 sideways moves lets it wander across the flat shelf, and in 19 of 20 seeded runs it finds its way to the real peak. (The remaining run used up its sideways budget before escaping.)

Random restarts attack the problem from the outside. In the final section, eight climbs from random starting points land on peaks of height 9, 37, 21, 37, 37, 5, 21 and 37. Keeping the best gives the global maximum. If a single climb succeeds with probability p, the expected number of restarts is 1/p, so for landscapes where many starting points lead uphill to a good peak, restarts are a surprisingly strong strategy.

N-queens

The n-queens problem asks you to place n queens on an nร—n board so that no two share a row, column or diagonal. A good local-search formulation puts one queen in every column from the start. A state is then a list queens[c] giving the row of the queen in column c; a move relocates one queen to a different row in its column; and the objective is the number of attacking pairs, which we want to minimize to 0. The hill is turned upside-down, but it's the same idea.

Python Hill climbing on 8 queens

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Plain hill climbing solves 8 queens in only 49 of 300 runs (16%); the other 84% get stuck in local minima with a few attacking pairs left. That sounds poor, but the state space has only 16.7 million states (8 to the power 8), and a run takes a handful of steps. Restarting until success needed just 4 starts. This is the usual pattern: a weak method repeated many times can beat a strong method used once.

Min-conflicts

For constraint-style problems there is a famously effective variation, the min-conflicts heuristic. At every step:

  1. Pick a queen that is currently attacked, at random.
  2. Move it, within its column, to the row where it will have the fewest conflicts (breaking ties randomly), even if the total gets no better.

The two details that distinguish it from steepest-ascent are the random choice of a variable and the willingness to make a sideways or even slightly uphill move. Together they let the search slide off plateaus, and the effect on n-queens is dramatic. The program keeps counters for every row and diagonal so that checking a square is O(1), and then solves boards up to 1,000 queens.

Python Min-conflicts solves n-queens, even for n = 1000

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The step counts barely grow with the board: roughly 10 to 35 moves for 8 queens, around 100 for 50 queens and about 700 for 1,000 queens, close to n steps in every case. A board with 10^3000 possible placements is solved in a few hundred moves, because the landscape of this problem has very few traps and min-conflicts rarely falls into one. This behaviour was used to schedule observations on the Hubble Space Telescope, which is one of the reasons the method is taught everywhere.

Local search can only be trusted when you are happy with "a good answer, usually". It cannot detect that a problem has no solution, and without a cap on the number of steps it may run forever (as we did above with max_steps).

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does a local search algorithm keep in memory?

    Local search moves between neighbouring states and remembers almost nothing, so memory use is constant; that is its main advantage.
  2. 2. Why can steepest-ascent hill climbing get stuck on a plateau?

    The stopping rule is 'no better neighbour'. On flat ground all neighbours are equal. Allowing a limited number of sideways moves helps cross the flat area.
  3. 3. If a single hill climb finds the global optimum with probability p, about how many random restarts are needed on average?

    The number of independent tries until the first success is geometric, with mean 1/p.
  4. 4. What is distinctive about the min-conflicts heuristic for n-queens?

    Choosing a random conflicted variable and accepting sideways moves lets the search escape plateaus that trap steepest ascent.

Summary

  • Local search keeps one current state and moves to neighbours; it is ideal when only the final state matters and the space is huge.
  • Hill climbing walks uphill and gets trapped by local maxima, plateaus and ridges.
  • Sideways moves and random restarts are cheap remedies that greatly raise the success rate.
  • N-queens is a standard test: plain hill climbing solves 8 queens in about 16% of runs, restarts fix that, and min-conflicts solves even 1,000 queens in a few hundred moves.
  • Local search offers no guarantee of optimality and cannot prove that no solution exists.

Next, look at methods that sometimes accept worse moves on purpose in Simulated Annealing and Genetic Algorithms.