1701742208
1701742209
迷宫的难度与各节点处发出的“枝”的数量息息相关。如果每个节点处都只有一个枝,那么这个迷宫一定是单行线迷宫。我们可以把节点想象成两颗珠子,在珠子之间有一条线,无论这条线如何盘旋环绕,一个不变的事实是,它总是连在两颗珠子之间。沙特尔教堂的迷宫就是单行线迷宫,这个迷宫没有墙,是用蓝色和白色的大理石在地板上铺出来的。
1701742210
1701742211
如果每个节点处有两个枝,迷宫同样毫无难度可言。我们可以把它设想成一堆珠子串在一条线上。走这样一个迷宫时,你不用做出选择。实际上,你通常不会把连接两个枝的连接点视为一个节点。把这两个枝看作连续的一个枝更简单,所谓的节点不过是在这个枝上打了一个结。
1701742212
1701742213
在迷宫里,一个真正的岔道至少需要几条通道汇聚在一个点(三条路形成三岔路口)。节点处汇聚的枝越多,迷宫就越难走。
1701742214
1701742215
大多数近年来的迷宫按照习惯采用了接近直线的设计,道路和限制通道的篱笆构成密密麻麻的蜂巢,填满整个区域。这使得此类迷宫比每个节点发出四个枝还要难。凡尔赛迷宫采用了更灵活的设计。各个枝不必要地平行,许多枝汇聚在一个单独的节点上。最高纪录是一个节点上汇聚了5个枝。凡尔赛迷宫的设计师安德烈·勒诺特雷(Andre Le Notre)在尚蒂伊建造了另一个迷宫,其中心节点汇聚了8个枝。
1701742216
1701742217
下表介绍了关于几个著名迷宫的统计数据。有几处,节点和枝的数目应当如何计算有待商榷。在每个场合,细心的游客需要做出决定的地点都被我算作一个节点,入口、终点和死胡同的终端也被当作节点,但是只有两个枝的冗余节点被排除在外。最后一列是平均每个节点汇聚的枝的个数,这个数量大致反映了迷宫的难度。
1701742218
1701742219
1701742220
1701742221
1701742222
凡尔赛迷宫
1701742223
1701742224
1701742225
1701742226
1701742228
右手法则
1701742229
1701742230
最著名的迷宫算法是“右手法则”:每当你面临选择时,选最右面的枝。如果走到了一个死胡同,折回来退到上一个节点,选择你没走过的枝中最右面的一条。为了具体地应用这条法则,最好的办法是始终用右手摸着右侧的篱笆,绝不漏掉右侧的枝。
1701742231
1701742232
当然,右手本身没什么特别之处。采用“左手法则”一样行得通。唯一需要注意的是,一旦进入迷宫,就必须坚持同一条法则。
1701742233
1701742234
为什么这条法则行得通?它不是一个单纯的习俗。“按顺时针方向拧紧螺丝”是一个单纯的习俗,但是你完全可以制造一枚螺纹方向相反的螺丝。右手法则比简单的习俗更深刻,它依赖于迷宫的拓扑结构。
1701742235
1701742236
我们来研究一张画在纸上的迷宫的规划图。被篱笆封锁的区域涂成绿色,绿色区域之间的白色部分是迷宫中可以通行的部分。在许多迷宫中,被篱笆封锁的区域连成一片。此时实际上只有一道篱笆,尽管它可能是蜿蜒曲折的。这个迷宫看起来像一个形状诡异的国家。对比地图上的国家,代表国土的绿色区域被边界线包围。边界线是一条单独的封闭曲线(边界线对应迷宫的篱笆)。这条曲线的任何一个部分与任何一个其他部分是连在一起的。因而,走迷宫的时候,只要把右手放在篱笆上耐心地往前走,一定会经过迷宫的所有部分。
1701742237
1701742238
前文提到童子军迷路算法——沿着溪流可以找到有人烟的地方,实际上,右手法则的基本原理与此类似。整个北美是一块大陆,北美的海岸线(包括江河构成的凹陷)是一条封闭曲线。沿着河岸或者海岸线走,最终一定会到达新奥尔良(也可以到达任何一个位于河流或海岸线上的地点)。在迷宫中,也许会包含被篱笆分隔开的“岛屿”,但是,只要入口处的篱笆和终点处的篱笆属于同一个岛屿,右手法则就可以生效。
1701742239
1701742240
右手法则(或者左手法则)的优点是简单。它的缺点有两个:首先,效率不高。跟随这条法则你会走遍右侧(或左侧)的每一条死胡同。在大多数场合,存在一条通向终点的短得多的路线。其次,右手法则并非在所有迷宫中都能生效,这一点更为糟糕。显然,所有已知的、在19世纪20年代以前建造的迷宫用这条法则都能走通。此后,数学家斯坦诺普伯爵设计了一个更复杂的迷宫,它坐落在肯特郡的切佛宁。
1701742241
1701742242
切佛宁迷宫有八个被篱笆分隔开的“岛屿”,因而右手法则不再有效。入口和终点不在同一个岛屿上。如果你依照右手法则走这座迷宫,你会围着一个区域兜圈子,永远无法到达终点。(就好比在长岛沿着河岸和海岸线走,永远无法到达新奥尔良一样。)这类迷宫需要一个更复杂的算法。
1701742243
1701742245
特雷莫算法
1701742246
1701742247
所有更强大的迷宫解法都需要某种方法以确保人们不是在兜圈子。你需要在路上做标记,沿路放丝线、撒面包屑、折弯树枝,如此等等。否则,你必须有极好的记忆力,能记住篱笆的形状,并且保证自己能认出所有曾经走过的地点。
1701742248
1701742249
有一种名为“特雷莫算法”的通用方法可以确保解决任何迷宫问题。根据法国数学家爱德华·卢卡斯(Edouard Lucas)的《娱乐数学》(1882)一书的记载,这种方法是特雷莫(M.trémaux)发明的,因而命名为特雷莫算法。这种方法可以说是前文提到的特修斯沿路放丝线的方法的精细化算法。
1701742250
1701742251
1701742252
1701742253
1701742254
切佛宁迷宫(篱笆围成的外部“岛屿”以黑色表示)
1701742255
1701742256
特修斯沿路放丝线保证自己可以原路返回入口处,不至于迷路。但是丝线不能帮助特修斯找到弥诺陶的窝。特修斯可能会走到某个岔路口,发现自己在兜圈子。当他决定下一步选哪一条路时,他可以利用这个信息加以改进,这种想法是合理的。特雷莫算法就是这么做的。
1701742257
[
上一页 ]
[ :1.701742208e+09 ]
[
下一页 ]