Hill Climbing

hill_climbing

Hill climbing can get stuck for the below reasons

  • Local maxima
  • Ridges: Result in a sequence of local maxima that is very difficult fro greedy algorithms to navigate
  • Plateaus: flat spaces like the sholder

pseudo code for local maximum hill climb

function HILL-CLIMBING(problem) # returns the a local maximum
	current <- problem.INITIAL
	while true do
		neighbor <- nextHighest # Look left, look right, choose the higher value
		if VALUE(neighbor) <= VALUE(current): return current # reached local peak
		current <- neighbor
		

Algorithms

  • Stochastic hill climbing
  • First-choice hill climbing: implements stochastic hill climbing by generating successors randomly
  • Random-restart hill climbing (if you don't succeed try try again)