Exhaustive Search: Try Everything

How to read this

Traveling Salesman Problem (TSP). Every city pair has a distance. The blue loop is the tour being measured right now; the thick green loop is the shortest tour found so far. The small numbers next to cities give the visiting order. The start city is fixed, so there are (n−1)! orders of the other cities, and each tour shows up twice (once in each direction), which is why only (n−1)!/2 tours are really different.

0/1 knapsack. Each box is an item (weight w, value v). Highlighted boxes are in the current subset. The bar underneath fills with their weights; the dashed line is the capacity W. Red means the subset is too heavy (not feasible). The table lists every subset, like Levitin's Figure 3.8, and reaches 2ⁿ rows.

Assignment. Rows are people, columns are jobs. A candidate picks one cell in each row, all in different columns: that is a permutation, and there are n! of them. Blue cells are the current pick; green-outlined cells are the best pick so far.

Explosion chart. The y-axis is logarithmic: each grid line is 10× the one below. Dashed lines show how many candidates a computer checks in a second, a day, a year and the age of the universe.

Try this

1. In TSP with the 4-city preset, find the two tours of length 11. Why are they "the same" tour? Now tick skip mirror tours: the tour count drops from 3! = 6 to 3!/2 = 3 and the answer does not change.
2. Add cities by clicking empty space until n = 8. The player now has thousands of steps. Drag the speed slider to the max and watch the best-so-far tour jump less and less often.
3. Knapsack: set the capacity to 19 (the total weight). Every subset is feasible now, so the answer is "take everything". Set it to 2: only the empty set fits.
4. Assignment: in Levitin's matrix the smallest entry is 1 (Person 3, Job 3). Build your own 3×3 matrix where the optimal assignment does not use the smallest entry (Levitin Exercise 3.4.5).
5. Explosion chart: switch the speed from 10⁹ to 10¹⁰ checks per second. How many more cities does 10× more speed buy you for n!? (Answer: about one.)