| 央视网|中国网络电视台|网站地图 |
| 客服设为首页 |
中国网络电视台 >
| 首播 |
|
|
| 重播 |
|
|
这是一种充满复杂通道的建筑物，很难找到从其内部到达入口或从入口到达中心的道路。在世界的不同文化发展时期，这些奇特的建筑物始终吸引人们沿着弯弯曲曲、困难重重的小路吃力地行走，寻找真相。还在找出口吗？不妨看看死理性派是怎么走迷宫的吧。
迷宫的历史和它的结构
迷宫最早出现于希腊神话中——用来囚禁 克里特岛 国王 米诺斯 的半人半牛的怪物儿子 弥诺陶洛斯 。米诺斯每年都会送 7 对童男童女进来供他儿子享用。后来在米诺斯女儿阿里阿德涅的帮助下，雅典英雄 忒修斯 靠着一团金线，摸进迷宫顺利地杀死了这头怪物。
早期的一些绘画艺术还原了这座传说中克里特岛迷宫。很多人发现，这座迷宫虽然很绕，却并没有岔路，只要“一条道走到黑”，就能来到中心。也就是 欧拉路径 ，即从迷宫的入口到中心遍历了所有的边且没有重复。
从左至右：迷宫中的弥诺陶洛斯，14世纪杰里科地图，克里特式迷宫。 图像来源：Wikipedia
想象一根有限长的绳子，如果要用这根绳子来围成一条路径，且使得人在走这条路径的时间花费尽量长，那么最直接的方法就是建造这样的“克里特式迷宫”，让线圈紧密地盘绕再盘绕。
克里特式迷宫可以当做很美的装饰画，也能在工业实践中得到广泛应用，但它因为没有极具迷惑性的岔路，“迷”的属性并不算突出。因此后来就从这种最初的迷宫中，又发展出了各类复杂的迷宫。
从数学上来说，形状奇怪、看起来让人眼花缭乱的各种各样的迷宫，无非是一个图。当我们不考虑各结点的具体位置，而只考虑其相对位置，也不考虑各条边的具体长度和形状时，就可以把迷宫的拓扑结构画出来。
对于非克里特型迷宫（克里特型迷宫中没有分岔和歧路，不能用“图”表示），可根据其拓扑结构分为两大类，单连通的和多联通的。单连通的迷宫，图中没有回路。多联通的迷宫，图中包含回路。那如何判断一张迷宫地图是单连通的还是多联通的呢？只要看它的墙的结构就行了：如果迷宫中的墙都是互相连着的，那它就是单连通的；如果迷宫中有孤立的、不与其他墙相连的墙，这个迷宫就是多联通的。迷宫的类型不同，在其中行走到达目的地的策略也就不同。
破解黑暗中的迷宫
对于事先我们并不知晓全貌的迷宫，或者即使我们能了解到它的全貌（比如一些旅游景点中的迷宫），但置身其中时仍会有“旁观者清，当局者迷”的感觉。这样的迷宫该如何破解呢？
当然，你可以选择神话中忒修斯拉线绳的方法——如果你有足够长的绳子的话，这无疑是最保守和安全的方法。但这里要介绍的几种比它巧妙的多的方法。
首先就是“左/右手法则”方法。顾名思义，就是进入迷宫后，选择一个方向，之后贴着墙壁一直走下去。这是最常见的走迷宫方法，其原理其实在上面“克里特式迷宫”中也已提到，就在于考察迷宫的拓扑结构，无论围墙是多么的蜿蜒曲折，把它抻直了也就是一根线段而已，迷宫的出入口分别对应着这条线段的两个端点。我们从入口进（或者选择该条线段上任意一点开始），沿着这条线笔直走下去，当然会走到出口。但这个法则也时常有失灵的时候。因为它的前提是“入口和出口都在一条线段上”，也就是说这堵墙必须是连通的才行，而如果遇到“回字形”迷宫，出口和入口并不连通，则会出现绕了一圈返回原地的情况。
“左/右手法则” 图像来源：Algorithmus der Woche
但我们可以稍微调整下策略来应对：从出发点出发，碰到墙后向右沿墙走，直到方向和出发时的方向相同，这时直走直到触壁。反复使用此策略即可走出上述的“回”字形迷宫了。但问题随之又来了，比如在走 G 形迷宫时，采用这个策略就会陷入困境，相反这时“左/右手法则”却是个更好的方法。
实际上，最大的问题是，当你身处迷宫中时，你很难判断出这是一个什么类型的迷宫，因此也就无法采取针对策略走出去。那有没有一种万能的走迷宫策略呢？英国埃克塞特一个叫 Jon Pledge 的 12 岁小男孩就想到了一种现在被称为 Pledge 算法的解决方案。
“回”字形迷宫解决方法与字母G形迷宫困境 图像来源：Algorithmus der Woche
这个算法的策略是这样的：先选择一个“偏好方向”（favored direction），比如东、南、西或北，然后总是尽可能朝这个方向走。当遇到墙时，向右转身沿左侧墙壁继续前进，直到面向偏好方向且转身数的总和为零（ 初始值为 0，顺时针转身时减 1，逆时针转身时加 1 ）为止。此时，继续沿偏好方向向前走。这个算法在“回”字形迷宫中可避开障碍，在字母 G 形迷宫中实际上就变为了“左/右手法则”。虽然 Pledge 算法也不是万能的，但用它已足以应对大多数迷宫了——对于方向感不太好的朋友在野外使用时，可能还需要一块指南针。此外还可以通过标记每个分岔路口或走过的轨迹来判断哪些是旧路、哪些是新路，从而达到尽量避免走重复路径、尽快找到正确路径的目的。这类的方法在这里就不赘述了。
染色法解迷宫
另一类迷宫的特点是你时刻可以看到它的全貌，比如人们经常玩的“纸上迷宫”。它的解法很容易，只要用铅笔把所有看到的死胡同涂黑，正确的路径就显现出来了。另一种略显粗暴而又不失技术含量的解法是 图像分析法 。这里举个简单的例子：
“图像分析法”破解“纸上迷宫” 图像来源：Cris’s Image Analysis Blog
我们可以看到图（a）中的迷宫错综复杂，徒手找到那条正确的路径确实需要花点儿功夫。利用“图像分析法”，我们先将它染色，如图（b）所示，红色为墙，黑色为通道。之后用图像处理软件的上色工具（如windows画图板的油漆桶）对迷宫的最外墙上色，便可如图（c）所示明显区分出两个不同的区域，我们要找的路径也就“跃然纸上”了（解答如图（d）所示）。
这种方法的原理就在于我们可以把迷宫看成由一块块不规则拼图拼接出来的平面图形（本例是两块），而正确的路径就是这些拼图之间的缝隙。我们只要把这些拼图区分出来即可。
解谜时间：迷宫变形体
任何迷宫游戏设计者的目的只有一个，就是要耗费玩家找到正确路径的时间。为了达到这一目的，这些设计者们可谓“不择手段”，大家不妨来试试这些迷宫的变形体。
（a）“分形迷宫”。设外层大迷宫为X的话，则内层A、B、C则是三个与X一模一样的小迷宫，任务是从“+”号走到“-”号；
图像来源：matrix67.com
如果你搞定了这个“简单”的，那不妨试试这个更加复杂的：
图像来源：matrix67.com
（b）要求从中心的小星星出发，只能沿箭头方向行走，最后还必须回到小星星
图像来源：wikipedia
还等什么呢？动手试一试吧。
实际生活中，折磨大家最痛苦的想必是 PC 游戏中迷宫吧。比如说当年让人爱恨交加的《仙剑奇侠传》。
参考资料：
[1] 《迷宫趣话》吴鹤龄，毛晚堆
[2] 维基百科：Maze, Maze solving algorithm
[3] Solving mazes using image analysis
[4] Der Pledge-Algorithmus
热词：
中央广播电视总台 中国网络电视台 版权所有
违法和不良信息举报电话:010-88047123 京ICP证060535号 京网文【2014】0383-083号
网上传播视听节目许可证号 0102004 新出网证（京）字098号 中国互联网视听节目服务自律公约
排行榜
意见反馈
顶
踩
收藏
MSN或QQ好友
贴到博客或论坛
转发邮件
