8

是否有运行时间小于 O(2 n ) 的河内塔的解决方案，其中n是要移动的磁盘数量？我的解决方案需要 O(2 n ) 时间。

此外，以下解决方案是递归的。我们可以使用带有记忆概念的动态编程在更短的时间内解决这个问题吗？

public void towersOfHanoi(
        int num, 
        MyStack<Integer> from,
        MyStack<Integer> to, 
        MyStack<Integer> spare
) {
    if (num == 1) {
        int i = from.pop();
        to.push(i);
        System.out.println("Move "+i+" from "+from.getName()+" to " + to.getName());
        return;
    }
    towersOfHanoi(num - 1, from, spare, to);
    towersOfHanoi(1, from, to, spare);
    towersOfHanoi(num - 1, spare, to, from);
}

MyStackStack是Java中类的扩展版本，它添加了name字段和访问器。

另外，同一个问题是否有任何变化？

4

5 回答 5

17

鉴于求解河内塔总是需要 2^n - 1 步......不，你不会找到更快的算法，因为打印出步骤需要 O(2^n)，更不用说计算它们了.

于 2012-05-21T02:19:28.113 回答
10

我不会证明（如斯蒂芬所做的那样），但我会尝试直观地解释 2^n-1 是最小值：在每个状态下，磁盘只有三种可能的移动。让我们将当前状态表示为有序 seq (1, 1, .. , 1)，这样第一个数字表示较大的磁盘在哪里，最后一个数字表示最小的磁盘在哪里。(1, 1, .., 1) 表示所有磁盘都在位置 1 上。同样从 (1, 1, ..1) 开始只有两种下降状态：(1, 1, ... 2) 和 ( 1, 1, .... 3)。从 (1, 1, ... 2) 有三个下降状态：

  1. 返回 (1, 1, .. 1)
  2. 转到 (1, 1, ..., 3)
  3. 转到 (1, 1,...3, 2)

如果继续，您将获得节点是可能状态且边（转换）是“磁盘移动”的图形。

您将获得如下所示的图像（如果继续，它将看起来像三角形，顶点将是 (1, 1, ...1), (2, 2, ..2), (3, 3, . ..3))。步数实际上就是图中的路径。

如果沿着三角形的边走，2^n-1的步数。所有其他路径的长度相同或更长。

在此处输入图像描述

如果使用策略：将除最大的磁盘之外的所有磁盘移动到位置 3，然后将大的磁盘移动到位置 2，最后将所有表格 3 移动到 2，公式可以设计如下：

f(n) =
f(n -1) // 将除了最大的从 1 移到 3
+ 1 // 将最大的从 1 移到 2
+ f(n -1) // 将所有从 3 移到 2
->
f( n) = 1+ 2 * f(n-1)

该循环方程的解为您提供该策略所需的步数（恰好是最小步数）

于 2012-05-21T04:54:11.067 回答
10

河内塔的解决方案不可避免地是 2 n。然而，在动态规划解决方案中，每个子问题只计算一次，然后通过组合第一个子问题解决方案、当前磁盘移动和第二个子问题解决方案来解决问题。

因此，生成每个解决方案有两个组件：为当前解决方案分配内存，然后填充该内存。内存分配大约与分配的内存大小无关，并且是昂贵的组件。内存复制与复制的内存大小呈线性关系，虽然速度很快，但作为 Towers 的解决方案，它在 n 中呈指数增长。

时间 = c 1 *n + c 2 *2 n，其中 c 1 >> c 2。即，它以线性开始并以指数方式结束。

链接到出现在 ACM 的 SIGCSE Inroads杂志（2012 年 9 月）中的文章

于 2012-10-12T18:37:29.030 回答
2

标准的河内塔问题涉及 3 个钉子。

但是，如果我们有 k-pegs，时间复杂度将是 O(2^(n/(k-2)))。

我已经用 4 个钉子和 5 个钉子解决了这个问题，结果的时间复杂度分别为 O(2^(n/2)) 和 O(2^(n/3))

于 2015-02-25T21:46:52.137 回答
-1

这个比递归的快大约 7%。它将移动存储在列表中，以便您可以在之后使用它，如果您愿意，可以打印并移除容器。

```
unsigned long i;  
static const int MAXNUMBEROFDISKS = 32;
vector<int> pow2Vec;
uint_fast32_t mPinFrom    = 0;
uint_fast32_t mNumDisk    = 0;
unsigned long numDiskLong = 0;
uint_fast32_t mOffset[MAXNUMBEROFDISKS];
uint_fast32_t mDir[MAXNUMBEROFDISKS]          = { 0 };
uint_fast32_t mPositionDisk[MAXNUMBEROFDISKS] = { 0 };
const uint_fast32_t mRedirectArr[5] = { 2, 0, 1, 2, 0 };




Algos::Algos()
{ 
  for (int i = 0; i < MAXNUMBEROFDISKS; ++i)
  {
    pow2Vec.push_back(pow(2, i));
    mOffset[i] = 1;
  }

  for (int i = 1; i < MAXNUMBEROFDISKS; i += 2)
  {
    mDir[i] = 2;
  }

  mOffset[0] = 0;
}




void Algos::calculListBinExperiment(vector<tuple<int, int, int>>& listeFinale, int nbDisk)
{
  listeFinale.resize(pow2Vec[nbDisk] - 1);
  _BitScanForward(&i, nbDisk);
  for (int noCoup = 1; noCoup < pow2Vec[nbDisk] ; ++noCoup)
  {
    _BitScanForward(&numDiskLong, noCoup);
    mNumDisk = numDiskLong;
    mPinFrom = mPositionDisk[mNumDisk];
    mPositionDisk[mNumDisk] = mRedirectArr[mPositionDisk[mNumDisk] + mDir[mNumDisk + 
    mOffset[i]]];
    listeFinale[noCoup - 1] = make_tuple(mNumDisk, mPinFrom, mPositionDisk[mNumDisk]);
  }
}
```
于 2020-11-17T21:53:42.933 回答