4.1 Local Search and Optimization Problems
Local search keeps one or more candidate states and seeks a high-quality solution rather than a path. Hill climbing follows improving neighbors; it can stall at local maxima, plateaus, or ridges.
Problem-solving · Chapter 4
Search in Complex Environments
When a full state-space plan is impractical, agents can optimize locally, reason about uncertain outcomes, maintain beliefs, or learn while acting.
Chapter guide
4.2 Local Search in Continuous Spaces
For continuous variables, gradient-based methods follow derivatives, while stochastic and derivative-free methods handle rough objectives or unavailable gradients.
4.3 Search with Nondeterministic Actions
When an action can have several outcomes, a solution is a conditional plan: an action followed by a response for each possible resulting state.
4.4 Search in Partially Observable Environments
An agent cannot identify the exact state from its percepts, so it reasons over a belief state—a set or probability distribution of possible states.
4.5 Online Search Agents and Unknown Environments
Online agents interleave computation and action, discovering transitions as they go. They balance exploration with progress and may use trial-and-error or real-time search.
Key terms and local-search intuition
Objective function: scores candidate states. Neighbor: a state reachable by one small change. Local optimum: no examined neighbor improves the score, although a better state may exist elsewhere. A belief state instead represents possible world states when observations are incomplete; nondeterministic planning branches over possible action outcomes.
At the default position 2, the neighbor at 3 has value 5, below the current value 7, while position 1 has value 3. The climber stops at this local peak even though position 8 has the global value 14. Random restarts or broader exploration can help, but this demo intentionally uses neither.
Interactive lab
Hill climbing on a landscape
The agent checks its immediate left and right neighbors, then moves to the higher one. The curve has a local peak and a higher global peak: a greedy local method can get stuck.
Position (horizontal) · objective value (vertical)
Current state: 2 · value —
Best neighbor: —
Ready to climb.
The chart is a fixed discrete objective. This simple algorithm stops when no adjacent state is strictly better; it does not guarantee a global optimum.
Step rule and complexity
inspect left/right; move to the higher-valued neighbor only if it is strictly better; otherwise stop. Inputs are the fixed values array v[0..n−1] and current index i. The demo checks at most two neighbors per step, so one step is O(1) time and O(1) auxiliary space. The landscape itself stores O(n) input values and the SVG/O(n) labels are visualization memory, not climber working memory. Across a strictly improving run, at most n−1 moves occur: O(n) total time and O(1) algorithmic auxiliary space. The claim assumes the finite, static landscape shown and strict-improvement stopping.