0
$\begingroup$

Are hill climbing variations (like steepest ascent hill climbing, stochastic hill climbing, random restart hill climbing, local beam search) always optimal and complete?

$\endgroup$
0
1
$\begingroup$

No, they are prone to get stuck in local maxima, unless the whole search space is investigated.

A simple algorithm will only ever move upwards; if you imagine you're in a mountain range, this will not get you very far, as you will need to go down before going up higher. You can see that going down a bit will have a net benefit, but the search algorithm will not be able to see that.

Random restart (and similar variations) allow you to do that, up to a point. Imagine you have ten people that you parachute over your mountain range, but they can only go upwards. Now you've got a better chance of finding a higher peak, but there's still no guarantee that any of them will reach the highest one.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy