When you just need a good answer fast
A heuristic is a practical rule of thumb that usually produces a decent answer quickly, without any guarantee of being optimal. When problems are too large or too hard for exact methods, heuristics are often the only realistic option.
Local search
Local search starts from some solution and repeatedly makes a small change that improves it, such as swapping two elements or moving one item. Each candidate reachable by a single change is a neighbor. You keep stepping to a better neighbor until none is better, reaching a local optimum.
The trap of local optima
The danger is getting stuck at a local optimum, a solution better than all its neighbors but not the global best. The landscape can have many valleys, and simple hill climbing settles in the nearest one.
- Restarts from different starting points explore more valleys.
- Random moves that occasionally accept a worse step, as in simulated annealing, help escape shallow traps.
- Memory of recent moves, as in tabu search, avoids cycling back.
Key idea
Heuristics and local search trade guarantees for speed, improving a solution through small neighbor moves while using restarts and randomness to escape local optima.