本帖最后由 deducemath 于 2011-4-7 22:54 编辑 5 Q- x, y2 Y: E0 H
- e( r! x1 ]" c b% S# X0 v/ x
迷宫注记-那些千回百转的乐趣
" Y5 q- p7 M% Q) V. u' O ?. I7 ]. z e8 L& x, P
“黄蓉向郭靖打个手势,反向后行,庄中道路东转西绕,区区折折,尤其是转弯处的栏杆亭榭全然一模一样,几下一转,哪里还分辨得出东西南北……” $ C- L1 V1 ?6 j
——《射雕英雄传》第13回 ' y" z n& I: a1 r2 S, z( S) l+ X& e% T
美丽的古希腊神话起源
- n3 S! I) ~$ j. r6 b
9 `/ \: U$ k6 r! X3 `# P忒休斯的克里特之旅 文艺复兴佛罗伦萨画家作 现存于法国Avignon " z5 ?& s6 C; w" ~/ w
$ |( T7 L; k3 W$ o, Y- n6 _ 米诺斯是克里特岛的国王,需向海神波塞冬献祭,苦于自己养的牲畜实在龌龊,于是请求海神赐予一头白牛,海神答允。因此牛身材毛色堪称美的典范,米诺斯不忍杀之,另找牛代替。海神震怒,附体于白牛,诱惑米诺斯的妻子,致使其产下牛首人身的怪物,即米诺陶洛斯。米诺斯建迷宫将其囚禁。祸不单行,米诺斯的儿子在雅典遇害,于是他强迫雅典每9年献7对少男少女,把他们关进迷宫作怪物之食。第3次进献时,雅典王子忒修斯亲自出马,此公修长俊美,米诺斯之女阿里阿德涅对其一见钟情。公主赠其金线团与宝剑,借助这两样宝物,王子杀死怪物后轻松走出迷宫并携公主与少男少女驾船逃走……(可以改编成AVG了。)
& G0 r( p5 {7 u* D: B. w% e; a/ w, F1 U. ~" X; w5 @( w9 @
“所有的迷宫神话都以这样或那样的方式叙述了这四重故事:旅行、考验、启蒙和复活。”(《智慧之路——论迷宫》P43) ) Z) r* n0 s( w; j
$ r4 Z7 H2 E) f迷宫的描述性定义: 拓扑结构为图(状态或位置用点表示,相邻则连边),从起始点出发到终止点的路不明显,探索的过程存在一些障碍。 " s* u5 } Z- N& z
) P( x0 T) H2 P6 i/ r广义的迷宫: 世界、人生的象征 棋类等博弈游戏 滑块谜题(如华容道) 拓扑解套谜题(如九连环 ,状态图仅为一条简单的路,虽结构简单,实际操作起来却不平凡) 朝圣之旅(教堂迷宫) + u5 I- Z) G6 u& K
北京圆明园有个黄花阵迷宫,为郎世宁设计,被毁后重建,如图:
9 ]- _* ?8 {& `2 z3 F! Y: G$ o 8 D; b% K7 y- \% ^; C3 G, X
使用迷宫的推理或解谜小说: ; X4 Q9 x" J' C% G3 R1 p, |: L1 I- W
8 o2 i- u }" {- T) C8 E8 k3 R
1《迷宫馆的诱惑》绫辻行人 日本推理小说家 (文学性差些)
; T t# z% R7 I/ ~- P4 {
& K9 X0 E* F- ?# V+ O( V2《迷宫案》 古利克(高罗佩)荷兰汉学家 (美妙的小说,收入《大唐狄公案》,迷宫形状为篆体字“虚空楼阁”,到达迷宫中心的的秘密在一幅画中。) 2 v% \+ N/ P/ `- `; G3 i
: v4 f" ^ e/ b1 p1 m. l( U9 l3《玫瑰的名字》 埃科 意大利知识分子 (有大量中世纪宗教文化,若算推理小说,最多二等)
. z6 j% v7 [6 G
) L1 u- _) Y& d# \2 V2 Y- k博尔赫斯有名的短篇:小径分叉的花园
" M. K) `" c5 N- n# u6 Y2 q9 S l/ G- A( U3 ~
一个百科全书式的云南总督建造了一个谁也走不出的迷宫,后来被某汉学家揭示其实此迷宫是他留下的充满矛盾的小说手稿,小说中主人公面临不同的选择时选择了所有的可能性(类似于AVG的多线程设计)。“他认为时间有无数系列,背离的、汇合的和平行的时间织成一张不断增长、错综复杂的网。” ! P; O. [! t; t) E6 x J5 L
) c# S: y$ q, E% T# l# Q; O
可以把红楼梦看做文学迷宫,不过这个迷宫是开放式的,没有终点的迷宫,至今还有很多人在寻找众多的可能性…… / X) h( [. m/ d$ y6 [* w/ T
o: V- L ~4 v4 `" `$ `Mechanical Mazes # Y3 r* W6 ] c" J0 o% C
6 V' ]2 H# d+ J/ x. E% v3 X
如果你把一些Mechanical Puzzles的状态图画出来,再分别将初始和终止状态节点标记为入口和出口,就得到了Mechanical Mazes。马丁加德纳90岁生日时,世界各地的谜题大师们纷纷撰文致敬,这些精妙的小文集锦成书《A Lifetime of Puzzles: A Collection of Puzzles in Honor of Martin Gardner's 90th Birthday》,其中荷兰谜题大师M.Oskar van Deventer 的文章就是论述Mechanical Mazes的。下面为文中三个截图,具体内容大家可以参看网上的电子书(不全)。 1 R) X2 R7 l& C* B9 H/ k7 Y
1 x3 _( U. Y9 K# @; ^3 ^) P" B3 j % ]/ {5 c: O- B1 J `# E- N' q
8 p) U. x" l8 _
AVG中的迷宫5 ?) J+ @1 d+ \; q! f4 K
塞伯利亚1 花园迷宫,只可惜游戏没充分利用,主要作风景了。 8 @' w9 ]7 c' I
5 S0 [; a; {$ Z2 t% T3 g6 M静物1 机械蜘蛛谜题即为一动态迷宫,很不错的设计。 ; q5 d! f( P8 z. B \
# [ X, r" R* P. [
静物1 还有个简单下水道迷宫,走的时候只知道迷宫的局部信息。
; L2 Z& H" C' V: w: ~$ d . `7 R" u! T R& l6 j8 a
机械迷城里面的电梯锁就是经典的双马换位谜题,见加德纳的书《啊哈!灵机一动》。貌似有点复杂的棋盘图拓扑结构只不过一个简单的圈,在纸上换种画法谜题就很平凡了。
0 M6 l& h+ F5 G( r. @! I. a 5 t1 T- _. X# @& }) B2 S
米勒山庄疑案4 也有个小迷宫, 走不对就被里面的怪物吃掉(很多电子游戏的迷宫-怪物模式来源于那个迷宫起源神话),虽然拿到了迷宫地图,可是看不懂。 & s% W' z/ }: n1 x( O# U u
2 b D8 H/ N- p: B# V% N" F童年的记忆碎片 " U, `8 a6 H5 P3 O, w. Z5 |
6 ]; e' ?! {# x+ i; K4 Z! }' n
幽长狭窄的胡同,高低大小不一的红瓦屋顶,以及连接它们的一道道斑驳的砖墙与庭院树木,自然形成一个独特的空中迷宫。 我喜欢在这个迷宫中游荡,如同卡尔维诺《树上的男爵》。这种游荡不只含有冒险的性质,除了需要躲避某些不识趣的大人以及探索新的路线,有时可以躺下来呆看微风中的白云,有时帮邻居大妈采摘香椿树叶,有时偷几串葡萄或未成熟的小葫芦,而最具目的性的莫过于爬到邻居家玩红白机。当年玩的最多的大概为魂斗罗、双截龙和超级玛丽。超级玛丽最后一关(8-4)便是一个很微妙的迷宫, (全局设计图http://www.gamefaqs.com/nes/525243-super-mario-bros/faqs/54149)攻略如下图
7 {0 N' g7 u# K+ N! j' ]5 u6 _0 W
7 t2 d3 S x$ E6 |, T迷宫的数学
3 m! a8 [& Z0 c5 @% S6 F2 G, n" ~, j9 m- M) h; s& y
维基百科的图片被封掉了,不知道猴年马月能恢复。将每个词条所在的网页看做一个有向图的节点,每个词条的解释当中含有很多其它词条的链接,在词条与其解释中出现的词条所在网页之间连有向边,得到一个很庞大的有向图。这个图应当含有一个巨大的连通分支(渗流现象),此连通分支的直径却很小(小世界现象)。不用搜索引擎,将初始所在词条的网页作为起始点,指定一个目标词条,则在它们之间找路的过程如同在迷宫中摸索。 , Y7 i! {8 x/ @: \# d
& V4 B% X/ V9 d5 C" @, m7 ]
渗流理论(概率论与图论的交叉学科,主要研究临界现象)中的随机图可以看成一个随机迷宫。下面是Marek Biskup的关于渗流簇上随机游动问题的PPT截图: * S4 N7 X2 q- U! R0 Y' V
7 z3 W1 f% u2 k9 U8 N R/ X
考虑无限大的二维正方形格子图,每条边以概率1-p删除。若p较大,剩余图会包含一个无限大的连通子图,称其为随机迷宫。蜗牛在此迷宫中作随机游动,在适当的尺度变换下,运动轨迹收敛于布朗运动。 0 N, r: I( z/ l; E, ?7 u! q9 v
6 g' w9 Q3 t+ j! V, D4 Y
许多谜题的状态图极复杂,如同超级迷宫。例如,魔方的状态图(魔方置换群的Cayley图,参见http://www.jaapsch.net/puzzles/cayley.htm)有43252003274489856000个顶点,每个顶点的度为18(基本旋转数),猜测其直径为20,也就是说,任何一种魔方的初始状态都可以在20步内还原。08年Tomas Rokicki使用群论与计算机证明状态图直径大于等于20小于等于22。见http://www.mathpuzzle.com/30November2008.html 08.8.19添加材料。2010年7月Morley Davidson, John Dethridge, Herbert Kociemba, and Tomas Rokicki最终彻底解决魔方问题,“上帝之数”(God’s Number)为20。见http://www.cube20.org/ 及http://www.mathpuzzle.com/ 10.8.9材料。
1 ]. I2 q% h' X7 U3 p, G/ W6 ]' g0 l1 K* L
) y- V, T0 Q9 Z' [* K2 G
(国外关于迷宫的书很多,国内似乎只有吴鹤龄先生的《迷宫趣话》论述比较全面,北京理工大学出版社出版,推荐之。) |