走出迷宫 | 糟糕的选择04 | Bad Choices 04| 逻辑少年 | 计算思维

首页 » 家庭教育 » 走出迷宫 | 糟糕的选择04 | Bad Choices 04| 逻辑少年 | 计算思维

走出迷宫 版权说明:《Bad Choices》是由Ali Almossawi著作的一套计算思维书籍,可以通过https://bookofbadchoices.com/访问本书英文版本。书中通过一系列人物的故事场景,以插画的方式展示了一个个现实生活中遇到的问题,进而引出了一些计算思维的问题,内容丰富且非常有趣。本书的目标读者是计划学习编程的儿童、学生,通过阅读本书可以开拓眼界,培养计算思维习惯。

本章背景故事(请孩子阅读,家长伴听)

裁缝店迷宫
走出迷宫难题

小I先生是个成功的裁缝店主,他今天遇到了一个大麻烦。由于自己的店面近两年来不断扩充,增加货架和弯曲的走廊,有一天,在同样货架上满是纺线和缝纫用具的某个地方,他竟然迷路了~他究竟要如何才能找到走出的路,还是说,他注定要被埋葬在自己一手创建的这个迷宫里面呢?

首先,让我们讨论一下 小I先生可能会选择回到商店门口的三种方法。

目标:到达商店的门口。
方法一:穿过通道,随机转弯,直到他找到出路。
方法二:右手扶墙,跟着墙走,一直向右移动。
方法三:从墙上取下一根线,在他走过通道时将线展开。如果他走到了死胡同,或者如果发现一根线有交叉的时候,他就会转身,回到上一个转弯,然后走另外一条路。

走出迷宫 02
走出迷宫02

思考完成再接着往下看哦!

走出迷宫 分析过程(请家长+孩子分段阅读思考)

在开始分析之前,我们先来阅读一个关于牛头怪和迷宫的传说吧!


希腊的故事讲述的是牛头怪Minotaur,一个半牛半人的生物,当他出生时,伟大的建筑师代达罗斯建造了一个迷宫来放置这个凶猛的生物。
“一旦进去,就会沿着曲折的小路无休止地走,却永远找不到出口。年轻的雅典人每次都被带到这个地方并留给牛头怪,没有人可以逃脱。”
幸运的是,即将要进入迷宫作为食物喂给牛头怪的忒修斯,得到了国王的女儿阿里阿德涅的爱情,她帮忙制定了一个计划来帮助他逃脱。
国王的女儿派人去找迷宫的建筑师代达罗斯,找到一条离开迷宫的方法。之后又派人去找忒修斯,告诉他这条线索。离开的方法正是一个线团,他要把线团的一端系在门的内侧,然后一边继续走一边松开。忒修斯这样做了,并确信他可以随时返回他的来时路,他大胆地走进迷宫寻找牛头怪。正好牛头怪睡着了,忒修斯压住他,把他按在地上并用他的拳头战胜了怪物。

按下牛头怪的故事我们先不详细讨论,一起看看小I先生的三条方法吧:

方法一类似一只老鼠落在了迷宫里,其进行搜索导航的方式。老鼠没有高级的认知能力,只是从一个地方随机走到另一个地方,直到偶然遇到一块奶酪。实际上这种方法有时被称为“随机老鼠"。您可能想象的出来,这种方法很慢。

方法二要更有趣一些,尽管仍然非常简单。用这种方法,小I 用一只手摸着墙壁走,最终他能够找到通往商店前面的路。为什么这种方法是有效的呢?因为如果你重新排列迷宫的墙壁,你实际上可能会得到一条直线。所以你可以把迷宫想象成一根绳子,很明显,小I做的就是从绳子的一端走到另一端。

方法二也被经常称为跟墙行方法或者右手法则或者左手法则,虽然方法二比方法一更快,但这种方法的主要问题是,如果迷宫中恰好有所谓的岛屿或循环,它就失效了。如同下方左侧图形表示,这种环形的墙壁,不直接连接到外墙,而这正式让方法二失效的原因。而右侧图形则是方法二成功的常见场景。

方法二的迷宫失效
右手法则的迷宫失效

另外一个有关达尔文的有趣故事是,在他发表著名的《物种起源》之前,他大概花了20年的时间去研究进化论的相关论证。提出这样一个如此规模的理论,就像在一个迷宫中,路上的分岔口就是你的论点,而死胡同则是观点无效的证明,出口则是观点合乎前提的逻辑证明结果。正如我们在方法三和牛头怪的故事中看到的,这种在论证中立论和反驳的认知方式,对于我们从实际迷宫里逃离是同样奏效的。

使用方法三,小I先生通过线团进行了回溯 - 每当他遇到死胡同时,回溯并尝试不同的路径。这种方法让小I先生能够返回到交叉路口,并尝试更有希望的能力路线保证了最终会找到出路。这种逃离迷宫的策略被称为 Trémaux 算法,来自法国数学家 Edouard Lucas 于 1882 年出版的 Récréations Mathématiques。而最近的研究似乎还表明,蚂蚁当遇到前面的道路断裂的时候,会使用回溯方法找寻道路。方法三比方法一更快,并且能够处理循环,避免方法二遇到的岛屿情况。

请注意,我们在这里介绍的三种方法,对于我们已经在迷宫中并想要出去的时候很有用。事实上,还有其他方法可以更快地逃离迷宫,但需要我们事先知道迷宫的样子。我们在这里看到的三种方法并不能保证走出迷宫的最短路径。

走出迷宫
走出迷宫03

无论如何,这一次小I先生通过聪明才智总算是找到了出口,但是如果他继续这样无序扩张和乱放布置,下一次他可能必须要带着一个绳子走来走去了。

今天学习结束了,下面一起来通过实验体会一下cache的方法吧!

走出迷宫 本章延申练习(请家长+孩子共同完成)

这种迷宫解密方法在很多的互联网软件中会使用到,比如社交软件会提示你可能认识谁,地图软件告诉你更好的搜索结果等,而更常见的可能是扫地机器人,事实证明,并非所有扫地机器人都是一样的,因为在它们能够覆盖多少房间的地面时,有些机器人不像其他的那么复杂。较简单的扫地机器人可能会以随机的线或圆圈漫游,而更好的可能会首先映射一个房间,确定墙壁和任何角落和角落可能的位置,然后在网格中从一端到另一端来回移动。换句话说,当机器人知道如何最好地从房间的一个地方到达另一个地方时,它会最大化其目标,从而使房间更干净。

Written By

li, Mickey