13

我最近正在解决河内塔问题。我使用“分而治之”的策略来解决这个问题。我将主要问题分为三个较小的子问题，因此产生了以下递归。

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

解决这个导致

O(2^n) [指数时间]

然后我尝试使用记忆技术来解决它，但是这里的空间复杂度也是指数级的，堆空间很快就耗尽了，对于更大的 n，问题仍然无法解决。

有没有办法在不到指数的时间内解决这个问题？解决问题的最佳时间是什么时候？

4

5 回答 5

15

这取决于您所说的“解决”是什么意思。3个钉子和n圆盘的河内塔问题需要2**n - 1移动来解决，所以如果你想枚举移动，你显然不能做得更好，O(2**n)因为枚举k事物是O(k)。

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

另外值得注意的是，移动的枚举可以迭代地完成，O(n)空间复杂度如下（disk1是最小的磁盘）：

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
于 2012-09-12T07:38:24.783 回答
14

您可以解决递归并获得封闭形式。

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(nk) + 2^(k-1) + 2^(k-2) + ... + 2^0

解决这个封闭的结果是

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

现在使用平方取幂。

于 2012-09-12T07:39:42.710 回答
3

不幸的是，不可能在更短的时间内解决这个问题，因为改变所有河内塔位置所需的移动次数是指数级的。因此，根据步数 O(T)，最佳解是线性的，因此尾数解是指数 O(2^n)

于 2012-09-12T08:40:30.043 回答
0

恰好有 2^n-1 次移动，所以要列出它们，我们不能做得比 O(2^n) 时间复杂度更好。

在 O(1) （好吧，如果您采用任意大小的整数，则为 O(log n)）空间中可以枚举必要的移动：

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

[方案]

请注意，由于算术（以及fb查找最低有效设置位的位置的算法），该算法具有 log n 的开销。任何涉及计数器上任何类型的递增/递减的简单解决方案都将具有相同的开销。

于 2017-10-17T11:57:26.473 回答
0

这在一定程度上取决于您接受哪种表示形式。想象以下表示：

OneMove
    from : integral
    to   : integral

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

这种表示实际上可以以线性复杂度创建，因为其中涉及大量重复。

我刚刚试了一下，为高度 64 构建这样的解决方案花费了不到一毫秒的时间。当然，单步执行仍然需要 2 n -1 步。

您没有指定语言，但如果您想要 C++ 中的代码，请写一行。

于 2017-11-10T10:08:24.150 回答