我喜欢这个问题中提到的算法：“如何运作？奇怪的汉诺塔解法” （英文链接）
有没有办法将那个非递归的汉诺塔解法扩展到使用X个盘子和Y个塔，其中塔用栈表示？
使用X个盘子和Y个塔，将一个迭代、位运算算法扩展到解决汉诺塔问题的规模
8
- Robb
6
怀疑这个。你如何使用X个盘子和Y个塔解决汉诺塔问题？据我所知，没有被证明的算法可以用最少的步骤解决这个问题。除非你不在意步数是否最小？ - IVlad
6如果您不关心步数是否最少，请忽略除三根柱子以外的所有其他柱子。工作完成 :) - Steve Jessop
@Steve Jessop - 确实 :). @Robb - 你最好的起点可能是Frame-Stewart算法，它在这里描述：http://en.wikipedia.org/wiki/Tower_of_Hanoi - 目前还不知道该算法是否真正最优，但很可能是。我不知道如何将其改编为非递归解决方案并打印每个移动步骤，但其他人可能会想出来并希望发布他们的发现 :)。 - IVlad
解决X个圆盘还是比较容易的，你只需要知道它是奇数还是偶数。但有Y个塔就比较棘手了。 - Andres
“最优”解决方案在> 3个磁盘的情况下尚不为人所知[尽管框架斯图尔特猜想提供了一些解决方法]，而位解决方案则利用了3种情况下的假设。 - Foo Bah
@Foo 我相信对于大于3个针柱的情况，最优解尚未被发现，这里指的是针柱数量而非盘片数量。 - TaslemGuy
1个回答
1
在维基百科上可以找到一个关于Y=3塔和X个盘子的汉诺塔问题的迭代解决方案：
对于偶数个盘子：
- 在A和B之间进行合法移动
- 在A和C之间进行合法移动
- 在B和C之间进行合法移动，直到完成
对于奇数个盘子：
- 在A和C之间进行合法移动
- 在A和B之间进行合法移动
- 在B和C之间进行合法移动，直到完成
在每种情况下，总共进行2^X-1次移动。 使用此算法的移动次数仅为Y=3时最少的次数。
此解决方案忽略了其他塔，因此适用于任何Y>= 3和任何X。
尽管三柱版本有一个简单的递归解决方案，如上所述，但四柱（称为Reve's puzzle）甚至更多柱的汉诺塔问题的最优解仍然是一个未解决的问题。这是一个很好的例子，说明如何通过稍微放松问题约束条件，可以使一个简单可解的问题变得极其困难。引自维基百科。
- Martin Thoma
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接