电脑鼠走迷宫比赛为何会烧坏参赛者的大脑?比赛规则其实很简单,谁的电脑鼠率先抵达迷宫终点谁就能获得冠军。
这里所说的电脑鼠是一个由微处理器控制的小型智能机器人车辆,它要在整个迷宫中自动探索,还必须随时掌握自身位置,准确获取墙壁信息并做记录,最终依靠算法找出最佳路线。
迷宫的最终布局只在每次比赛开始前公布,且后续不能更改程序代码。每名参赛选手可提前预跑5次,时间会被限制在10分钟之内,以便让算法提前学习迷宫路线。
由于最早期的迷宫终点基本都位于地图边缘,因此那时的参赛者都会选择沿着墙边行走,这样就能迅速到达目的地。为了增加玩法和比赛难度,迷宫终点被换到了中间位置,并且三面全都设有围墙阻挡。但这可难不倒聪明的参赛者,他们开发出了深度优先搜索算法。
机器鼠会记住路上的每个分叉口,每当在前进过程中遇到死胡同便会返回到上一个分叉口重走,就这样不断尝试新路线,最终成功找到迷宫的终点。但这种搜索方式有个弊端,由于只在碰壁时才掉头返回,因此它找到的可能并不是最快抵达终点的路线。
后来参赛者们又开发出了广度优先搜索算法,当经过第一个分叉口时系统会自动标记位置信息,当经过第二个分叉口时机器鼠便会掉头折返走第一个分叉口的其他路线,如此不断往复循环直至终点。
虽说这样能找到最快抵达终点的路线,但迷宫却有256个单元格,会浪费相当多的探路时间,赛前可能连跑都跑不完,更别提获得冠军了。
后来有个聪明的参赛者发明出了洪水填充搜索算法,这种算法的核心是先标记出迷宫中每个方块到终点的距离,探路时机器鼠会从大到小不断沿着数字向前运动,每当遇到墙壁阻碍时便会记住地图上的对应数字,通过更新计算中找到终点。
该过程类似于用水淹没迷宫,一旦水被填满就会标记位置,如此一来只要能抵达终点,它就能理顺所有来时的路线,也能逆向折返找出最短的路线。
但问题就在于最短的路线并不意味着它能以最快速度抵达终点,它能以最快速度抵达终点,比如这条赛道,这是通往终点的最短路径,每个参赛者都会选择这条路,而这却是彗星选手选择的路,足足多出了5.5米的距离。
它的机器算法与别人不同,我们暂称为最快优先搜索算法。虽说这条路离着终点更加遥远,但它的转弯次数却少了很多,并且用斜角过弯替代了直角过弯,削减了机器所做的多余动作,平均移动速度也提高了不少。即使需要多跑一些路程,也比距离近的路线更快。
就是这样看似简单的迷宫比赛,其中却蕴藏着无穷无尽的知识量,至少融合了微电子、计算机软硬件、通信和电子工程等多种前沿技术,复杂程度超出所有人的想象。
我是舰长,我一直都在。
Copyright © 2024 妖气游戏网 www.17u1u.com All Rights Reserved