复杂的河内塔？ [英] 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

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

解决这个导致

O（2 ^ N）指数时间]

O(2^n) [exponential time]

然后我试图用记忆化技术来解决这个问题，但同样的空间复杂度是指数和堆空间耗尽很快和问题仍然无法解决对于更大的n。

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?

推荐答案

这取决于你所说的解决的意思。汉诺塔的问题，3钉和 N 磁盘会占用 2 ** N - 1 移动来解决，因此，如果要列举的动作，你显然不能做得比 0（2 ** N）自枚举 K 事情是 O（K）。

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).

在另一方面，如果你只是想知道所需的移动次数（不枚举它们），计算 2 ** N - 1 是一个更快的操作

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.

另外值得一提的，招式枚举可以反复使用 O（N）空间复杂度做了如下（disk1的 $ C>最小盘）：

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

这篇关于复杂的河内塔？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！