| Sometimes problems only seem hard to
solve. A hard problem may be one that can be reduced to 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 (also
referred to as problem decomposition and related to the
method referred to as divide-and-conquer) . This
type of search differs in many ways 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. Here we will compare
the state space formulation with the problem reduction formulation
of this problem.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
to be 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)poblems. 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 problm 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. Not 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
rule 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 Poblem
|
|
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 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 subpropblem
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
|
