用高等数学清扫马路能省多少钱

七君

大家有没有想过，平时路上的洒水车、铲雪车是怎么规划行车路线的呢？

有人会说，这还不简单，哪儿没有跑过就去跑一遍不就行了。这种方法的确能保证所有的道路都被打扫了，但是车子可能会在某几段马路上重复开，损失燃油和时间。

扫马路车、洒水车、铲雪车这类问题在数学上属于“中国邮差问题”，早在20世纪70年代就有了靠谱的解法。

这还要从1962年说起。当时，毛主席鼓励科学家们用科学解决日常生活中遇到的问题。我国数学家管梅谷就想到了这样一个问题：一个邮差走遍每条街道去送信，最短路径应该是什么样的？后来，美国数学家AlanJ. Go l dman把这个问题命名为“中國邮差问题”。

到了1973年，加拿大滑铁卢大学的数学家Jack Edmonds和IBM研究院的计算机科学家Ellis L. Johnson提出了一个至今无人超越的有效算法。他们的算法要涉及300年前的一个人，那就是欧拉。

其实，欧拉在1735年就研究过一个和管梅谷类似的问题——七桥问题，并得到了一些重要的结论。

七桥问题和我们小时候玩的一笔画的益智问题类似：在普鲁士的柯尼斯堡有两个小岛，两个小岛和附近一共有7座桥连通。现在问题来了，怎样规划路线才能恰好经过每一座桥一次？

第二年，欧拉发表了一篇论文，证明七桥问题不可解，原因是他给出了能解的一般条件，那就是每块地都必须有偶数座桥，而七桥问题不符合这种情况。这类问题在数学上发展成了图论和拓扑学。而因为欧拉的开创性贡献，能够一笔画的图被叫作欧拉图，能一笔画的路径被叫作欧拉路径。

七桥问题等价于下面这个图形。欧拉证明，只有当奇顶点的数量等于0或2时，才存在一笔画。七桥问题的奇顶点（蓝点）的数量等于4，因此无法一笔画。

欧拉还证明了一张图能一笔画的一般情况：奇顶点（也就是边的数量是奇数的顶点）的数量等于0或2。所以按照欧拉证明的定理，中文的“串”就可以一笔写成，因为它的奇顶点只有最上面和最下面两个。

把欧拉证明的结论推广到中国邮差问题的情况，最难搞定的是奇数分叉的道路，遇到三岔路口、五岔路口，走回头路几乎是必然的。

所以Edmo n ds他们的算法是，把奇数路口拎出来单独算，找到这些路口间的最短路径；而偶数岔路之间必然存在只走一次的方法，最后把两部分拼起来就可以了。但是呢，实际生活中扫马路、洒水和铲雪要比这复杂得多。比如，高速公路的整洁对司机的生命财产安全更重要，所以要早点清扫完毕；一些路段是单行线，或者对大型车辆限行。此外，“邮差”也不止一个人，清洁车之间的交接班也要考虑在内。因此在现实生活中，“中国邮差问题”很难找到最优策略，这也是为什么一开始Edmonds的算法没有得到广泛应用。

随着计算机技术的进步，一些数学家开始尝试把中国邮差问题应用到日常生活中。比如，明尼苏达大学的数学教授Peh Ng就曾用图论的思想帮明州莫里斯市政府规划冬季的铲雪线路。

而从2001年开始，北美的一些大城市就开始用比较成熟的软件，如ArcGIS来规划铲雪车的行车路径。这些软件一般会把一大块城市交通网分割成一小块一小块的，然后分别再进行计算。比如，多伦多在用图论原理对铲雪线路进行规划后，铲雪费用比之前减少了三分之一，每年节省了大约300万美元（约合人民币2000万元）。

除了道路养护，中国邮差问题的算法在很多领域还有应用。比如，在交互设计时，中国邮差问题就被用于终端产品的可用性检测。举个例子，一个手机被制造出来以后，手机制造商想要看看每个功能是不是和名称相符。比如，按下主键，点开“设置”，再点开“网络”，是不是真的会出现网络设定功能。

因为手机的功能很复杂，不同功能之间形成的网络要怎样才能有效地走个遍，这个问题有时连制造商也搞不太明白。1996年诺基亚出的2110的菜单有88个项目，一共有273种操作。如果随便按，可能一些菜单永远也不会得到检测。但是利用中国邮差问题的算法就能规划测试路径和计算步骤数量了：最少只需要按594次键盘按钮，就可以把所有的菜单和功能都过一遍。

//摘自把科学带回家微信公众号，本刊有删节/