Hill climbing algorithm simple example

Question

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 1

Hill climbing has no guarantee against getting stuck in a local minima/maxima. However, only the purest form of hill climbing doesn't allow you to either backtrack.

A simple riff on hill climbing that will avoid the local minima issue (at the expense of more time and memory) is a tabu search, where you remember previous bad results and purposefully avoid them.

Answer 2

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.

Answer 3

the path according to pure hill climb will be a-> J -> k if you expand children's from left to right, if you expand them from right to left then you will get in this local minima A -> F -> G, but generally we expand from left to right.

Answer 4

one of the problems with hill climbing is getting stuck at the local minima & this is what happens when you reach F. An improved version of hill climbing (which is actually used practically) is to restart the whole process by selecting a random node in the search tree & again continue towards finding an optimal solution. If once again you get stuck at some local minima you have to restart again with some other random node. Generally there is a limit on the no. of time you can re-do this process of finding the optimal solution. After you reach this limit, you select the least amongst all the local minimas you reached during the process. Though it is still not complete but this one has better chances of finding the global optimal solution.

Answer 5

Actually in Hill Climbing you don't generally backtrack, because you're not keeping track of state (it's local search) and you would be moving away from a maxima. Neither backtracking or Tabu Search help answer the question either: the former just moves you away from a local maxima and the latter keeps you from revisiting the same local maxima. Neither would help you hit a global maxima. – Tyson Oct 16 '12 at 22:59

"where you remember previous bad results and purposefully avoid them" I can't agree, you mark as taboo also good solutions, but You don't want to follow same path again. –

Answer 6

You could try to use a technique called simulated annealing to prevent your search to get stuck on to local minimums. Essentially, in simulated annealing, there is a parameter T that controls your likelihood to make a move to sub-optimal neighborhood states. If T is high, you are more likely to make a sub-optimal move to a neighboring state and thereby might escape a local minimum when stuck there, which you wouldn't if you used normal hill climbing.

Answer 7

Here is the solution:

A -> F, with the least possible cost F -> G with cost 3 but there is no path.

Restart from the least possible cost other than G, well it's E because E was already inserted in the queue/stack/priority queue or whatever data structure you use.

Thus E -> I but I has higher cost than E thus you are stuck :S

Restart from the least cost other than F E & G, thus we pick J because J has lower cost than B with difference of 2 i.e. J = 8 B = 10

J->K with cost 0 thus K is the goal

NOTE: The proposed variation of hill-climbing to pick a point randomly, but picking the least cost other than the already visited nodes is better than picking randomly.

ANOTHER NOTE: is that when node E didn't visit I because I has higher value than E, the algorithm already inserted it in the data structure, thus picking the least cost other than the already visited would create a new path from I because I was never visited and thus it has lower value than J, this is the only path that i've skipped.