If you are moving the disk from rod $i$, and the two other rods are valid destinations, then move it to rod $i 1\mod 3$.With these rules, the non-recursive algorithm has two simple steps: Moving a disk from rod $i$ to rod $j$ is only valid if $i\neq j$, and either rod $j$ is empty or the top disk in rod $j$ is larger than the top disk in rod $i$.You can only move a disk from the top of one rod to the top of another rod.Never move the same disk twice in succession.(This does not generalize easily to more than $3$ rods for presumably obvious reasons).Ī bit more interesting is trying to prove that the non-recursive solution gives an optimal solution this solution only requires you to remember the last disk you moved at any given time (the recursive solution is more memory intensive, of course). The optimal strategy for $k 1$ described above takes $(2^k-1) 1 (2^k-1) = 2^k 2^k - 1 = 2^-1$ steps thus, the optimal solution for $n$ disks and $3$ rods requires $2^n-1$ moves. Assume that moving $k$ disks requires $2^k-1$ moves in the optimal strategy. So the optimal strategy for $k 1$ disks is to move the top $k$ using the optimal strategy for $k$ from $I$ to $A$, then move the largest disk from $I$ to $T$, then move the top $k$ disks using the optimal strategy for $k$ from $A$ to $T$.īy keeping track of the actual number of moves needed at each step, you can give the number. Then you move the $k 1$st disk, and then you want to move the remaining $k$ disks from the auxiliary rod to the terminal one in as few moves as possible (the optimal way). To move $k 1$ disks, you need to move the largest disk from the initial rod to the terminal rod, but that is the only time it needs to move (it cannot help you with the other disks, since it must lie at the bottom at any given time, so any other moves only require further moves in the end) to move the bottom ($k 1$)st disk from the initial rod $I$ to the terminal rod $T$, you must first move the top $k$ disks out of the way this requires moving the $k$ disks from the initial rod $I$ to the auxiliary rod $A$, and the optimal way of doing this is the optimal strategy you know for $k$ disks. I'm sure there are other ways of proving it, perhaps with Lucas numbers as you suggest.Ĭlearly, the optimal strategy with $n=1$ is to simply move the disk directly.Īssume you already have the optimal strategy for moving $k$ disks. To show the optimal strategy for $n$ disks in $3$ rods is the "usual" one, you can do it by induction (which yields a recursive solution). I will address your first question, but not the one for larger number of rods as far as I know, it's still generally wide open what the optimal strategy might be even for $4$ rods and a smallish number of disks.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |