给定 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”。但是我们如何决定把它放在哪里呢?
这就是我所得到的。我可以编写一个递归算法来尝试所有可能的地方,但我不确定这是否是最优的。