Complexity for towers of Hanoi?

问题:

I was recently solving Towers of Hanoi problem. I used a "Divide and Conquer" Strategy to solve this problem. I divided the main problem into three smaller sub problems and thus following recurrence was generated.

T(n)=2T(n-1)+1

Solving this leads to

O(2^n) [exponential time]

Then i tried to use memoization technique to solve it, but here too the space complexity was exponential and heap space exhausted very soon and problem was still unsolvable for larger n.

Is there a way to solve the problem in less than exponential time? What is the best time in which the problem can be solved?

回答1:

It depends what you mean by "solved". The Tower of Hanoi problem with 3 pegs and n disks takes 2**n - 1 moves to solve, so if you want to enumerate the moves, you obviously can't do better than O(2**n) since enumerating k things is O(k).

On the other hand, if you just want to know the number of moves required (without enumerating them), calculating 2**n - 1 is a much faster operation.

Also worth noting, the enumeration of the moves can be done iteratively with O(n) space complexity as follows (disk1 is the smallest disk):

while true:
    if n is even:
        move disk1 one peg left (first peg wraps around to last peg)
    else:
        move disk1 one peg right (last peg wraps around to first peg)

    if done:
        break
    else:
        make the only legal move not involving disk1

回答2:

You can solve the recurrence and obtain a closed form.

T(n) = 2*T(n-1) + 1

T(n) = 2 * ( 2 * T(n-2) + 1) + 1

T(n) = (2 ^ 2) * T(n-2) + 2^1 + 2^0

T(n) = (2^k) * T(n-k) + 2^(k-1) + 2^(k-2) + ... + 2^0

Solving this the closed from comes out to be

T(n) = (2^n) - 1 with T(0) = 0

Now use exponentiation by squaring.

回答3:

Unfortunantly it's impossible to resolve this problem in less time, because number of moves needed to change position of all hanoi tower is exponential. So the best solution is lineal according to the number of steps O(T), so in number of tails solution is exponential O(2^n)

回答4:

There are exactly 2^n-1 moves, so for listing them all we cannot do better than O(2^n) time complexity.

Enumeration of the necessary moves is possible in O(1) (well, O(log n) if you take arbitrary size integers) space:

(define (fbs n i) (if (even? n) (fbs (/ n 2) (+ i 1)) i))

(define (fb n) (fbs n 1))

(define (hanois n i m) 
  (
    cond 
    ((= i m) "DONE")
    (else 
          (define k (fb i))
          (print "move disk " k " " (if (even? (+ n k)) "left" "right"))
          (hanois n (+ 1 i) m))))

(define (hanoi n) (hanois n 1 (expt 2 n)))

[Scheme]

Note that this algorithm has an overhead of log n due to arithmetic (and the algorithm fb finding the position of the least significant set bit). Any naive solution involving any kind of increment/decrement on a counter will have the same overhead.

回答5:

It depends a bit on what kind of representation you accept. Imagine the following representation:

OneMove
    from : integral
    to   : integral

Solution
    step_one   : optional reference to Solution
    step_two   : OneMove
    step_three : optional reference to Solution

Such a representation can actually be created in linear complexity, since there is a lot of repetition involved.

I just tried it, constructing such a solution for height 64 took less than a millisecond. Of course, stepping through it still takes 2ⁿ-1 steps.

You did not specify language, but if you want code in C++, drop a line.