algorithm - 用任意放置的磁盘解决河内塔？

Question

我正在尝试使用递归解决河内塔问题。我知道如果一开始所有的环都在一个塔上，那么有一个很好的算法可以基于查看序列中每个步骤的二进制表示来解决问题。

但是让我们假设我们想解决河内塔问题，一开始环是杂乱无章的。令 R _i表示半径为 i 的环。假设最初 R ₅和 R ₂在极点 A 上，R ₄在极点 B 上，R ₃和 R ₁在极点 C 上，如下所示：

 **           *
***** ****   ***
  A     B     C

如果目标是将所有圆环移到 B 极，第一步是什么？而且，更一般地说，您将如何解决河内塔的这种变体？

标签： algorithmrecursiontowers-of-hanoi

Answer 1

有趣的问题！我们可以使用类似于解决常规河内塔谜题的递归洞察力来解决这个问题。

让我们按大小对磁盘 1、2、3、4、...、n 进行编号。现在，假设我们要以主轴 B 上的每个磁盘结束。看看磁盘 n 的位置。如果磁盘 n 在主轴 B 上，那么我们永远不需要移动它 - 它永远不会对其他磁盘的移动产生任何影响，因为它的位置永远不会阻止任何移动。那时，我们只需（递归地）将其他 n-1 个磁盘移动到主轴 B 上，基本上可以忽略磁盘 n。

另一方面，如果磁盘 n 在不同的主轴上——比如主轴 A 或主轴 C——那么我们需要将它移动到主轴 B。但唯一可能发生的方法是如果所有其他磁盘都没有打开磁盘 n 的顶部（然后磁盘 n 无法移动）或主轴 B 的顶部（然后磁盘 n 无法移动到那里）。这意味着我们得到以下基本设置：

move all disks of size n or less to spindle X:
    # Base case: If we need to move zero disks, there's nothing to do.
    if n == 0: return

    # Recursive case 1: If disk n is already on spindle X, we don't need to
    # do anything fancy! Just move the other disks.
    if disk n is on spindle X:
        recursively move all disks of size n-1 to spindle X
        return

    # Recursive case 2: If disk n isn't on spindle X, it's on some other
    # spindle Y. That means all other disks need to get to the third 
    # spindle Z before we can move disk n.
    recursively move all disks of size n-1 to spindle Z, as defined above.
    move disk n to spindle X.

    # Now, move all the remaining disks back on top of disk n.
    recursively move all disks of size n-1 to spindle X.

这个解决方案的好处是每一步基本上都是强制的——没有决定做什么，也没有捷径可走。因此，可以保证找到移动磁盘的最快方式。

此外，该解决方案很好地概括了河内塔的标准递归算法。请注意，如果所有磁盘都以标准配置启动，则递归案例 1 永远不会触发，我们将使用与以前完全相同的算法。