Algorithms For Dummies

 Challenging Difficult Problems

In local search, you can mimic the same procedure successfully using an objective 

function, a measurement that evaluates the neighboring solutions and determines 

which one improves on the current one. Using the hill-climbing analogy, having 

an objective function is like feeling the inclination of the terrain and determining 

the next best move. From the current position, a hiker evaluates each direction to 

determine the terrain’s slope. When the goal is to reach the top, the hiker chooses 

the direction with the greatest upward slope to reach the top. However, that’s just 

the ideal situation; hikers often encounter problems during a climb and must use 

other solutions to circumnavigate them.

An objective function is similar to a greedy criterion (see Chapter 5). It’s blind 

with respect to its final destination, so it can determine direction but not detect 

obstacles. Think about the effect of blindness when climbing the mountains —  

it’s difficult to say when a hiker reaches the top. Flat terrain that lacks any oppor-

tunities  for  upward  movement  could  indicate  that  the  hiker  reached  the  top. 

Unfortunately, a flat spot can also be a plain, an elbow, or even a hole the hiker 

happened to fall into. You can’t be sure because the hiker can’t see.

The same problem happens when using a local search guided by a hill-climbing 

heuristic: It pursues progressively better neighbor solutions until it can’t find a 

better solution by checking the solutions that exist around the current one. At this 

point, the algorithm declares it found the solution. It also says that it has found a 

global  solution,  even  though,  as  illustrated  in  Figure  18-2,  it  may  have  simply 

found a local maximum, a solution that’s the best around because it’s surrounded 

by  worse  solutions.  It’s  still  possible  to  find  a  better  solution  through  further 

exploration.

FIGURE 18-2: 

Local search 

explores the  

landscape by  

hill climbing.

---

CHAPTER 18