尽管数学总是给人留下枯燥乏味的印象，但事实恰恰相反，自古以来有太多引人入胜的游戏和玩具，都是巧妙伪装的数学问题，分散在数学的每个分支之内。
在今天的节目里，我们将从一些最古老的趣味数学问题开始，悄悄领略一下离散数学中，图论的趣味。
－文字稿－
说起数学问题，一般人总想到连绵不断的方程、函数与计算，为此怵头苦恼，但还有一类从小就给我们带来许多乐趣的“趣味数学”就完全不是这样，就比如走迷宫，我们甚至很难意识到它也是数学问题。
“克里特岛”的迷宫大概是流传最广的迷宫传说了：在神话中，克里特岛国王米诺斯得罪了波塞冬,受到天谴，他的王后就与一头牛私通，生下了牛头人米诺陶，一个吃人的可怕怪物。米诺斯于是令代达罗斯建造了一座最复杂的迷宫困住米诺陶，强迫雅典人每年进献9对童男童女给米诺陶吃——直到大英雄忒修斯来到克里特岛，对他一见钟情的公主阿里阿德涅给了他一个线团，助他斩杀了米诺陶，还走出了迷宫。
后来，欧洲人就将这种不断分支迂回错综复杂的空间布局叫做迷宫，然后就发展为一门在迷宫平面图上寻找路径的消遣游戏，很受儿童欢迎。
乍看起来，迷宫考的是眼力，但这是因为人脑面对较小的迷宫能迅速随机遍历出一条可能的路径。而对与更加复杂的迷宫，就需要专门的算法了：最简单的是溜边走，可这对于设有桥梁和隧道，或者起点终点不都在迷宫外部的迷宫就无效了。
这就是为什么忒修斯需要一个线团了——有了线团，他就知道那条路已经走过，从而不断遍历新的路径——这在今天称为特莱谋算法（Trémaux），一个典型的图论算法。
一般认为，图论起源于欧拉破解柯尼斯堡七桥问题（Seven Bridges of Königsberg），即东普鲁士的柯尼斯堡，今日俄罗斯的加里宁格勒，在穿城而过的河中有两个岛，共有7座桥以对称的位置相连，人们茶余饭后散步，便思考能否不重复地一次走遍七座桥。
在市民上百年的失败之后，欧拉在1736年证明了这压根就不可能：两岛两岸可以简化成四个点，七座桥可以简化成七条边，所以七桥问题等价为能否一笔画出这个图案，而这显然不可能，因为任何一个点如果发出奇数条边，那么它不是起点就是终点，而这个图中四个点都发出了奇数条边，远远超过了一条线起点终点各一个的配额。
将这个解法倒过来，我们就能轻易解决“周游世界问题”了：在一个十二面体上，如何沿着边不重复地遍历20个顶点。
然而另一个更古老的类似问题却难倒了欧拉：全世界的象棋都源于印度的恰图兰卡，而从9世纪开始，人们就在思考马走日能否不重复地走遍棋盘上的每一个格子——这被称为“骑士巡逻问题”。如果将这个问题抽象出来，就是在这样8×8的结点图中，能否找到一条路径不重复遍历所有结点。其中的可能性已经达到了10的51次方数量级，即便现代的计算机也难以穷举——这个问题直到1823年才得到了系统化的解决，但直到今天，我们也只算出了回到起点的走法有26534728821064种，而不回到起点的走法仍是个未知的大数字。
在今天，这几个问题都统一在图论中的哈密顿路径问题（Hamiltonian pathproblem）与哈密顿循环问题（Hamiltonian cycleproblem）之下，如果将结点抽象为事件，将边抽象为关系，我们就会发现这是研究多个事物及其相互关系的利器。
比如更经典更著名的四色问题，即问能否只用四种颜色给任意平面地图上色，明确区分所有邻国。就可以将所有的国家都抽象为一个有颜色的点，如果某个国家有一处飞地，就增加一个同颜色的点，两个国家相邻，就在对应的点之间连接一条边。那么四色问题就是在问，是否存在某种上色方案，使每条边的端点都有不同的颜色——孰料这个问题异常复杂，直到1976年，当时最快的计算机，IBM 360耗时1200小时，才首次解决了这个问题，而完全出自人脑的解法至今尚未出现。
这的确从侧面表明了图论与计算机科学的亲切关系——图论是当代计算机科学从数据结构到算法实现到通信网络等等方面的根基理论——虽然绝大多数成果都隐藏在叫人眼花缭乱的代码之下，但也有一些有趣的东西能被我们直接观察到：比如现在很多人家中都有扫地机器人，如果仅仅是随机乱跑，或者撞到障碍物就折返，那么机器人既不能充分地扫遍地面，也会浪费许多精力在相同的地点。
所以扫地机器人的实际工作，乃是确定整个房间的户型，然后以最优的路径遍历它——但是准确的地图需要准确的定位，准确的定位又需要准确的地图，这就需要给机器人装备特殊的硬件了：目前最有效的解决方案，是让机器人多角度的扫描屋顶，获取房间的形状，同时确定自己的位置，这被称为“同步定位地图构建”（SLAM）。
如此一来，机器人就能规划出最合理的行进路线，遍历全家的地面了。
新一代ILIFE智意天耀X800智能扫地机器人采用最新升级的AI视觉导航系统，搭载3颗AI智能处理芯片并通过高清摄像头和第二代陀螺仪系统 CV-SLAM视觉导航算法，同步实现全屋扫描、实时建图、精准定位、智能分区，从而智能且快速的规划清扫路线，不漏扫，不重扫，让清洁更全面、高效。
本文系网易新闻·网易号“各有态度”特色内容
联系客服
