积雪清扫车 用高等数学 清扫脚下路 前几天,北京下了2021年的第一场雪。这让很多生活在南方的孩子羡慕不已。她说:“下大雪看着确实挺好看的,可对那些无家可归的人,还有天没亮就起来扫街的环卫工来说,尤其是老人,下雪会让他们本来就困难的生活更加艰难。” 环卫工人清扫积雪 也就是因为她这句话,突然想到了一个关于雪还有清扫马路的数学问题。 看完以后,谁再问你数学有什么用,可以直接把这篇文章转给他。 数学清扫马路? 积雪 在上面这张图中,很明显,地面被白雪覆盖,公路上却干干净净。这肯定不是雪花故意绕开的选择,也不能是靠环卫工纯人力去扫除的。 没见过雪的南方孩子或许知道向积雪路面“撒盐”可以融雪,但他们一定没有见过这个东西。 不好意思,放错了,是下面这个。 组合铲雪车 当然,在国内,北方孩子最常见的还是下面这种铲雪车: 那为啥说它跟数学有关呢?这就要说到路线规划问题。 学过数学的人一辈子都不会忘记的知识点中,一定有一句“两点之间直线最短”。可公路并不总是直线连接的,而且也不只有一个“铲”那么宽。 虽然铲雪车出现的目的就是为了铲雪,但也不能随心所欲地开,能够找到一条省时、省油又能清扫干净的路线,可以省一大笔钱。 好比,加拿大的多伦多用“图论原理”对铲雪线路进行规划后,铲雪费用比之前减少了三分之一,每年节省了大约300万美金(约合2千万人民币)。 怎么用数学清扫马路? 一条最短铲雪路线是铲雪车横穿所有所需的过道,而不会回溯路线的任何部分。如果存在这样的路径,则称为欧拉路径;如果该路径在同一位置开始和结束,则称为欧拉回路。
简单来说: 数学家发现,表示此问题的简便方法是使用图形。图形只是边缘和顶点交叉的集合。对于扫雪车路线,边缘代表扫雪车必须走的街道,并且顶点是交叉点。 例如,对于世界上最简单的城市(如下左图所示),该图由四个边和四个顶点(如下右图所示)组成。 数学家发现,确定欧拉路径是否存在的关键是奇数顶点的数量。即使顶点连接偶数个边,也将其视为顶点;如果顶点连接奇数个顶点,则将其视为奇数,反之则为偶数。上面的图形有四个偶数顶点,下面的城市有四个偶数顶点和两个奇数顶点。 通过多次试验,你很容易就会发现: 但现实并不像理想中的那么简单,问题很快就出现了:如果有两个以上的奇数顶点,该怎么办? 一种答案是使用更多的铲雪车,这一看就知道不是最佳选择。 在这种情况下,实际上可以将图形分成“边缘分离的路径”,它们是没有任何公共边的简单路径。对于具有 奇数个顶点的任何一组连通的顶点,该图可能会覆盖n个边不相交的路径。 比如,如果我们的城市变大了一点,随之我们就添加了另一条途径,则对应的图形将如下图所示。 请注意,它具有 个奇数顶点,因此可以用2条边缘分离的路径覆盖,如下所示。 (虚线为1条,实线为另1条) 这种情况下,如果你是想找到一条最少重复的路径,而不是尝试去找一条不相交的路径,该怎么办? 一种非常简单的办法就是加边,通过添加“边”,就可以使奇数顶点的数量减少2个,这样就能找到一条欧拉路径。而且,如果把奇数顶点的数量减少到0(如下图),就可以找到一个欧拉回路。 所以,如果你看到铲雪车在街道上来回开两次,这可不代表效率低,实际上可能非常高效。 洒水车和垃圾扫地车也是这个原理。 七桥问题与中国邮差问题 然而实际上,公路可能七扭八拐,这要怎么找奇偶数顶点?如果不能应用到实际生活中,那么从这个角度来看,“欧拉途径”这个数学问题确实“没什么用”。 但是,随着科技的发展,卫星定位技术已经可以把“世界”放在地图上。 又得益于计算机技术的进步,一些软件能够把城市的交通网进行分割分析,然后再分别进行计算,进而规划出路径,欧拉途径就这样被应用到了“铲雪”一事上。
这个问题同理可以套用扫水车、路面清理...... 不过最后还是得绕回欧拉身上,因为欧拉在1735年就研究过一个和管梅谷类似的问题——七桥问题,并得到了一些重要的结论。 七桥问题 图片来源:wikipedia
可是。欧拉虽然提出了七桥问题,但他给出的能解的一般条件是每块地都必须有偶数座桥,而七桥问题不符合这种情况,也就是说七桥问题不可解。
后来,类似七桥问题、中国邮差问题的问题在数学上发展成了图论和拓扑学。因为欧拉的开创性贡献,一笔画的图被叫做欧拉图,一笔画的路径被叫做欧拉路径。 串的奇顶点有2个(最上和最下) 把欧拉证明的结论用到到中国邮差问题上,遇到三岔路口、五岔路口时就不得不回头。 于是计算机数学家们就把奇数路口单独另算,再找到这些路口间的最短路径;又因为偶数岔路口一定存在只走一次的方法,最后把这两部分拼起来就找到了“最短路径”。 也就是: 就这样,北方的孩子再也不用滑雪橇上学了。 写在最后 所以,如果有一天你听见有人说博士生“扫大街”,千万不要再惊讶了! 在这个浮躁的时代,一些人觉得研究纯数学和应用数学的数学家要名难出名,要利难获利,他们应该把自己的聪明才智用在搞金融上。 数学研究是一个功在后世的学科,正如200多年前欧拉的一个数学证明,可以在今天方便我们的生活一样。伟大的数学家看的不是眼前,而是未来。 然而,科学的发展不能只靠数学家来推动!每一位数理爱好者的出现,都是科学长远发展的推动力。 |
|