用高等数学“铲雪”！竟省2000多万……

liugang1029

用高等数学

清扫脚下路

前几天，北京下了2021年的第一场雪。这让生活在广州的超模君羡慕不已，原本打算春节前去哈尔滨看个冰雕，结果由于各种原因一直都没成行。一个月前被关进小黑屋的设计师妹子刚好来自哈尔滨。她听见超模君竟然想看雪，双眼在流露出0.3秒钟的不屑后（她可能还以为我没发现），说出了一句让我觉得她整个人都在发光的话。

她说：“下大雪看着确实挺好看的，可对那些无家可归的人，还有天没亮就起来扫街的环卫工来说，尤其是老人，下雪会让他们本来就困难的生活更加艰难。”

超模君当时就下决定，她下次要是再被关小黑屋，一定要替她求情！也就是因为她这句话，超模君突然想到了一个关于雪还有清扫马路的数学问题。看完以后，谁再问你数学有什么用，可以直接把这篇文章转给他。

数学清扫马路？

在上面这张图中，很明显，地面被白雪覆盖，公路上却干干净净。这肯定不是雪花故意绕开的选择，也不能是靠环卫工纯人力去扫除的。

没见过雪的南方孩子或许知道向积雪路面“撒盐”可以融雪，但他们一定没有见过这个东西。

不好意思，放错了，是下面这个。

组合铲雪车

当然，在国内，北方孩子最常见的还是下面这种铲雪车：

那为啥说它跟数学有关呢？这就要说到路线规划问题。

学过数学的人一辈子都不会忘记的知识点中，一定有一句“两点之间直线最短”。可公路并不总是直线连接的，而且也不只有一个“铲”那么宽。

虽然铲雪车出现的目的就是为了铲雪，但也不能随心所欲地开，能够找到一条省时、省油又能清扫干净的路线，可以省一大笔钱。
好比，加拿大的多伦多用“图论原理”对铲雪线路进行规划后，铲雪费用比之前减少了三分之一，每年节省了大约300万美金（约合2千万人民币）。

怎么用数学清扫马路？

一条最短铲雪路线是铲雪车横穿所有所需的过道，而不会回溯路线的任何部分。如果存在这样的路径，则称为欧拉路径；如果该路径在同一位置开始和结束，则称为欧拉回路。

经过一个图中每条边且仅经过一次，并且经过每个顶点的路径，叫做这个图的一条欧拉路径（Euler Path），如果欧拉路径的起点和终点是同一个点则这条欧拉路径为欧拉回路（Euler circuit）。

简单来说：

数学家发现，表示此问题的简便方法是使用图形。图形只是边缘和顶点交叉的集合。对于扫雪车路线，边缘代表扫雪车必须走的街道，并且顶点是交叉点。
例如，对于世界上最简单的城市（如下左图所示），该图由四个边和四个顶点（如下右图所示）组成。

数学家发现，确定欧拉路径是否存在的关键是奇数顶点的数量。即使顶点连接偶数个边，也将其视为顶点；如果顶点连接奇数个顶点，则将其视为奇数，反之则为偶数。上面的图形有四个偶数顶点，下面的城市有四个偶数顶点和两个奇数顶点。

通过多次试验，你很容易就会发现：

但现实并不像理想中的那么简单，问题很快就出现了：如果有两个以上的奇数顶点，该怎么办？一种答案是使用更多的铲雪车，这一看就知道不是最佳选择。

在这种情况下，实际上可以将图形分成“边缘分离的路径”，它们是没有任何公共边的简单路径。对于具有奇数个顶点的任何一组连通的顶点，该图可能会覆盖n个边不相交的路径。比如，如果我们的城市变大了一点，随之我们就添加了另一条途径，则对应的图形将如下图所示。

请注意，它具有2的平方个奇数顶点。因此可以用2条边缘分离的路径覆盖，如下所示。

（虚线为1条，实线为另1条）

这种情况下，如果你是想找到一条最少重复的路径，而不是尝试去找一条不相交的路径，该怎么办？
一种非常简单的办法就是加边，通过添加“边”，就可以使奇数顶点的数量减少2个，这样就能找到一条欧拉路径。而且，如果把奇数顶点的数量减少到0（如下图），就可以找到一个欧拉回路。

所以，如果你看到铲雪车在街道上来回开两次，这可不代表效率低，实际上可能非常高效。 洒水车和垃圾扫地车也是这个原理。

七桥问题与中国邮差问题

然而实际上，公路可能七扭八拐，这要怎么找奇偶数顶点？如果不能应用到实际生活中，那么从这个角度来看，“欧拉途径”这个数学问题确实“没什么用”。

但是，随着科技的发展，卫星定位技术已经可以把“世界”放在地图上。

又得益于计算机技术的进步，一些软件能够把城市的交通网进行分割分析，然后再分别进行计算，进而规划出路径，欧拉途径就这样被应用到了“铲雪”一事上。

但是，计算机并不是直接在欧拉问题的基础上开始的，而是先从中国邮差问题。

1962年，我国数学家管梅谷提出过一个数学问题：一名邮差从邮局出发送信，要求对辖区内每条街，都至少通过一次，再回邮局。在此条件下，怎样选择一条最短路线？后来，美国数学家 Alan J. Goldman 把这个问题命名为“中国邮差问题”。

这个问题同理可以套用扫水车、路面清理......
不过最后还是得绕回欧拉身上，因为欧拉在1735年就研究过一个和管梅谷类似的问题——七桥问题，并得到了一些重要的结论。

七桥问题 图片来源：wikipedia

在普鲁士的柯尼斯堡有两个小岛，两个小岛和附近一共有7座桥连通。怎样规划路线才能恰好经过每一座桥一次？

可是。欧拉虽然提出了七桥问题，但他给出的能解的一般条件是每块地都必须有偶数座桥，而七桥问题不符合这种情况，也就是说七桥问题不可解。

欧拉证明，只有当奇顶点的数量等于0或2时，才存在一笔画。七桥问题的奇顶点（蓝点）的数量等于4，因此无法一笔画。后来，类似七桥问题、中国邮差问题的问题在数学上发展成了图论和拓扑学。因为欧拉的开创性贡献，一笔画的图被叫做欧拉图，一笔画的路径被叫做欧拉路径。

串的奇顶点有2个（最上和最下）

把欧拉证明的结论用到到中国邮差问题上，遇到三岔路口、五岔路口时就不得不回头。

于是计算机数学家们就把奇数路口单独另算，再找到这些路口间的最短路径；又因为偶数岔路口一定存在只走一次的方法，最后把这两部分拼起来就找到了“最短路径”。

也就是：

就这样，北方的孩子再也不用滑雪橇上学了。

写在最后

所以，如果有一天你听见有人说博士生“扫大街”，千万不要再惊讶了！

在这个浮躁的时代，一些人觉得研究纯数学和应用数学的数学家要名难出名，要利难获利，他们应该把自己的聪明才智用在搞金融上。

数学研究是一个功在后世的学科，正如200多年前欧拉的一个数学证明，可以在今天方便我们的生活一样。伟大的数学家看的不是眼前，而是未来。

作者简介：超模君，数学教育与生活自媒体博主，新晋理工科奶爸。出版过[color=var(--weui-LINK)]《芥子须弥 · 大科学家的小故事》；《数学之旅·闪耀人类的54个数学家》[color=rgba(0, 0, 0, 0.498)]。后续数学文化创意多多，欢迎关注认识！

本文系网易新闻·网易号“各有态度”特色内容部分资料来源于网络转载请在公众号中，回复“转载”