Example of problems in Simple Hill Climbing algorithm

Question

What are some examples that cause Simple Hill Climbing to reach problems like local maxima, ridges and alleys, and plateau problem(s)? I have tried searching:

• Link one: which gives a fairly good example of Simple Hill Climbing stuck-in-local-maxima problem in block arrangements. However, it does not show the steps.
• Link two: which gives steps to finding the solution in SHC. However, I don't understand how h(1) can be -6 when all there are only four blocks and four of them are misplaced, therefore only yielding -4. It also doesn't show the problem(s) encountered by SHC.
• Link three: I understand how the concept of reaching state 'g' makes your algorithm reach a local maximum and get stuck. However, it's rather ambiguous what the states are and I don't know what state 'g' and the final states refer to.

From the lecture note I read, I was given the TSP problem. The graph was a complete graph with four nodes: A, B, C and D. We used both Simple Hill Climbing and Steepest-Ascent Hill Climbing to solve the problem. The heuristic value used to solve that problem was the total distance of each state. We can explore other neighbouring states by switching positions of the characters "ABCD" using 6 different combinations (first letter <-> second, second <-> third, etc.). However, in the example given, it did not show what exactly "stuck at a local maximum" is. Neither did it show the ridges and alleys problem nor the plateau problem.

Could someone give me an example of how we reach those problems and what those problems actually are in examples (I understand the definition of each problem: here and here)? For reference, this below is the image of the TSP problem I mentioned:

Answer 1

When your simple hill climbing walk this Ridge looking for an ascent, it will be inefficient since it will walk in x or y-direction ie follow the lines in this picture. It results in a zig-zag motion.

To reach this state, given a random start position, the algorithm evaluates the 4 positions (x+1,y) (x-1,y) (x, y+1) (x, y-1) (for a step of 1) and pics the highest. So it will start to move toward the ridge.

Let's illustrate this behavior with the previous picture. Given a start at the origin (0,0), and a step of 1. The thin dark lines intersect on the surface are the unit point ((0,1),(0,2),...,(1,0),...) images through the function. The algorithm chooses in those points, but only those directly adjacent (because it moves along the axis). This is the path it will take. (forgive my poor paint skills).

In the link 2, to compute the heuristic function, you evaluate each block, if the block is misplaced (aka not at the right index on the pile) each block under it add -1, otherwise, each block under it add +1. h(1) = -3 -2 -1 (A is misplaced, there is 3 blocks under it so -3, same for B but 2 blocks so -2, C -1 and D has no block under it so does not add anything)

For the plateau problem, if you reach a flat surface or almost flat, the algorithm will not be able to find a better position.

I hope I understood your question.