The Difference-Reduction method of Problem Solving

People experience difficulty in solving a problem at points where the correct solution involves increasing the differences between the current state and the goal state.
A common method of problem solving, particularly in unfamiliar domains, is to try to reduce the difference between the current state and the goal state. For instance, consider my solution to the eight puzzle. There were four options possible for the first move. One possible operator was to move the 1 tile into the empty square, another was to move the 8, a third was to move the 5, and the fourth was to move the 4. I chose the last operator. Why? Because it seemed to get me closer to my end goal. I was moving the 4 tile closer to its final destination. Human problem solvers are often strongly gov- erned by difference reduction or, conversely, by similarity increase. That is, they choose operators that transform the current state into a new state that reduces differences and resembles the goal state more closely than the current state. Difference reduction is sometimes called hill climbing. If we imagine the goal as the highest point of land, one approach to reaching it is always to take steps that go up. By reducing the difference between the goal and the cur- rent state, the problem solver is taking a step “higher” toward the goal. Hill climbing has a potential flaw, however: By following it, we might reach the top of some hill that is lower than the highest point of land that is the goal. Thus, difference reduction is not guaranteed to work. It is myopic in that it considers only whether the next step is an improvement and not whether the larger plan will work. Means-ends analysis, which we will discuss later, is an attempt to introduce a more global perspective into problem solving.
One way problem solvers improve operator selection is by using more so- phisticated measures of similarity. My first move was intended simply to get a tile closer to its final destination. After working with many tile problems, we begin to notice the importance of sequence—that is, whether noncentral tiles are followed by their appropriate successors. For instance, in state (o) the 3 and 4 tiles are in sequence because they are followed by their successors 4 and 5, but the 5 is not in sequence because it is followed by 7 rather than 6. Trying first to move tiles into sequence proves to be more im- portant than trying to move them to their final destinations right away. Thus, using sequence as a measure of increasing similarity leads to more effective problem solving based on difference reduction (see N. J. Nilsson, 1971, for further discussion).
The difference-reduction technique relies on evaluation of the similar- ity between the current state and the goal state. Although difference reduction works more often than not, it can also lead the problem solver astray. In some problem-solving situations, a correct solution involves going against the grain of similarity. A good example is called the hobbits and orcs problem:
On one side of a river are three hobbits and three orcs. They have a boat on their side that is capable of carrying two creatures at a time across the river. The goal is to transport all six creatures across to the other side of the river. At no point on either side of the river can orcs outnumber hobbits (or the orcs would eat the outnumbered hobbits). The problem, then, is to find a method of transporting all six creatures across the river without the hobbits ever being outnumbered.
Stop reading and try to solve this problem.  correct sequence of moves. Illustrated are the locations of hobbits (H), orcs (O), and the boat (b). The boat, the three hobbits, and the three orcs all start on one side of the river. This condition is represented in state 1 by the fact that all are above the line. Then a hobbit, an orc, and the boat proceed to the other side of the river. The outcome of this action is represented in state 2 by placement of the boat, the hobbit, and the orc below the line. In state 3, one hobbit has taken the boat back, and the diagram continues in the same way. Each state in the figure rep- resents another configuration of hobbits, orcs, and boat. Participants have a particular problem with the transition from state 6 to state 7. In a study by Jeffries, Polson, Razran, and Atwood (1977), about a third of all participants chose to back up to a previous state 5 rather than moving on to state 7 (Greeno, 1974). One reason for this difficulty is that the action involves moving two creatures back to the wrong side of the river. This appears to be a move away from the desired solution. At this point, participants will go back to state 5, even though this undoes their last move. They would rather undo a move than take a step that moves them to a state that appears further from the goal.
Atwood and Polson (1976) provide another experimental demonstration of participants’ reliance on similarity and how that reliance can sometimes be harmful and sometimes beneficial. Participants were given the following water jug problem:
You have three jugs, which we will call A, B, and C. Jug A can hold exactly 8 cups of water, B can hold exactly 5 cups, and C can hold ex- actly 3 cups. Jug A is filled to capacity with 8 cups of water. B and C are empty. We want you to find a way of dividing the contents of A equally between A and B so that both have exactly 4 cups. You are allowed to pour water from jug to jug.
Figure 8.8 shows two paths for solving this problem. At the top of the illustra- tion, all the water is in jug A—represented by A(8); there is no water in jugs B or C—represented by B(0) C(0). The two possible actions are either to pour A into C, in which case we get A(5) B(0) C(3), or to pour A into B, in which case we get A(3) B(5) C(0). From these two states, more moves can be made. Nu- merous other sequences of moves are possible besides the two paths illustrated, but these are the two shortest sequences to the goal.
Atwood and Polson used the representation  to analyze partici- pants’ behavior. For instance, they asked which move participants would prefer to make at the start state 1. That is, would they prefer to pour jug A into C and get state 2, or jug A into B and get state 9? The answer is that participants preferred the latter move. More than twice as many participants moved to state 9 as moved
to state 2. Note that state 9 is quite similar to the goal. The goal is to have 4 cups in both A and B, and state 9 has 3 cups in A and 5 cups in B. In con- trast, state 2 has no cups of water in B. Through- out the experiment, Atwood and Polson found a strong tendency for participants to move to states that were similar to the goal state. Usually, similar- ity is a good heuristic, but there are critical cases where similarity is misleading. For instance, the transitions from state 5 to state 6 and from state 11 to state 12 both lead to significant decreases in similarity to the goal. However, both transitions are critical to their solution paths. Atwood and Polson found that more than 50% of the time, participants deviated from the correct sequence of moves at these critical points. They instead chose some move that seemed closer to the goal but actually took them away from the solution.1
It is worth noting that people do not get stuck in suboptimal states only while solving puzzles. Hill climbing can also produce suboptimal re- sults when making serious life choices. A classic example is someone trapped in a suboptimal job because he or she is unwilling to get the education needed for a better job. The person is unwilling to endure the temporary deviation from the goal (of earning as much as possible) to get the skills to earn a higher salary.