Overview
Hill Climbing is a simple local search method that accepts improving moves until no neighbor improves the current solution.
CoreSource checked
Hill Climbing
Improves a solution by repeatedly moving to a better neighboring solution.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Optimization
- Difficulty
- Beginner
- Family
- Local Search
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 4
- Code example
- Ready
- Visualization
- Ready
Core Concepts
local searchneighbor moveobjective comparisonlocal optimum
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(1) per neighbor
Average
Problem dependent
Worst
Problem dependent
Space
O(1) plus candidate storage
When to Use
- Use when a cheap neighbor move often improves a rough initial solution.
- Use when quick heuristic optimization is a central requirement.
When Not to Use
- Avoid when escaping local optima is essential and no restart or randomness is planned.
- Avoid when the objective is noisy, discontinuous, or violates the method's assumptions.
What It Does
- Evaluates neighboring candidates
- Moves to a better neighbor
- Stops at a local optimum
Use Cases
- Quick heuristic optimization
- Local improvement after random initialization
- Small combinatorial searches
Inputs
- Initial candidate
- Neighbor generator
- Objective function
Outputs
- Locally improved candidate
Key Formulas (1)
Move rule
accept neighbor if score(neighbor) > score(current)
accept neighbor if score(neighbor) > score(current)Keeps only moves that improve the objective in the chosen direction.
Pseudocode
- 1.Start with an initial candidate
- 2.Generate neighboring candidates
- 3.Move to a neighbor if it improves the objective
- 4.Repeat until no neighbor improves the result
Canonical Example
- Input
- start route cost = 20, neighbor cost = 17
- Output
- move to cost 17
- Explanation
- The method accepts the better neighbor and continues searching locally.
Implementation Notes
- Keep the neighbor generator small enough that each iteration stays cheap.
- Track objective value, step size, and convergence criteria at each iteration.
- Keep a tiny example with expected output beside the implementation.
Common Pitfalls
- The first local optimum found may be far from the global optimum.
- Stopping too early or using unscaled variables can make a good method look broken.
- Not defining boundary, empty, or degenerate inputs before implementation.
Interactive Mechanism Walkthrough
Iterative Convergence & State TrajectoryShow a point climbing uphill on a landscape until it reaches a local peak.
Step 1 of 4: Start with an initial candidate
optimization-landscapeNotes
Random restarts are often used because plain hill climbing can get stuck.
Sources (1)
What each reference supports for this entry.
Artificial Intelligence: A Modern Approach
BookReference text for search, local search, beam search, and constraint-satisfaction backtracking.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageAlternative toSimulated Annealing
Hill climbing is a simpler local search without temperature-based escape moves.
Conceptual neighborTabu Search
Both move through neighboring solutions using local search.
Related Algorithms
Tags
OptimizationLocal SearchMetaheuristic