2

I have implemented the hill climbing algorithm, with side away steps, which can increase the rate of success, because, when you don't have new generated states, you can go back to previous level and choose from there another state.

What should I do when new generated states have bigger distance to the goal than the parent state?

Do I have to go back to the previous level and choose another state, from which I will continue? Or I continue with one of the states generated which has bigger distance?

nbro
  • 42,615
  • 12
  • 119
  • 217
Darius Ionut
  • 31
  • 3

1 Answers1

0

If you don't go back to your previous state, the best you will do is get stuck in a local maxima. So, to answer your question, yes, backtrack if your hill climbing has failed. The number of times you want to do this depends on you and your implementation. Hill climbing does not guarantee to find the global maxima and, in many cases, you won't know if it is a local maxima or a possible global maxima, unless you try the hill climbing a few times.

If you haven't already seen its Wikipedia article, it has a cool graph showing what I mean.

nbro
  • 42,615
  • 12
  • 119
  • 217
solarflare
  • 324
  • 2
  • 10