|
In
considering this it will be useful to recall that in the standard
problem we thought of a peg as fulfilling one of three functions.
At any point in the solution, a peg might be the source peg,
the target peg, or the other peg. The source
peg refers to the peg that holds the disk that is to be moved
to the target peg. The other peg refers to the
remaining peg that may be safely used to store the disks that
may cover the disk that is to moved.
With
this terminology in mind, let us consider the case where the
number of pegs exceeds the number of disks....the cells below
the diagonal shown in blue. In this case we have not a single
"other peg" but a set of other pegs that may be used
to store the disks that must be moved to clear a particular disk.
In
fact, since the number of pegs is at least one more than the
number of disks, we are guaranteed that we have as many "other
pegs" as we have disks that must be moved to clear a bottom
disk. Consider the first move of the problem where all of the
n disks reside on the same "source disk". In this case
n - 1 disks must be moved to clear the bottom disk. But recall
that there are at least n + 1 pegs. Now one of these pegs is
the source peg, and one the target pet. But there are n - 1 pegs
available for use as other pegs. Consequently, we can place each
of the n - 1 disks onto a unique peg. Thus, the number of moves
required is basically the number of moves required to unstack
the disks from the source peg and then restack the n disks on
the target peg. We save one move because the bottom disk can
be stacked directly; thus, 2n -1 moves. Note that increasing
the pegs from n + 1 to n + k with k > 1 can lead to no further
benefit.
Although
these problems denoted by the blues cells were simply solved,
notice that this class of problems were not solved by
transferring knowledge from the standard 3 Peg and N Disk Problem.
Of course, we could have achieved perfect transfer....simply
ignore the "extra" pegs and solve the problem using
only 1 peg other than the starting and goal pegs. But now the
solution length would be 2 n-1 rather
than 2n - 1. But perhaps
some of our knowledge can usefully transfer to problems that
lie in the area between 3 pegs and n + 1 pegs; the areas that
are shown in green and red in the above matrix.
The
standard Tower of Hanoi problem, where three pegs are available
is depicted in yellow in the matrix above. . And the standard
formula for computing the number of moves to solve the problem
as a function of n is also shown. Let us represent the number
of pegs as |pegs| and the number of disks as |disks|.
Two of the four possible relations between the number of pegs
and the number of disks has been considered; the case with |pegs|
> |disks|, and the standard problem with |pegs| = 3.
There
is one more of the four cases that is easily determined. This
is the case where |pegs| = |disks|. This case corresponds
to the diagonal cells shown in green in the matrix. In this case
the number of moves required to solve the problem as a function
of the number of disks is (2n + 1). This case is similar to the
case where there was at least one more peg than disks. Again,
at any point in the solution one peg serves as the source,
another as the target, and n - 2 are available as other
pegs. But there are n - 1 disks that must be removed. Thus, one
of the other pegs must hold two disks resulting in a stacking
and unstacking move to create this temporary stack of two disks.
Thus, we arrive at (2n + 1) moves as the minimum required moves.
Again in this case there appears to be little knowledge from
the standard Tower of Hanoi problem that was transferred. Rather
from our line of argument you can see that it was primarily knowledge
from the problems where |pegs| > |disks| (the blue
cells) that informed out conclusions.
The
final case where |disks| > |pegs| (with |pegs| >
3) is the most interesting and most challenging to
consider. These cases are shown in red in the matrix above. Recall
that for the three cases already considered, we can provide both
an algorithm for solution to the problem as well as a formula
from which the number of moves required by the algorithm
can be computed. We would like to do the same for this case.
However, there is an additional consideration. Each of the problems
in the matrix share the constraints that: (1) only one disk may
be moved at a time; (2) no larger disk may be placed on a smaller
disk; and (3) a disk may be moved only if it is clear; that is,
no disk is stacked on top of it. Do these constraints result
in a pegs x disks space of problems which share a common
structure or is the structure of these problems quite disparate
from each other?
Transfer
is possible if the hypotheses that these constraints yield a
"single" space of problems is true. Guided by this
hypotheses we will think about the |disks| > |pegs| case
in a way that is consistent with our previous reasoning about
problem solutions. Namely, again partition the pegs in three
sets according to their function. Then, the cardinality of the
set of other pegs is the feature that changes as the number of
pegs increases from 3 to p.
As
we saw in considering the previous cases, the key element to
consider is the cardinality of the set of other pegs, (|pegs|
- 2), in relation to the number of disks, |disks|.
The quantity (|pegs| - 2) may be greater than or equal
to (|disks| - 1), the lower half matrix; or exactly one
less than (|disks| - 1), the diagonal of the matrix. For
either of these cases, we know the solution algorithm. Both are
a minor variations on unstacking and restacking the disks. The
other case for which a solution algorithm is known is when (|pegs|
- 2) = 1; that is, the standard Tower of Hanoi Problem.
The
trick then is to construct a general algorithm from these pieces.
The algorithm is quite simple. The trick is to reduce any of
the possible problems to these known cases. Thus, we must determine
the decisions that are to be made when 1 < (|pegs| -
2) < |disks| since these cases fall outside our known
three cases. Note, that any time that we have more than one other
peg that can be used, it should be used since it can reduce the
number of disks that must be temporarily stacked and unstacked
from a peg. And, since the function for stack and unstacking
from a single peg is exponential, we should reduce the exponent
as much as possible. Thus, at any point if there are d
disks that must be temporarily stacked and p > 1 pegs
available as a temporary storage area for the stack, then we
should create p stacks with each stack containing d/p
disks. In case d is odd then the first stack will contain an
additional disk. This step in our reasoning is quite straightforward.
However,
things are a bit more complicated because this decision rule
must be applied recursively until the recursion bottoms out on
one of our three cases. And, the number of other pegs available
varies as the algorithm is recursively applied. An intuitive
feel for this can be obtained by carefully following the animation
of the application of the algorithm to a problem involving 4
pegs and 8 disks. The animation is shown below together with
a description of the major steps of the solution. Watch the algorithm
and see if you can recognize the way in which our knowledge of
the standard Tower of Hanoi problem was transferred to this case.
|
