|
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.
|
