Hill Climbing
Always move to a better neighbor — the classic greedy trap.
1
3
7
2
4
9
6
5
8
Start at index 2 (value 7). Each step moves right only if the value increases.
Current position: 2 (value 7)
Local maximum reached — no better right neighbor. The global peak is at value 9 (index 5).
Hill climbing keeps only one state and never backtracks — hence its tendency to stick on local maxima. Random restarts, simulated annealing or tabu search escape this.