3

给定 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”。但是我们如何决定把它放在哪里呢?

这就是我所得到的。我可以编写一个递归算法来尝试所有可能的地方,但我不确定这是否是最优的。

4

1 回答 1

1

我们不能。

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

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

于 2012-07-03T05:54:55.800 回答