汉诺塔问题是一个古老的“游戏”，在每本计算机程序设计教课书里，几乎都把求解汉诺塔问题作为递归算法的范例。经典的汉诺塔问题可以描述如下：有三根柱子与 n 个大小不一的盘子，初始时，这 n 个盘子从大到小叠放在第一根柱子上，并且小盘子位于大盘子上面。问题是如何把这 n 个盘子从第一个柱子全部移动到第三个柱子上，移动时满足这样的规则：每一次只能移动一个盘子，并且满足小盘子只能在大盘子上面。就这一问题本身而言，无论是最佳的移动方法还是最少的移动步数，都已成功解决。 从经典的汉诺塔问题可以拓展出许多其它的版本。例如，我们最近提出了一个扩展的汉诺塔问题，即在上述移动规则下，并不按照最优的方法移动盘子，而是对其进行随机移动。我们的问题是：从初始状态（所有盘子都在第一个柱子上）出发，按照移动规则，随机地移动盘子，请问：所有盘子恰好首次均在第三个柱子上时，期望移动盘子的次数是多少？这一问题当初由我本人提出来，让来自台湾参加大陆 ACM 总决赛的同学思考，问题的答案最终由我的硕士生伍顺琪在我与陈关荣老师的共同指导下得到了圆满解决。我们将所提出的问题归结为求解对偶 Sierpinski 分形上随机游走的平均首达时间，相关结果已经被《 The European Physical Journal B 》正式录用，以下是论文的中文摘要。 摘要： 本文研究了 d 维对偶 Sierpinski 分形（ Dual Sierpinski gaskets, DSGs ）上的随机游走问题。根据电阻距离与随机游走平均首达时间的关系，首先计算了 d 维 DSGs 上两个特殊点之间的平均首达时间，然后利用 DSGs 拉普拉斯矩阵的谱，计算了 DSGs 中所有节点对之间的平均首达时间。通过递归的方法，得到了上述两个问题的精确解，并给出了它们与网络规模大小的变化关系。最后，给出了 d=2 时所得 DSGs 上随机游走的研究结果与扩展的汉诺塔问题的对应关系。 发表的论文PDF版本: Random walks on dual Sierpinski gaskets.pdf
标签: 汉诺塔问题
