Hill climbing algorithm simple example
I am a little confused with Hill Climbing algorithm. I want to "run" the algorithm until i found the first solution in that tree ( "a" is initial and h and k are final states ) and it says that the numbers near the states are the heuristic values. Here's the tree:
My question : i am trying to run hill climbing on the tree, so ok we start a-> f-> g and then what ??finish(without result) , but I read that hill climbing can't go back and make a new choice(example j or e) ? Is this right ? If i can go back then how ? i mean where we change our initial choice example we choose e instead of g or j instead of f
Sorry if my question is too simple .
Answer
A common way to avoid getting stuck in local maxima with Hill Climbing is to use random restarts. In your example if G is a local maxima, the algorithm would stop there and then pick another random node to restart from. So if J or C were picked (or possibly A, B, or D) you would find the global maxima in H or K. Rinse and repeat enough times and you'll find the global maxima or something close; depending on time/resource limitations and the problem space.
Note that Local Search like Hill Climbing isn't complete and can't guarantee to find the global maxima. The benefit, of course, is that it requires a fraction of the resources. In practice and applied to the right problems, it's a very effective solution.