河内的解决方案比O(2 ^ n)更好？

Question

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

此外,下面的解决方案是递归.我们可以使用动态编程和memoization的概念在较短的时间内解决这个问题吗？

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);
}

MyStack是StackJava中的类的扩展版本,它添加了一个name字段和访问器.

此外,同一问题有任何变化吗？

Answer 1

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

Answer 2

我不会证明(正如斯蒂芬所做的那样),但我会尝试直观地解释2 ^ n-1是min:在每个状态中,磁盘只有三种可能的移动.让当前状态表示为有序的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,... ..三合一)).步数实际上是图中的路径.

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

如果使用策略:移动除最大磁盘以外的所有磁盘放置3,然后将大移动到位置2,最后将所有窗体3移动到2,可以按以下方式设计公式:

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

该循环方程的解决方案为您提供该策略所需的步骤数(恰好是最小步数)

Answer 3

河内塔楼的解决方案是不可避免的2 ⁿ.但是,在动态编程解决方案中,每个子问题只计算一次,然后通过组合第一个子问题解决方案,当前磁盘移动和第二个子问题解决方案来解决问题.

因此,在生成每个解决方案时有两个组件:为当前解决方案分配内存,然后填充该内存.内存分配几乎与分配的内存大小无关,是昂贵的组件.内存复制在复制的内存大小上是线性的,虽然速度很快,但在n中是指数,作为塔的解决方案.

时间= c ₁*n + c ₂*2 ⁿ,其中c ₁ >> c ₂.即,它开始线性并以指数结束.

链接到ACM SIGCSE Inroads杂志上发表的文章(2012年9月)