Hill Climbing

Local Search and Optimisation

AI, Artificial and Computational Intelligence
AI, ACI, Local Search, Optimisation, Hill Climbing, Local Beam Search, N-Queens

Local Search and Optimisation #

Local search improves one or a few complete candidate solutions by moving through their neighbourhoods. It is especially useful when the final configuration matters but the path used to reach it does not.

– Local Search Algorithms & Optimisation Problems

  • Hill Climbing Search
  • Local Beam Search
  • Online Search Agents

Learning Objectives #

  • distinguish path optimisation from state optimisation
  • explain states, neighbours and objective functions
  • apply hill climbing and its variants
  • recognise local maxima, plateaus and ridges
  • explain random-restart and stochastic hill climbing
  • describe local and stochastic beam search and trace one beam update

Big Picture #

flowchart TD
    S["Current state"] --> N["Generate neighbours"]
    N --> E["Evaluate values"]
    E --> B["Choose candidate"]
    B --> S
    B --> G["Stop condition"]

    style S fill:#E1F5FE
    style N fill:#FFF9C4
    style E fill:#EDE7F6
    style B fill:#C8E6C9
    style G fill:#C8E6C9

1. Path Optimisation vs State Optimisation ☆ #

In classical route search, the path is the solution. The agent must remember how it travelled from the start to the goal.