Puzzles for Programmers and Pros

6.10. Overloaded Scheduling and Freezing Crystals

When first faced with a problem, try pure greed (look for moves that lower the cost). If that doesn't work or if it reaches a dead end, then you can try case analysis as we did for Sudoko. If there are too many cases, then try dynamic programming. If all these fail, it is time for heuristic search techniques along with some bound on the optimum.

A heuristic technique is one that is not guaranteed to work perfectly, but often (you hope) works well. Greed is, of course, a great heuristic technique but can be brittle, as we saw in the solution to the "Finding a Schedule that Works" puzzle.

The principle of exploratory heuristic techniques is that they take anti-greedy moves sometimes. They do this in order to explore the search space. If each problem configuration could be encoded as some scalar value (horizontal axis of Figure 2-23), then the squiggly line in Figure 2-23 represents the cost of each configuration.

A greedy approach will make moves that decrease cost only. An exploratory heuristic technique will sometimes make moves to more costly states in the hopes of leaving a local minimum (see Figure 2-24). If this reminds you of high school chemistry notions of activation energy, you have the right intuition.

Figure 6.23. The horizontal axis represents the search space. The vertical represents the cost. A greedy approach, given a location in the search space, will perform moves that decrease cost. So the arrows always start ...