A locally optimal solution is the best solution within a particular area of the search space. It may still be worse than the global best solution found across the entire search space. section 1.9
Use the distinction to reason about optimization problems:
- A nearby restaurant can be the best local choice without being the best restaurant in the country or world. section 1.9
- Packing a car trunk illustrates how many valid arrangements can differ in quality while obeying space and weight constraints. section 1.9
- Evolutionary algorithms help avoid local optima by exploring multiple areas simultaneously through a population of candidate solutions. section 4.2
Knapsack search
In a knapsack with a 9 kg capacity, selecting items 1, 3, and 7 weighs 9 kg and has value $14. Another combination may look attractive nearby, but the goal is to compare solutions across the wider search space rather than stop at the first good arrangement. section 4.2
Figure 4.4 A simple example Knapsack Problem
Visualizes the constrained knapsack setup, making the search space and competing candidate solutions easier to inspect. section 4.2
