## Problem Reduction Search

Sometimes problems only seem hard to solve. A hard problem may be one that can be reduced to a number of simple problems...and, when each of the simple problems is solved, then the hard problem has been solved. This is the basic intuition behind the method of problem reduction. We will have much more to say about this method of search when we cover problem solving and planning in the second half of the course. At this point, our goal is simply to introduce you to this type of search and illustrate the way in which it differs from state space search.

The typical problem that is used to illustrate problem reduction search is the Tower of Hanoi problem because this problem has a very elegant solution using this method. The story that is typically quoted to describe the Tower of Hanoi problem describes the specific problem faced by the priests of Brahmah. Just in case you didn't decide to read this story, the gist of it is that 64 size ordered disks occupy one of 3 pegs and must be transferred to one of the other pegs. But, only one disk can be moved at a time; and a larger disk may never be placed on a smaller disk.

Rather than deal with the 64 disk problem faced by the priests, we will consider only three disks...the minimum required to make the problem mildly interesting and useful for our purpose here...namely to illustrate problem reduction search. The figure below shows the state space associated with a 3-disk Tower of Hanoi Problem. The problem involves moving from a state where the disks are stacked on one of the pegs and moving them so that they end up stacked on a different peg. In this case, we will consider the state at the top of the figure the starting state. In this case all three disks are on the left-most peg. And we will consider the state at the bottom right to be the goal state. In this state the three disks are now all stacked on the right-most peg.

#### State Space for the 3 Disk Tower of Hanoi Problem

Recall that in state space search the generators correspond to moves in the state space. Thus, the two states below the top state in the triangle of states corresponds to the movement of the smallest disk either to the rightmost peg or to the middle peg. The shortest solution to this problem corresponds to the path down the right side of the state space. This solution is shown in the animation below.

In problem reduction search the problem space consists of an AND/OR graph of (partial) state pairs. These pairs are referred to as (sub)problems. The first element of the pair is the starting state of the (sub)problem and the second element of the pair is the goal state (sub)problem.There are two types of generators: non-terminal rules and terminal rules. Non-terminal rules decompose a problem pair, <s0, g0> into an ANDed set of problem pairs {<si,gi>, <sj,gj>, ...>. The assumption is that the set of subproblems are in some sense simpler problems than the problem itself. The set is referred to as an ANDed set because the assumption is that the solution of all of the subproblems implies that the problem has been solved. Note all of the subproblems must be solved in order to solve the parent problem.

Any subproblem may itself be decomposed into subproblems. But, in order for this method to succeed, all subproblems must eventually terminate in primitive subproblems. A primitive subproblem is one which can not be decomposed (i.e., there is no non-terminal that is applicable to the subproblem ) and its solution is simple or direct. The terminal rules serve as recognizers of primitive subproblems.

The symmetry of the state space shown above may have led you to suspect that the Tower of Hanoi problem can be elegantly solved using the method of problem decomposition. The AND tree that solves the 3 disk problem is shown below.

#### AND Tree Showing the Problem Reduction Solution to the 3 Disk Tower of Hanoi Problem

Let us number the state space solution shown in the state space above 1 through 8 so that we can refer to the states by number. 1 corresponds to the topmost or starting state and 8 to the right corner or goal state. These two states are the first and second element in the problem shown as the root node in the AND tree above. The red arc is used to indicate that the node is an AND node.

The problem is decomposed into three subproblems. The left subproblem consists of states 1 and 4; the middle subproblem consists of states 4 and 5; and the right corresponds to states 5 and 8. Note that the left and the right subproblems correspond to the top and bottom nodes of the upper and lower triangles respectively. The middle subproblem corresponds to the move that links these two triangles of states. Note that this middle subproblem has no further decomposition. It is a primitive problem that corresponds to moving the large disk from the first to the third peg. The yellow border is used to depict primitive or terminal subproblems. The left and right subproblems are not primitive subproblems and they are each decomposed further. The three subproblems for each of these subproblems are primitive and correspond to the first three and the last three moves of the solution.

In this example, only AND nodes are shown. An OR node corresponds to the case where one or more different non-terminal rules are applied to a particular subproblem. For an OR node, at least one of the OR nodes must be solved in order to solve the (sub)problem

Note that syntactically a decomposition is simply a set of (partial) state descriptions. (This definition can be relaxed even further, but that is a rather long story.) Thus, there are very many possible nonterminal reduction rules that could be defined for this 3 Disk Tower of Hanoi Problem. The figure above illustrates another possible non-terminal rule for this problem. In this case, the first subproblem is to move the middle and small sized disks to the right peg. The second subproblem is to move these disks from the right peg to the middle peg. This corresponds to moving down the left side of the triangle in the state space above and then moving across to the right side. Although this involves unnecessary moves, it leads to a valid solution when coupled with the appropriate further rules of decomposition .

The next figure above illustrates a non-terminal rule for this problem which involves partial states. Note that the first subproblem specifies as the goal state a situation where the large disk is on the left peg and no disks are on the large disk. (Of course, our picture can't express this last condition since the other two pegs aren't in our picture at all.) The next subproblem involves a goal situation where the large disk is now on the left peg and again no disks are on the large disk.

Note that there are four states in the state space that satisfy the goal of the first subproblem and also four that satisfy the goal of the second subproblem. This observation forces us to recognize that implicit in the use of non-terminal rules in problem reduction is the assumption that there is a path in the state space that will be discovered when the partial state descriptions are bound to an appropriate state space.

#### Order of Problem Solving and Order of Problem Execution

Another important feature of problem reduction rules is that their use allows the order of problem solving to differ from the order of problem execution. In the state space above these two are obviously the same (although one could also search backward from the goal, but in the case of either forward or backward search the solution involves the same linear order of states.) In the present case, the problem solver could choose any of the subproblems to work on first.

In the Tower of Hanoi problem there is no obvious advantage to solving the problem in an order that differs from the order of problem execution. However, in some problems one may find that some subproblems are easier than others and their solution may serve to simplify the solution of the remaining subproblems. A Cryptarithmetic Problem has been developed which illustrates this point. In this case, the subproblems correspond to the different equations that are formed in the algebraic representation of the problem. Note, that in this case the state space has 10! states and solving it via state space search is out of the question for any sane human mind.