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 个以上的钉子，证明最佳解决方案是一个开放的问题。有一种已知的非常好的算法，被广泛认为是最优的，适用于简单的情况，即一堆磁盘位于一个钉子上，而您想将整个堆转移到另一个钉子上。但是，对于任意起始位置，我们没有算法，甚至没有已知的启发式算法。

如果我们确实提出了算法，那么开放问题可能会容易得多。