To get a sense of how bad this time complexity is, suppose it takes us one second to move one disk from a rod to another rod. This is and grows very fast as increases. We have seen that the minimum number of moves required for a Towers of Hanoi instance with disks is. There are other ways we can solve this recurrence such as using the Master Theorem or by unrolling the recurrence. Then by using the inductive hypothesis we know that, so our guess was correct!. Now assume that our hypothesis holds for all smaller values of. So our hypothesis holds for the base case. Let’s use a guess and check method to verify whether this guess is correct: Let’s first see if we can find a pattern in the values for. In other words, we would like to solve this recurrence relation. Now we know that is the minimum but we still would like to get an expression for that does not have any recursion in it. Therefore, our total moves of must be the minimum. Then we still need to move the remaining disks to the destination rod but with the minimum possible number of moves. By our induction hypothesis we know we can achieve this in a minimum of moves. We know that we’ll have to at least move the top disks out of the way with the minimum number of moves possible and then move the largest disk to the destination rod. Then for the inductive case, we can first assume that is minimum for. This is the minimum number of moves because we cannot do better than one move for a single disk. How do we know that is the minimum number of moves? We can prove this formally by mathematical induction: For the base case of = 1, we have seen that equals one. Now if, is equal to because we can first recursively move the top disks to the auxiliary rod, move the largest disk to the destination rod, and then recursively move the stack from the auxiliary rod to the destination rod. Our goal in the complexity analysis of this problem is to obtain an expression for in terms of, without any recursion in the expression.įirst, we notice that equals one since if there is one disk we can simply move it to the destination rod in one move. Let denote the minimum number of disk moves needed to solve a Towers of Hanoi instance with disks. Therefore, the time taken by an algorithm for Towers of Hanoi will be proportional to the number of times we move some disk. In our case, an elementary move is to move a disk from one rod to another rod. We know that the time taken by an algorithm will be proportional to the number of elementary moves made. If i % 3 = 0, make the legal move between rods and. If i % 3 = 2, make the legal move between rods and. If i % 3 = 1, make the legal move between rods and. In each iteration of this loop, we do something depending on what remainder we get when we divide by three. If is even then set the destination rod to the auxiliary rod and the auxiliary rod to the original destination rod. ![]() Compute the minimum number of moves needed to solve the puzzle, which is equal to (we will see later how we arrived at this number).Once again we have four inputs which are the same as in the recursive approach: This approach is not as intuitive as the recursive method but it works nevertheless. The idea behind this method is to choose which pair of rods to make a legal move between, depending on what iteration of the algorithm we are on. Now let’s move the smallest disk to rod B as well:Īnother way to solve this problem is to think about it iteratively. So, it’s clear that we should move the second smallest disk. ![]() Moving the smallest disk will not accomplish much since moving it to rod A gets us back to the original state, and moving it to rod B is redundant since we could have just moved the smallest disk to rod B in the first place. Now we have two disks that we can move, namely the smallest and the second smallest. So let’s move the smallest disk to rod C: Our first move can only involve the smallest disk since there is only one stack and this disk is at the top of it. Let’s say the goal is to move all three disks to rod C (which rod we choose as our destination doesn’t matter). We start with all three disks stacked on one of the three rods (rod A in this case): Let’s see an example of the puzzle in action when there are a total of three disks.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |