数学

用迷宫困住死理性派?没门!

死理性派怎么走迷宫的,破解迷宫

D-Horse 发表于  2011-11-04 15:33

这是一种充满复杂通道的建筑物,很难找到从其内部到达入口或从入口到达中心的道路。在世界的不同文化发展时期,这些奇特的建筑物始终吸引人们沿着弯弯曲曲、困难重重的小路吃力地行走,寻找真相。还在找出口吗?不妨看看死理性派是怎么走迷宫的吧。

迷宫的历史和它的结构

迷宫最早出现于希腊神话中——用来囚禁 克里特岛 国王 米诺斯 的半人半牛的怪物儿子 弥诺陶洛斯 。米诺斯每年都会送 7 对童男童女进来供他儿子享用。后来在米诺斯女儿阿里阿德涅的帮助下,雅典英雄 忒修斯 靠着一团金线,摸进迷宫顺利地杀死了这头怪物。

早期的一些绘画艺术还原了这座传说中克里特岛迷宫。很多人发现,这座迷宫虽然很绕,却并没有岔路,只要“一条道走到黑”,就能来到中心。也就是 欧拉路径 ,即从迷宫的入口到中心遍历了所有的边且没有重复。

/gkimage/sm/b0/8t/smb08t.png

从左至右:迷宫中的弥诺陶洛斯,14世纪杰里科地图,克里特式迷宫。 图像来源:Wikipedia

想象一根有限长的绳子,如果要用这根绳子来围成一条路径,且使得人在走这条路径的时间花费尽量长,那么最直接的方法就是建造这样的“克里特式迷宫”,让线圈紧密地盘绕再盘绕。

克里特式迷宫可以当做很美的装饰画,也能在工业实践中得到广泛应用,但它因为没有极具迷惑性的岔路,“迷”的属性并不算突出。因此后来就从这种最初的迷宫中,又发展出了各类复杂的迷宫。

从数学上来说,形状奇怪、看起来让人眼花缭乱的各种各样的迷宫,无非是一个图。当我们不考虑各结点的具体位置,而只考虑其相对位置,也不考虑各条边的具体长度和形状时,就可以把迷宫的拓扑结构画出来。

对于非克里特型迷宫(克里特型迷宫中没有分岔和歧路,不能用“图”表示),可根据其拓扑结构分为两大类,单连通的和多联通的。单连通的迷宫,图中没有回路。多联通的迷宫,图中包含回路。那如何判断一张迷宫地图是单连通的还是多联通的呢?只要看它的墙的结构就行了:如果迷宫中的墙都是互相连着的,那它就是单连通的;如果迷宫中有孤立的、不与其他墙相连的墙,这个迷宫就是多联通的。迷宫的类型不同,在其中行走到达目的地的策略也就不同。

破解黑暗中的迷宫

对于事先我们并不知晓全貌的迷宫,或者即使我们能了解到它的全貌(比如一些旅游景点中的迷宫),但置身其中时仍会有“旁观者清,当局者迷”的感觉。这样的迷宫该如何破解呢?

当然,你可以选择神话中忒修斯拉线绳的方法——如果你有足够长的绳子的话,这无疑是最保守和安全的方法。但这里要介绍的几种比它巧妙的多的方法。

首先就是“左/右手法则”方法。顾名思义,就是进入迷宫后,选择一个方向,之后贴着墙壁一直走下去。这是最常见的走迷宫方法,其原理其实在上面“克里特式迷宫”中也已提到,就在于考察迷宫的拓扑结构,无论围墙是多么的蜿蜒曲折,把它抻直了也就是一根线段而已,迷宫的出入口分别对应着这条线段的两个端点。我们从入口进(或者选择该条线段上任意一点开始),沿着这条线笔直走下去,当然会走到出口。但这个法则也时常有失灵的时候。因为它的前提是“入口和出口都在一条线段上”,也就是说这堵墙必须是连通的才行,而如果遇到“回字形”迷宫,出口和入口并不连通,则会出现绕了一圈返回原地的情况。

/gkimage/21/hd/5j/21hd5j.png

“左/右手法则” 图像来源:Algorithmus der Woche

但我们可以稍微调整下策略来应对:从出发点出发,碰到墙后向右沿墙走,直到方向和出发时的方向相同,这时直走直到触壁。反复使用此策略即可走出上述的“回”字形迷宫了。但问题随之又来了,比如在走 G 形迷宫时,采用这个策略就会陷入困境,相反这时“左/右手法则”却是个更好的方法。

实际上,最大的问题是,当你身处迷宫中时,你很难判断出这是一个什么类型的迷宫,因此也就无法采取针对策略走出去。那有没有一种万能的走迷宫策略呢?英国埃克塞特一个叫 Jon Pledge 的 12 岁小男孩就想到了一种现在被称为 Pledge 算法的解决方案。

/gkimage/yr/1l/kr/yr1lkr.png

“回”字形迷宫解决方法与字母G形迷宫困境 图像来源:Algorithmus der Woche

这个算法的策略是这样的:先选择一个“偏好方向”(favored direction),比如东、南、西或北,然后总是尽可能朝这个方向走。当遇到墙时,向右转身沿左侧墙壁继续前进,直到面向偏好方向且转身数的总和为零( 初始值为 0,顺时针转身时减 1,逆时针转身时加 1 )为止。此时,继续沿偏好方向向前走。这个算法在“回”字形迷宫中可避开障碍,在字母 G 形迷宫中实际上就变为了“左/右手法则”。虽然 Pledge 算法也不是万能的,但用它已足以应对大多数迷宫了——对于方向感不太好的朋友在野外使用时,可能还需要一块指南针。 此外还可以通过标记每个分岔路口或走过的轨迹来判断哪些是旧路、哪些是新路,从而达到尽量避免走重复路径、尽快找到正确路径的目的。这类的方法在这里就不赘述了。

染色法解迷宫

另一类迷宫的特点是你时刻可以看到它的全貌,比如人们经常玩的“纸上迷宫”。它的解法很容易,只要用铅笔把所有看到的死胡同涂黑,正确的路径就显现出来了。另一种略显粗暴而又不失技术含量的解法是 图像分析法 。这里举个简单的例子:

/gkimage/r3/yt/lr/r3ytlr.png

“图像分析法”破解“纸上迷宫” 图像来源:Cris’s Image Analysis Blog

我们可以看到图(a)中的迷宫错综复杂,徒手找到那条正确的路径确实需要花点儿功夫。利用“图像分析法”,我们先将它染色,如图(b)所示,红色为墙,黑色为通道。之后用图像处理软件的上色工具(如windows画图板的油漆桶)对迷宫的最外墙上色,便可如图(c)所示明显区分出两个不同的区域,我们要找的路径也就“跃然纸上”了(解答如图(d)所示)。

这种方法的原理就在于我们可以把迷宫看成由一块块不规则拼图拼接出来的平面图形(本例是两块),而正确的路径就是这些拼图之间的缝隙。我们只要把这些拼图区分出来即可。

解谜时间:迷宫变形体

任何迷宫游戏设计者的目的只有一个,就是要耗费玩家找到正确路径的时间。为了达到这一目的,这些设计者们可谓“不择手段”,大家不妨来试试这些迷宫的变形体。

(a)“分形迷宫”。设外层大迷宫为X的话,则内层A、B、C则是三个与X一模一样的小迷宫,任务是从“+”号走到“-”号;

/gkimage/s9/ni/o5/s9nio5.png

图像来源:matrix67.com

如果你搞定了这个“简单”的,那不妨试试这个更加复杂的:

/gkimage/w4/bu/03/w4bu03.png

图像来源:matrix67.com

(b)要求从中心的小星星出发,只能沿箭头方向行走,最后还必须回到小星星

/gkimage/ey/de/ht/eydeht.png

图像来源:wikipedia

还等什么呢?动手试一试吧。

 
实际生活中,折磨大家最痛苦的想必是 PC 游戏中迷宫吧。比如说当年让人爱恨交加的《仙剑奇侠传》。

参考资料:

[1] 《迷宫趣话》吴鹤龄,毛晚堆

[2] 维基百科:Maze, Maze solving algorithm

[3] Solving mazes using image analysis

[4] Der Pledge-Algorithmus

热门评论

  • 2011-11-04 15:41 吴师傅 数学专业

    看谁和我抢沙发!!!

    上图:

    [23] 评论
  • 2011-11-04 16:12 啊文


    坐办公室的人员表示2分钟无压力解决,LZ来个有难度的课后练习吧

    [16] 评论
  • 2011-11-04 15:57 烧鸡X 给水排水专业

    就应该把死理性派扔到哈利波特三强争霸赛里面那个迷宫里...

    [3] 评论

显示所有评论

全部评论(209)
  • 1楼
    2011-11-04 15:41 吴师傅 数学专业

    看谁和我抢沙发!!!

    上图:

    [23] 评论
  • 2楼
    2011-11-04 15:45 m千惠

    额~没杀到

    [0] 评论
  • 3楼
    2011-11-04 15:49 乱室佳人 古人类学博士

    仙五还没有拆封……

    [0] 评论
  • 4楼
    2011-11-04 15:52 李慕儿

    刚看的时候才1个回复。。。

    [0] 评论
  • 5楼
    2011-11-04 15:57 烧鸡X 给水排水专业

    就应该把死理性派扔到哈利波特三强争霸赛里面那个迷宫里...

    [3] 评论
  • 6楼
    2011-11-04 15:58 猪了个去 智能科学专业

    仙剑三外传。。。问路篇。。。。。。。。完全打不下去的都。。。。

    [1] 评论
  • 7楼
    2011-11-04 16:00 Frizen

    95版仙1的鎖妖塔啊...吃掉我好多天人參的惡魔><

    [1] 评论
  • 8楼
    2011-11-04 16:05 Berry.L

    仙3和寰神结才是最迷宫游戏~

    [1] 评论
  • 9楼
    2011-11-04 16:08 Ent 古生物学博士生,科学松鼠会成员

    老仙剑还能忍……
    后来的新仙剑,那个将军冢……

    [1] 评论
  • 10楼
    2011-11-04 16:12 啊文


    坐办公室的人员表示2分钟无压力解决,LZ来个有难度的课后练习吧

    [16] 评论
  • 11楼
    2011-11-04 16:25 Superpiggie

    分型迷宫有人能不用纸笔不依赖计算机纯靠眼睛和大脑走出来么...

    [0] 评论
  • 12楼
    2011-11-04 16:26 comein 无机化学硕士生,DIY爱好者

    被导语吸引进来了……发现楼上好多的仙剑粉丝啊……

    [1] 评论
  • 13楼
    2011-11-04 16:27 comein 无机化学硕士生,DIY爱好者
    引用乱室佳人的回应:仙五还没有拆封……


    仙五不好玩……强烈推荐古剑奇谭!

    [0] 评论
  • 14楼
    2011-11-04 16:33 啊文
    引用Superpiggie的回应:分型迷宫有人能不用纸笔不依赖计算机纯靠眼睛和大脑走出来么...

    可以,就是很耗时间

    [0] 评论
  • 15楼
    2011-11-04 16:46 Izual_Yang

    最后那个迷宫倒走无压力。有个flash版的类似迷宫,比这个要难得多,有个地方要多绕一点才能找对路。

    记得有段时间我曾经沉迷于pc版或flash版的高维迷宫和高维扫雷……

    [0] 评论
  • 16楼
    2011-11-04 16:48 yyy_daodao

    分形迷宫好有趣

    [0] 评论
  • 17楼
    2011-11-04 17:08 演算天地

    嘻嘻
    如果图谁随机图呢

    [0] 评论
  • 18楼
    2011-11-04 17:12 missiled

    歪个楼 ,问:为什么重楼把魔剑给景天不是给他飞蓬的镇妖剑?
    答:因为楼哥不会过锁四……

    [1] 评论
  • 19楼
    2011-11-04 17:20 两点两分

    可以用a*寻路算法来实现吗?

    [0] 评论
  • 20楼
    2011-11-04 17:21 huangshu2

    迷宫好复杂,看晕了。

    [0] 评论
  • 21楼
    2011-11-04 17:22 薛定的饿猫


    请用染色的方式破解这张图

    windows的画图怎么弄?

    [1] 评论
  • 22楼
    2011-11-04 17:29 李茉莉

    走仙一到仙五到古剑的迷宫从来只靠直觉屡试不爽~………好吧我承认三外锁妖塔四层我看攻略了 我猜死理性派对这种带机关的迷宫没招吧…

    [0] 评论
  • 23楼
    2011-11-04 17:30 一剑终情

    一个小时这么多回复。。都是牛人。。

    [0] 评论
  • 24楼
    2011-11-04 17:33 薛定的饿猫


    已解决
    牛死了

    [1] 评论
  • 25楼
    2011-11-04 17:33 薛定的饿猫

    爽歪了,这个染色法

    [0] 评论
  • 26楼
    2011-11-04 17:37 薛定的饿猫

    [0] 评论
  • 27楼
    2011-11-04 17:44 薛定的饿猫

    [0] 评论
  • 28楼
    2011-11-04 17:49 markc

    后面那几个迷宫直接看到头晕@@

    [0] 评论
  • 29楼
    2011-11-04 17:53 薛定的饿猫


    我已经玩high了

    [0] 评论
  • 30楼
    2011-11-04 17:55 破壳子

    看晕了已经

    引用米兰 昆德拉的回应:
    [0] 评论

显示所有评论

你的评论

登录 发表评论

D-Horse
D-Horse 生物信息学硕士生

作者的其他文章

更多科研事,扫码早知道

关于我们 加入果壳 媒体报道 帮助中心 果壳活动 免责声明 联系我们 移动版 移动应用

©2017果壳网    京ICP证100430号    京网文[2015] 0609-239号    新出发京零字东150005号     京公网安备11010502007133号

违法和不良信息举报邮箱:jubao@guokr.com    举报电话:13488674940