Solution Strategies, Transfer,
and Computational Resources III:
Goal Recursion Strategy
Basic Goal
Recursion Strategy
|
The
basic recursion strategy for solving the Tower of Hanoi problem
involves transferring the pyramid of disks covering the disk
that is to be moved to the other peg, and then transferring that
disk to the goal peg, and so on until the problem is solved.The
figure below depicts the AND tree that results when this
strategy is applied to the three disk problem. The top node depicts
the problem of transferring all of the disks from the peg on
the far left to the peg on the far right.
This
is decomposed into three subproblems shown at the next level
of the AND tree. The first and third subproblems are not terminal
subproblems and must each be further decomposed into subproblems.
The seven state pairs outlined in yellow represent terminal subproblems
and correspond to the seven transitions of the optimal solution
to this problem.
|
| |
 |
|
|
This
solution can be implemented using a stack. The memory resource
required for the three disk problem can easily be visualized
using this AND tree. Initially only the top-level problem node
is on the stack. The decomposition yields a stack with the problem
node on the bottom and the three nodes of the decomposition ordered
above it with the left-most node now at the top of the stack.
Thus, the stack holds 4 subproblems at this point. The top element
of the stack is further decomposed and one can think of the terminal
nodes being ordered above the previous 4. However, these can
each be executed and thus popped from the stack. Thus, the stack
size is decreased to only two elements. At this point the final
nonterminal subproblem is encountered. Its decomposition yields
the final 3 terminal subproblems, and following their execution,
this final subproblem is popped from the stack, and the initial
problem is popped from the stack since the problem is solved.
With
only three disks the memory requirements are not large. You will
probably find it fairly easy to simulate this recursive strategy
for the three disks "in your head." But now try and
to mentally simulate this recursive strategy for the five disk
problem. Clearly the size of the stack increases with the number
of disks involved in the problem. One way of thinking of it is
to recognize for an N-disk problem, the stack can grow
to a depth of n before a terminal subproblem is reached.
Recall that a terminal subproblem is one where the move can be
made and therefore the subproblem popped from the stack.
|
|
A Perceptual Goal
Recursion Strategy
| The
figure below presents one version of a goal recursion strategy
that uses a coupled "perceptual" system to limit the
memory required to solve Tower of Hanoi problems. Notice that
rules P3, P4, and P5 delete the contents of STM. Examination
of the tests on the left hand sides of the rules shown below
indicate that only the current GOAL and a STATE variable need
to be retained for this strategy. |
|
As in
the case of the Move Pattern strategy, this is achieved
by invoking a perceptual production system which is capable of
testing perceptual predicates relevant to current state of the
Tower of Hanoi problem. Note that this production system can
inform the controlling system if the problem is:
- Solved
- a subgoal is Done
- a subgoal Can be Done
- a subgoal Can't be Done
Clicking on the image below will bring up a window with the
definition of the perceptual predicates.
|
Adapted from Simon,
Herbert A. "The functional equivalence of problem solving
skills." Cognitive Psychology, 1975, 7, 268-288. |
|
This
production system would begin with rule P6 which would establish
the top-level goal and bind the number of disks involved to n
and bind the value of the peg to which they are to be moved to
GOAL-PEG. Note that this formulation introduces the concept of
a pyramid. In this context, a pyramid is a stack of 1 or more
disks that satisfies the constraints of the Tower of Hanoi problem;
i.e, no larger disk is above a smaller disk. Here again we have
a concept crafted to this domain and method of solution.
Rule
P5 would be satisfied on the next cycle. This is the rule that
invokes the perceptual system to determine the status of the
goal. Note that the perceptual tests are not defined on a "pyramid"
... the predicate tested is whether a particular disk, k, can
be moved from its current location P(k) to Peg A. Consequently
the perceptual test will always return CAN'T unless the "pyramid"
consists of a single disk.
Next
Rule P4 would be invoked and this rule deletes the current goal
and replaces it with a goal which involves a pyramid which has
one less disk and whose destination is the other peg. Eventually
a pyramid k with disk k is generated where
this disk is free, That is, T3 will return CAN. P3 will then
be invoked on the next cycle and the goal will be deleted and
the disk moved.
|
 |
Note that P3 deletes
the current goal and does not establish a new one. P6 is required
to reset the overall goal. Clicking on the figure to the left
opens a pop up window that provides a trace of this production
system for the three disk problem. |
|
Note
again the way in which the coupled conceptual perceptual system
reduces the memory requirement. And, of course this solution
method transfers to a Tower of Hanoi problem involving any number
of disks and any pairing of source and destination disks. Simon
develops another system based on a more sophisticated perceptual
strategy that has even broader transfer to additional variants
of the Tower of Hanoi problem. The interested reader is referred
to the article.
If
you still retain some appetite for the Tower of Hanoi world we
refer you to the next page where we will briefly introduce the
N Disk and K peg "Tower of Hanoi" problem where K is
greater than or equal to 3.
|
|
|
|
