algorithm - 使用 X 圆盘和 Y 塔缩放迭代、按位算法来解决汉诺塔

Question

我喜欢这个问题中提到的算法:“这是如何工作的？河内古怪的塔解决方案” How does this work? Weird Towers of Hanoi Solution

有什么方法可以扩展汉诺塔的非递归解决方案以使用 X 磁盘和 Y 塔，其中塔表示为堆栈？

Answer 1

具有 Y=3 个塔和 X 个圆盘的 Hanoi 塔的迭代解决方案，可以在 Wikipedia 上找到:

对于偶数个磁盘:

• 在钉子 A 和 B 之间做出合法移动
• 在 Hook A 和 C 之间做出合法移动
• 在钉子 B 和 C 之间做出合法移动重复直到完成

对于奇数个磁盘:

• 在 Hook A 和 C 之间做出合法移动
• 在钉子 A 和 B 之间做出合法移动
• 在钉子 B 和 C 之间做出合法移动重复直到完成

在每种情况下，总共进行了 2^X-1 次移动。 该算法的移动次数仅为minimal for Y=3 .

此解决方案忽略了其他塔，因此它适用于任何 Y >= 3 和任何 X。

Although the three-peg version has a simple recursive solution as outlined above, the optimal solution for the Tower of Hanoi problem with four pegs (called Reve's puzzle), let alone more pegs, is still an open problem. This is a good example of how a simple, solvable problem can be made dramatically more difficult by slightly loosening one of the problem constraints.

引自Wikipedia .