Are the towers of Hanoi better than O (2 ^ n)?

Question

Is there a solution for Towers of Hanoi whose operating time is less than O (2 ⁿ ), where n is the number of disks to move? My decision is O (2 ⁿ ) time.

Also, the solution below is with recursion. Can we use dynamic programming with the concept of memoization to solve this problem in less time?

public void towersOfHanoi( int num, MyStack<Integer> from, MyStack<Integer> to, MyStack<Integer> spare ) { if (num == 1) { int i = from.pop(); to.push(i); System.out.println("Move "+i+" from "+from.getName()+" to " + to.getName()); return; } towersOfHanoi(num - 1, from, spare, to); towersOfHanoi(1, from, to, spare); towersOfHanoi(num - 1, spare, to, from); } 

MyStack is an extended version of the Stack class in Java that adds a name field and an accessor.

Also, are there any options for the same problem?

Answer 1

Given that the Towers of Hanoi solution always takes 2 ^ n - 1 step ... no, you won’t find a faster algorithm because it takes O (2 ^ n) just to print the steps, calculate them a lot less.

Answer 2

I will not prove (as Stephen did), but I will try to explain intuitively that 2 ^ n-1 - min: In each state there are only three possible movements for the disks. Let it represent the current state in the form of ordered seq (1, 1, .., 1), so that the first number indicates where the larger disk is, and the last number indicates where the smallest disk is. (1, 1, ..., 1) means that all disks are included in position 1. Also from (1, 1, .. 1) there are only two downstream states: (1, 1, ... 2) and ( 1, 1, ... 3). From (1, 1, ... 2) there are three descending states:

• Return to (1, 1, .. 1)
• goto (1, 1, ..., 3)
• goto (1, 1, ... 3, 2)

If you continue, you will get a graph for which nodes are possible states and edges (transitions) are “disk movements”.

You will get the image as shown below (if you continue, it will look like a triangle, and at the vertices will be (1, 1, ... 1), (2, 2, .. 2), (3, 3, .. . 3)). The number of steps is actually the path in the graph.

If you walk along the edge of a triangle, the number of steps is 2 ^ n-1. All other paths are the same length or longer.

If you use a strategy: move all the disks except the largest one to accommodate 3, then move the large places to place 2 and finally move all the shapes from 3 to 2, the formula can be developed as follows:

f (n) =
f (n -1) // move all but the largest from 1 to 3
+ 1 // move for the most part from 1 to 2
+ f (n -1) // move everything from 3 to 2
->
f (n) = 1+ 2 * f (n-1)

solving this recurrence equation gives you the number of steps required by this strategy (which is the minimum number of steps)

Answer 3

The Hanoi Tower decision is inevitable 2 ⁿ . However, in a dynamic programming solution, each subtask is calculated only once, and then the problem is solved by combining the first solution of the subtask, the current movement of the disk, and the second solution of the subtask.

Thus, in the generation of each solution there are two components: the allocation of memory for this solution and the filling of this memory. The memory allocation is approximately independent of the size of the allocated memory and is an expensive component. A copy of memory is linear in size of the copied memory, which, although fast, is exponential in n as a solution for Towers.

Time = c ₁ * n + c ₂ * 2 ⁿ where c ₁ > c <sub> 2sub>. Ie, it starts linear and ends exponentially.

Link to an article in ACM SIGCSE Inroads Magazine (September 2012)

Answer 4

The standard towers of the Hanoi problem deal with three pins.

However, if we have k-pegs, the time complexity will be O (2 ^ (n / (k-2))).

I solved this problem with 4 bindings and 5 pegs, and temporary difficulties were O (2 ^ (n / 2)) and O (2 ^ (n / 3)) respectively