汉诺塔：闪烁在数学和心理学交汇之地奇妙问题
"当 64 金片移动完成时宇宙会在一瞬间闪电式毁灭."
数学家和心理学家们的研究鲜有交集，即便有，也难想象其中有汉诺塔问题会闪烁其中。然而，汉诺塔问题在这两个领域都很有吸引力。心理学上，它有助评估一个人的认知能力。数学上，它展示了大量优美特征，带你直面惊人棘手的待解难题。
其游戏规则直截了当。有三根桩和一些碟片（最早是八个），碟片按照大小顺序叠在其中一根桩上，最大的碟片放在最底部。你的任务是把整叠碟片移动到另一根桩上，一次只许移动一张，期间不许大碟压小碟。
数学家安德里亚斯·M·欣茨（Andreas M. Hinz）从数学和心理学的角度来看待这款游戏。他即将出版一本关于汉诺塔游戏的书，而且他与心理学家合作开发了一种评估病人的新工具。他解释说，汉诺塔问题对心理学家来说如此有趣缘于其简洁性。“这个游戏很容易解释，你可以看到人们在思考，”他说。“(被试人员)在实验组织者面前做动作，这样你就能看清他尝试的每一步、每一个策略。这就是心理学家如此喜欢它的原因所在。”
这个游戏特别适用于评估人们的任务规划和任务细分能力：要移动整个塔，先得移动塔的顶端，同样的规则也适用于后续子问题。修改问题也容易：可以添加更多碟片，或者规定新的开始和结束条件，比如说不让所有碟片最终堆叠在一个桩上。事实证明，这两种特性：游戏的递归特性及其可变性，也引出了一些非常有趣的数学问题。
游戏规划
The Game Plan
观察游戏结构的最佳方法是绘制网络或图形，显示所有可能的构图和移动。假设用三张碟片和三根桩来玩这个游戏。将碟1、碟2和碟3标上序号，其中碟1最小, 碟3最大。也为桩1,桩2和桩3打上标记。现在假设碟1和碟3在桩1上，碟2在桩3上。使用三元组（1,3,1）对这种情况进行编码。三元组中数值的位置编号对应于碟片编号，数值表示该碟片所在的桩。因为已知必须按大小顺序排列，所以在哪根桩上放置几号碟片就不会搞混。因此任一合法的碟片码放方式都可以明确地以有序三元组来编码。
连接各状态转移节点
现在在纸上把每个三元组画到圈内。如果单步移动碟片能够从一个圈转移到另一个圈，则将二者连起来。例如起始状态（1,1,1）（所有碟片在桩1）连到了（2,1,1）（碟1在桩2，其他碟都在桩1）和（3,1,1）（碟1在桩3，其他碟都在桩1）上。总共有 3³=27种可能存在的状态。它们构成如下状态转换图：
汉诺塔游戏的状态转移图 H3
这张图叫做汉诺塔游戏状态转移图，以H3表示。下标3表明游戏中有3个碟子。
有了状态转换图就很容易描述某人的游戏过程。“心理学家热衷于使用状态转移图，因为可以用它画出被试者的动作序列，”欣茨解释道，“你能从中轻易看出他有没有做出最优操作，或者，如果没有，他在哪里遇到问题，在哪里长时间思考等。因此可以从个人或众人的测试结果中掌握许多信息，假如你把众人的些操作过程图叠加到一起来看的话。”
玩3张碟子的汉诺塔游戏十分简单，那么4碟、5碟、6碟或任意n碟时情况如何呢？从转移图来看答案非常漂亮：4碟子汉诺塔游戏的状态转移图H4中包含3个H3图，每个H3图与其他两个H3图都由单边相连。
4碟子汉诺塔游戏的状态转移图H4中包含3个H3图
类似地，H5图由3个H4图构成，H6图由3个H5图构成，以此类推。这是由游戏的递归特性决定的：如果忽略最大的碟子，n+1碟汉诺塔游戏就变成了n碟汉诺塔游戏。比如说在4碟汉诺塔游戏中，最大的碟4在桩1，对余下3张碟的任何合法操作，也同样是忽略碟4后3碟汉诺塔游戏中的一个合法操作。因此，如果看H4图中碟4在桩1的状态节点（这些状态节点的标签以1结尾），会看到一个H3图。类似地，碟4在桩2时、碟4在桩3时，会分别看到各自对应的H3图。
如何在这些状态转移图上移动？若想移动碟4，必得其他3碟同在另外两桩之一上面才行。每份H3图中都有2个节点对应此种情况（分别表示另外两桩之一上有全部剩余碟子），从任一H3图出发分别有一条边通往其他两个H3图（代表碟4移动）。因此各H3图被两两分组并联通。同理，当n为整数时，Hn+1图中包含3个Hn图。
2012年7月，在克拉科夫（Krakow）的欧洲数学大会（European Congress of Mathematics）上，欣茨在介绍他的书《The Tower of Hanoi — Myths and Maths》（汉诺塔——神话和数学）
如果已经掌握了解决汉诺塔游戏的方法，那么增加碟子数并不会相应加大游戏难度。但若规定：游戏开始和结束时，并非所有碟子都以塔式叠于同一根桩上，那么事情就复杂了。“此时游戏变得相当困难，”欣茨说。“心理学家在测试中使用了这种变体游戏，但他们对其结构理解不深。我们帮助其建立了这种图表式的数学模型，使得可以用数学方法分析游戏结构。”
比如，通过状态转移图可以立即看出，无论怎样规定起止条件，无论用多少碟子，总是可以找到游戏答案。因为很容易从递归结构中推断出每个Hn图都是联通的：任何两个节点之间都有通路。
但是最小移动次数的最优解怎样求呢？一般的起止条件是所有碟子都在一个桩上，因此可以算出最小移动步数是 2n-1。这也是最糟的：任意起止条件下，最小移动步数至少是2^(n-1)。可以用数学归纳法证明：首先证明该公式对于初值 n=1 成立，然后证明如果公式对n成立则必定对 n+1 也成立。（自己证明试试，或看看这个证明）plus.maths.org/content/optimal-solution
三角形连接
Triangle Connections
数学家发现，增加碟子的数量会引发一些有趣的问题。假设游戏中有无数个碟片，那么状态转移图会是怎样的？好吧，看看下面的图片。
谢尔宾斯基三角形Sierpiński's triangle
这便是谢尔宾斯基三角形。通过另一种无限递归过程就能生成它。从一个（填满的）等边三角形开始，去掉其三条边的中点的连线所围的倒三角形（只移走该倒三角形的内部而留下其三条边）。现在剩下了 3 个填满的等边三角形。同样地，再从这 3 个三角形中逐一移除其各自的中心倒三角形，于是便剩下9个三角形。继续进行，总是从剩余的各个三角形中移除其中间倒三角形，不断重复进行。最终你会得到谢尔宾斯基三角形。
谢尔宾斯基三角形是最著名的分形之一。它是自相似的：任何一个三角形不管它有多小，如果放大其内部，你看到的都和整张图完全一样。谢尔宾斯基三角形属于一个介于相邻维度之间的奇怪世界：它比光滑的一维曲线维度更高，但面积是零，所以也就不是二维对象。数学家们推广了维度的概念，以抓住此类复杂事物的本质。从广义的维度概念来看，谢尔宾斯基三角形的维度是log3/log2≈1.585。
当逐渐增加汉诺塔游戏中的碟子时，对应的状态转换图经过适当缩放，看起来就越来越像谢尔宾斯基三角形。当n趋于无穷时，得到的图形和谢尔宾斯基三角形的结构是一样的。
它与数学家喜欢的另一种三角形：帕斯卡三角形，有着同样有趣的联系。（我们不会在这里定义它，如果你还没见过它，这里有个很好的解释[1]）如果取帕斯卡三角形的前2^n行，并连接水平和对角相邻的奇数，那么得到的图和汉诺塔Hn图结构完全一样。
[1] mathforum.org/dr.math/faq/faq.pascal.triangle.html
帕斯卡三角形的前八行中相邻的奇数项相连
这种联系不仅漂亮而且实用。在某个领域内难以证明的结果，在其他领域内或许易于证明，于是就可以进行问题转化。例如，假设你在谢尔宾斯基三角形中旅行，但是从未走出分形之外。那么两点之间的平均距离是多少？没有人能够回答这个问题，直到欣茨用汉诺塔状态转移图来计算它：结果是466/885（假设谢尔宾斯基三角形最外层的边长是1）。
加桩
Adding Pegs
增加碟片的情况讨论够多了，增加一根桩会怎样呢？游戏本身变得更容易了，因为有了更多空间来移动碟子。但这些图表也失去了它们的整洁结构。现在有更多的碟子组合以让你移动最大碟片——小的碟片不再需要被堆在一根桩上了。
这意味着，最大碟片在桩1的状态图，和最大碟片在桩2的状态图之间的连接边不止1条，因此使得整体状态图更复杂。“4根桩的状态转移图通常不再是平面结构，”欣茨说。“这意味着，你不可能把它们画在一张纸上而不让边交叉。这得要3个维度才行。我们还不能很好地理解这些图表，因为它们紧密地交织在一起。”
欣茨和书的共同作者在一起。从左到右：Ciril Petr, Andreas M. Hinz, Sandi Klavžar和Uros Milutinović
这种复杂性意味着看似简单的问题可能难以解决。例如，没人知道在正常起止条件下，最短解决方案有多长。有一些策略策略可以解决多桩难题，著名的弗瑞姆-斯图尔特猜想（Frame-Stewart conjecture ）声称这些策略是最优的。但是，尽管这个猜想已经有70多年的历史了，但这个问题还没有解决。在计算机的帮助下，它的正确性已经被证明在30个碟子之内是正确的。
欣茨是一位数学物理学家，但他迷恋汉诺塔游戏纯属消遣。他说：“与图论专家---他们是我在这本书的合著者---和心理学家之间的合作非常吸引人。”他与心理学家一起制作的评估工具现在正在被使用，例如测试患有痴呆症或中风的人，看看大脑的哪些区域受到了损伤。
它不仅仅有用。“数学家伊恩•斯图尔特（Ian Stewart）曾经说过，人们对数学很感兴趣，因为它很有趣，很漂亮，而且很有用。”欣茨说。“但我想补充第4点：人们喜欢数学，因为它令人惊奇。”作为一个数学对象，汉诺塔游戏当然符合所有这4点的要求。(完)
-
编码
+关注
关注
6文章
940浏览量
54814 -
数学
+关注
关注
0文章
99浏览量
19235
原文标题：汉诺塔：闪烁在数学和心理学交汇之地奇妙问题
文章出处：【微信号：TheAlgorithm，微信公众号：算法与数据结构】欢迎添加关注！文章转载请注明出处。
发布评论请先 登录
相关推荐
工商网监
评论