To the Ends of the Hills: Problem-solving Heuristics

Suppose you are are a farmer, and you are transporting your goods to market. You have a fox, a chicken, and some grain. You come across a river and a boat that holds you and one other item. If you leave the fox with the chicken, he will eat the chicken. If you leave the chicken with the grain, she will eat the grain. How can you safely ferry all of your goods across the river?

Algorithms v. Heuristics

In a previous post, we drew a distinction between routine and insight problem solving. Routine problems are nice because we see them all the time. Because of that, we have an available procedure that can be easily deployed. Insight problems, however, are more stubborn because we don't have a ready-made strategy. Instead, we need to invent or apply creative approaches to the problem.

In addition to distinguishing between types of problems, a distinction can also be made for the problem-solving process. On one hand, we have algorithms, which are problem-solving procedures that guarantee an answer. The start state is well defined, and you also have a set of operators that transform the problem from one state to another. You apply the operators in a prescribed order until the solution is generated. It might take some time, but you will eventually arrive at a solution. Long division is an example of an algorithm because it is a step-by-step procedure that will guarantee a solution. Unfortunately, that algorithm only works for dividing numbers. You can't use it to pick an outfit for work. 

Contrast an algorithm with a heuristic, which trades off a guaranteed solution with its broad applicability. An algorithm only works if one exists, and it is problem specific. Heuristics, on the other hand, apply to a broad range of problems. The tradeoff is that a heuristic might not give you an answer (or it might provide a sub-optimal solution). Let's take a look at two problem-solving heuristics. 

"Trying to get up that great big hill (of hope)" -- 4 Non Blondes

The first heuristic is called hill climbing (or difference reduction) [1]. It's called "hill climbing" because you can envision the problem space as a mountain. At the base is the starting point (or initial state). The top of the mountain is the solution (or goal state). The hill climbing heuristic selects an operator that reduces the difference between the current state and the eventual goal state. 

To make this more concrete, let's apply the hill climbing heuristic to the farmer's dilemma that opened this post. I don't have an algorithm for solving this problem because I've never seen it before [2]. Before I begin, there is only one problem-solving operator that can change the problem state, and that is loading something onto the boat and moving it to the other side of the river. There are two constraints. I can't leave the fox and chicken alone, and I can't leave the chicken and grain alone. 

To apply the hill-climbing heuristic, I need to select an object. The chicken is the only option because the fox isn't interested in the grain. In terms of climbing the hill, it gets me one step closer to the top. I go back across the river, and I now have to select something else. It doesn't seem to matter which object I choose, so I select at random. I pick the grain. I move that over to the other side of the river, and I am one step closer to the solution. Warning: Here comes the hard part. I have to take something back across the river because it will violate one of the problem-solving constraints (e.g., leaving the chicken with the delicious grain). This goes against climbing the hill because I have to take a step backwards, away from the goal. 

As you can see, hill-climbing might not guarantee a solution. The reason this puzzle is potentially difficult is precisely because you have to make a move that gets you further away from the goal state. 

Means-ends Analysis: It's a Means...to an End!

The second problem-solving heuristic is called means-ends analysis, and it attempts to solve a larger problem (or goal) by breaking it down into smaller sub-problems (or subgoals). Suppose my goal is to drive to work. But when I try to start my car, it fails to turn over. Now I have a problem: How do I get to work? I could call a coworker, but I don't remember her number. Thus, I have to set another subgoal to find her number and give her a call.

Let's take another example. Means-ends analysis works really well for the 3-disk version of the Tower of Hanoi. Here is the initial state:

My top-level goal is to get all the disks on the right most peg. Since that currently isn't possible, I set a subgoal to move the blue disk. But the purple disk is on top of it, so I set another subgoal to move the purple disk out of the way. But the purple disk is blocked by the red disk, so I set a subgoal to move the red disk to a different peg.

As you can see, I now have a bunch of sub-goals hanging around. It's hard to keep track of them because my working memory is severely constrained. Thus, the more disks I have, the more subgoals I collect, which adds an additional burden to working memory.

The STEM Connection

Both math and science education might benefit from knowing about the different problem-solving heuristics. Let's consider science first. One of the top-level goals of science is to build an explanation for some observable phenomenon. If we use the language developed here, the top-level goal is to construct a model or an explanation. The research question or the hypothesis is the problem to be solved. That problem can be decomposed into smaller problems or subgoals. Suppose I want to measure the distance a bee flies after leaving the hive. Thus, I set a subgoal to figure out how to track individual bees. That measurement problem opens several other interesting subgoals.

For math education, it might be useful for students to know the distinction between an algorithm and a heuristic. Some math problems are encountered so frequently that the field of mathematics has developed an algorithm that can be learned and executed whenever the conditions of the problem match the algorithm. But other math problems might not have a ready-made solution (e.g., How many pounds of trash are generated by New York city in a day?). When students encounter these types of questions, then it is time to find a problem-solving heuristic that drives toward a solution. Finding a heuristic, one might say, becomes the first subgoal in finding a solution! 


Share and Enjoy!

Dr. Bob

For More Information

[1] I consulted John Anderson's very approachable textbook Cognitive Psychology and its Implications for the description of the difference reduction and means-ends analysis heuristics. I highly recommend picking up a copy of this book.

[2] Actually, that's not 100% accurate. The fox, chicken, and grain problem is eerily reminiscent of the Hobbits and Orcs problem that we encountered in a previous post.