algorithm - 具有可变数量杆的汉诺塔的通用解决方案？

Question

给定 D 圆盘、P 极和圆盘的初始起始位置，以及极所需的最终目的地，我们如何编写该问题的通用解决方案？

例如，

给定 D=6 和 P=4，初始位置如下所示:

5     1
6 2 4 3

其中数字代表圆盘的半径，极点从左到右编号为 1-4，我们要将所有圆盘堆叠在极点 1 上。

我们如何选择下一步？

解决方案是(手工计算):

3 1
4 3
4 1
2 1
3 1

(格式:<from-pole> <to-pole>)

第一步很明显，将“4”移动到“5”之上，因为这是最终解决方案中所需的位置。

接下来，我们可能想要移动下一个最大的数字，即“3”。但首先我们必须把它挖出来，这意味着我们接下来应该移动“1”。但是我们如何决定将它放在哪里呢？

就我所知。我可以编写一个递归算法来尝试所有可能的位置，但我不确定这是否是最优的。

Answer 1

我们不能。

更准确地说，如http://en.wikipedia.org/wiki/Tower_of_Hanoi#Four_pegs_and_beyond说，对于 4+ pegs，证明什么是最佳解决方案是一个悬而未决的问题。有一个众所周知的非常好的算法，它被广泛认为是最优的，适用于一堆磁盘在一个钉子上并且您想将整堆磁盘转移到另一个钉子上的简单情况。但是，对于任意起始位置，我们没有算法，甚至没有已知的启发式算法。

如果我们确实有一个建议的算法，那么开放式问题大概会容易得多。