Local search algorithms focus on finding solutions by moving through the search space locally, usually from one state to a neighboring state.
They don’t build or explore a full search tree. Instead, they keep a single current state and move to a better neighbor.
Best used for optimization problems, where the goal is to maximize or minimize some objective function.
Examples:
| Algorithm | Description | Pros | Cons |
|---|---|---|---|
| Hill Climbing | Moves to the neighbor with the highest value (best improvement) | Simple, fast | Can get stuck in local maxima, plateaus, or ridges |
| Simulated Annealing | Sometimes accepts worse moves to escape local optima, gradually reduces randomness | Can escape local optima | Slower than hill climbing |
| Local Beam Search | Keeps k states instead of one, and picks the best k successors | More diverse search | Still may converge to local optima |
| Genetic Algorithms | Population-based search using selection, crossover, and mutation | Very effective for complex spaces | Requires tuning and is stochastic |
🧠 Analogy: Climbing a hill in fog. You can see around you but not the entire mountain. You stop when no neighbor is higher — even if you're not at the highest peak (global maximum).
| Concept | Meaning |
|---|---|
| Local Search | Searches from one state to its neighbors |
| Goal | Optimize a function (not just find a path) |
| Memory Efficient | Only stores current state |
| Useful for | Large or infinite state spaces |
| Risk | Getting stuck in local optima |
Open this section to load past papers