Algorithmic Problem Solving

The examples in this chapter all involve getting a number of people or things across a river under certain constraints. We use them as simple illustrations of “brute-force” search and problem decomposition.

Brute-force search means systematically trying all possibilities. Brute force does not require any skill, but it does require a lot of careful and accurate work. Using brute force is not something human beings are good at; lots of careful, accurate work is something more suited to computers. But brute force is not even practical for implementation on a computer. The amount of work involved explodes as the problem size gets bigger, making it impractical for all but toy problems. Nevertheless, it is useful to know what brute force entails, because it helps to understand the nature of problem solving.

Problem decomposition is something we humans are much better at. Problem decomposition involves exploiting the structure of a problem to break it down into smaller, more manageable problems. Once a problem has been broken down in this way, brute force may be applicable. Indeed, it is often the case that, ultimately, brute force is the only solution method, so we cannot dispense with it. But it is better to explore problem decomposition first, postponing the use of a brute-force search for as long as possible.

All river-crossing problems have an obvious structural property, namely ...