algorithm - 汉诺塔有两个辅助杆

Question

我在其中一个网站上遇到了这个问题。

要求:

如果给定两个辅助杆而不是一个，需要提出算法并计算汉诺塔问题的时间复杂度。

我的尝试:

原始汉诺塔:

T(N)= T(N-1) // Moving N-1 disks from Source to Auxilary 
    + 1      // Moving Nth disk from Source to Destination  
    + T(N-1) // Moving N-1 disks from Auxilary to Destination

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

            = O(2 power N )   // exponential.

在当前的问题中，因为我们有两个辅助杆

`

     T(N) =

          T(N/2)  // Moving top N/2 from Source to Aux1

          + T(N/2)  // Moving the remaining N/2 from Source to Destination using Aux2.

           + T(N/2)  // Moving N/2 from Aux1 to Destination.

                T(N) = 3*T(N/2) 
                =O( 3 power log N base 2 ) 
                = O( N power log 3 base 2 )  // less than quadartic.

但我对此不是很确定，因为我不是将顶部 N/2 移动到 Aux1 以及使用 Aux2 将底部 N/2 从源移动到目标的时间计算为 T(N/2)。

为什么我认为这是不正确的，因为在第一种情况下，我们可以在移动顶部 (N/2) 时使用三根杆:Destiation、Aux1 和 Aux2 但是在移动底部 (N/2) 时我们只能玩两根杆 Destination,Aux2

所以我认为应该有更好的方法来解决这个问题。

Answer 1

这是 Python 中的一个简单内存递归函数，它使用 Frame–Stewart algorithm找到最少的移动次数。根据上面链接的维基百科文章，该算法被证明对 4 个钉子和最多 30 个磁盘是最佳的，并且它被认为对 n 的所有组合都是最佳的。磁盘和 r Hook (但未证明如此)。可能我的实现可以稍微优化一下，但它的速度足够合理 n和 r值(value)观。

def hanoi(n, r, memo={}):    # deliberately using a mutable default argument here
    """Return the number of steps required to move n disks using a total of r pegs."""
    if n == 1:               # base case
        return 1
    if r <= 2:               # impossible cases
        return float("inf")
    if (n,r) not in memo:
        memo[n, r] = min(hanoi(k, r)*2 + hanoi(n-k, r-1)   # recursive calls
                         for k in range(1, n))
    return memo[n, r]