Hillclimbing
Hill climbing is an iterative local-search technique that moves from a candidate solution to a neighboring solution with a better objective value.
Optimization Algorithms: AI techniques for design, planning, and control problems
A local search algorithm that repeatedly moves from a candidate solution to an improving neighboring solution.
- How it is used
- Uses heuristic-guided local search for graph paths, puzzle states, and routing problems.
- How deep it goes
- Defines neighbor-based improvement, gives pseudocode and implementations, then stops short of guaranteed global optimality.
- Examples
- Demonstrates route finding, an eight-puzzle solver, misplaced-tile costs, randomized routes, and neighborhood-size tuning.
- What you can do after
- Apply hill climbing by defining states, neighbors, and a cost function, then tuning neighborhood size for routing.
Advanced Algorithms and Data Structures
Hill climbing is an iterative local-search technique that moves from a candidate solution to a neighboring solution with an improved objective value.
- How it is used
- Improves approximate solutions for optimization problems such as graph layouts, routing, schedules, and component designs.
- How deep it goes
- Defines neighborhood exploration and improvement-based updates, then explains failure on local minima and plateaus.
- Examples
- Uses vertex movements in graph embeddings and a marble moving across a cost landscape.
- What you can do after
- Apply it to improve a computable objective when differentiability is unavailable, while recognizing approximate results.
Read how Advanced Algorithms and Data Structures explains hillclimbing →
Related concepts
- Pareto frontiercontrasts with · A Pareto frontier is the set of feasible solutions that are not dominated by any other solution across the objectives being optimized.
- local searchkind of · Local search is an optimization technique that iteratively modifies a candidate solution by exploring neighboring alternatives according to an improvement rule.
- scoreuses · A numerical measure or rating of the performance, quality, or progress of a result, option, or participant.
- COPROused by · COPRO is a DSPy prompt-optimization technique that iteratively generates and evaluates alternative prompt instructions to improve their performance.
- simulated annealingcontrasts with · Simulated annealing is a stochastic optimization method that gradually reduces the probability of accepting worse solutions to escape local optima.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.