Don't climb the wrong hill: In algorithms and in life, its easy to end up on the wrong one

A classic problem in computer science is hill climbing.  Imagine you are dropped at a random spot on a hilly terrain, where you can only see a few feet in each direction (assume it’s foggy or something).  The goal is to get to the highest hill.

Local_maximum

Consider the simplest algorithm.  At any given moment, take a step in the direction that takes you higher.  The risk with this method is if you happen to start near the lower hill, you’ll end up at the top of that lower hill, not the top of the tallest hill.

Interesting CS analogy to one's own career.

views
6 responses
My career seems to always be attracted to the nearest cliff.
In computational biophysics the related problem is to find the deepest valley (i.e., the global minimum). Some of the algorithms for doing that are pretty wild, but here's a simple one:

1) Step in a random direction
2) If you end up at a lower point, stay there
3) If you end up at a higher point, stay there with probability exp(-dX) where dX is the difference in altitude. Otherwise return to your original place.
4) Repeat ... a lot.

With this algorithm, you're guaranteed to find the lowest point. Same algorithm can be used to find the global maximum as well. But it might take you awhile -- but what is true in computational biophysics is true in real life too. ;)

4 visitors upvoted this post.