Algorithms For Dummies

Explaining hill climbing with n-queens

You can easily find analogies of the techniques employed by local search because 

many phenomena imply a gradual transition from one situation to another. Local 

search isn’t just a technique devised by experts on algorithms but is actually a 

process that you see in both nature and human society. In society and science, for 

instance, you can view innovation as a local search of the next step among the 

currently  available  technologies: 

https://www.technologyreview.com/s/ 

603366/mathematical-model-reveals-the-patterns-of-how-innovations- 

arise/

. Many heuristics derive from the physical world, taking inspiration from 

the force of gravity, the fusion of metals, the evolution of DNA in animals, and the 

behavior of swarms of ants, bees, and fireflies (the paper at 

https://arxiv.org/ 

pdf/1003.1464.pdf

 explains the Lévy-Flight Firefly algorithm).

Hill climbing takes inspiration from the force of gravity. It relies on the observa-

tion that as a ball rolls down a valley, it takes the steepest descent, and when it 

climbs a hill, it tends to take the most direct upward direction to reach the top. 

Gradually, one step after the other, no matter whether it’s climbing up or 

down, the ball arrives at its destination, where proceeding higher or lower isn’t 

possible.

---

344

 

   

  PART 5