For example, I have the following problem:
The only operators I can apply are:
- Place the uppermost block from the structure down
- Place a block that is not in the structure to the uppermost position of the structure
I have a heuristic function of:
- h(n) = +1 for every supporting block if a block is placed correctly and -1 for every supporting block if a block is placed incorrectly.
In this example, "A" block is placed correctly, hence I get a +3 for each supporting block below A. "D" is placed incorrectly, thus I get a -2. C is placed correctly, I get another +1. Therefore, my heuristic function now returns a value of 3 + 1 - 2 = +2.
Now based on the algorithm here, the algorithm will only quit when it reaches its goal state and that it will only choose the next state as its current state if it yields a better heuristic value. However, it is no longer possible to proceed in the case I made above. Putting A down from the structure will yield a heuristic value of -1 which is worse than the previous value (+2).
Why did I modify the example? I want to show when we encounter local maxima problem in Simple Hill Climbing algorithm, and this is a local maxima problem, right? Another question, as the algorithm says that it will quit [only] when it reaches its goal state, it will never quit. Or is it correct of me to assume that it will also quit when the other neighbouring states no longer give a better result?
Hill Climbing is a local search and guarantees to find optimal solutions for convex problems. For non-convex problems it can get stuck (terminates) in a local optima.
There is an "alternative version" of Hill Climbing called Enforced Hill Climbing (EHC) that performs breadth-first search until a more promising state is found to "escape" sich local optima. EHC is often used for non-optimal (satisficing) planning as the search is only stopped if the goal is not reachable.