When will Hill climbing searches fail? Do Steepest ascent hill climbing always find solutions? How might some problems be overcome in the search?

Hill climbing only fails when you aren''t wise enough to sit on the top

or if you neglect to take enough rope, or check the weather before you set off.

And if your name is Jack, be careful not to accompany anyone named "Jill" on your hill climbing expedition.

and remember, Humpty Dumpty was pushed...

at infinitely tall hills.

quote: Original post by looking_nice
When will Hill climbing searches fail? Do Steepest ascent hill climbing always find solutions? How might some problems be overcome in the search?

There''s plenty of literature out there on this topic looking_nice. Basically though, Hill Climbing algorthms (gradient ascent/descent) are likely to fail in domains with a multi-modal cost space. Furthermore, they generally don''t work in stochastic domains (where the value of the function at any point can vary in time with a stochastic component).

Solutions to these problems are methods like Simulated Annealing, Gibbs Sampling, Genetic Algorithms, hybrid algorithms, etc.

Take a look at what Google returns for a search on Hill Climbing algorithms and also on the other methods I have mentioned.

Good luck,

Timkin