by Albert Major

Introduction to Artificial Intelligence

Local Search Algorithms

• A method to explore search spaces with limited resources
• Aims to find solutions that are "good enough" rather than optimal
• Focuses on the final configuration, not the path to get there

Key Characteristics:

• Examines ONLY direct neighbouring states to decide next moves
• Does NOT keep track of previously visited states
• Does NOT worry about potentially better solutions elsewhere

Hill-Climbing

Definition: A local search algorithm that always moves towards a better state

“Simple hill climbing” examples

• Analogy: Like climbing a mountain in fog with amnesia
• Process:
  1. Tracks one current state
  2. Looks at immediate neighbours
  3. Moves to the neighbour with the highest value
  4. Stops when it reaches a peak (no better neighbours)
• Problems: Can get stuck in local maxima, plateaus, or ridges
  • (Local maxima: Getting stuck on a small peak, missing the highest point)
  • (Plateaus: Flat areas where it's hard to decide which way is "up")
  • (Ridges: Narrow paths that are hard to follow to the top)

example of places where hillclimbing might get stuck

Types of Hill-Climbing

• Simple hill climbing:
  • Always moves to the best neighboring state
  • Stops when no better neighbor is found

Hill-Climbing can be improved with allowing limited sideways moves. e.g:

• Stochastic hill climbing:
  • Randomly selects among uphill moves
  • Probability of selection related to how much better the move is