Algorithms For Dummies

  Performing Local Search 

     345

An example of hill climbing in action (and of the risks of getting stuck in a local 

maximum or in a local minimum when you’re descending, as in this example) is 

the n-queens puzzle, first created by the chess expert Max Bezzel, in 1848, as a 

challenge for chess lovers. In this problem, you have a number of queens (this 

number is n) to place on a chessboard of n x n dimensions. You must place them 

so that no queen is threatened by any other. (In chess, a queen can attack by any 

direction by row, column, or diagonal.)

This is really a NP-hard problem. If you have eight queens to place on a 8 x 8 

chessboard, there are 4,426,165,368 different ways to place them but only 92 con-

figurations solve the problem. Clearly, you can’t solve this problem using brute 

force or luck alone. Local search solves this problem in a very simple way using 

hill climbing:

1. 

Place the n queens randomly on the chessboard so that each one is on a 

different column (no two queens on the same column).

2. 

Evaluate the next set of solutions by moving each queen one square up or 

down in its column. This step requires 2*n moves.

3. 

Determine how many queens are attacking each other after each move.

4. 

Determine which solution has the fewest queens attacking each other and use 

that solution for the next iteration.

5. 

Perform Steps 4 and 5 until you find a solution.

Unfortunately, this approach works only about 14 percent of the time because it 

gets stuck in a chessboard configuration that won’t allow any further improve-

ment 86 percent of the time. (The number of queens under attack won’t diminish 

for all 2*n moves available as next solutions.) The only way you get away from 

such a block is to restart the local search from scratch by choosing another ran-

dom starting configuration of the queens on the chessboard. Figure 18-3 shows a 

successful solution.

In spite of this weakness, hill-climbing algorithms are used everywhere, especially 

in  artificial  intelligence  and  machine  learning.  Neural  networks  that  recognize 

sounds or images, power mobile phones, and motivate self-driving cars mostly 

rely on a hill-climbing optimization called gradient descent. Randomized starts and 

random injections in the hill-climbing procedure make it possible to escape any 

local solution and reach the global maximum. Both simulated annealing and Tabu 

Search are smart ways to use random decisions in hill climbing.

---

346