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$
1
  • $\begingroup$ Please, do not edit your post just for the sake of editing or just because you don't like to see my nickname or profile picture under your post. This post is about hill climbing, optimality and completeness, so the tags that you removed should not have been removed. Take a look at this for more details. $\endgroup$
    – nbro
    Mar 29 at 15:17
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