- m# a! E1 q' X' z0 @- g7 Y1 y, D" b" c2 p. g
& f: Z% m) E( o1 {, V6 u% x- S' v i
& U8 [4 B3 ~" F$ V1 d T
有人会说，这还不简单，哪儿没有跑过就去跑一遍不就行了嘛。 % `( L! _+ ^- ^
这种方法的确能保证所有的道路都被打扫了，但是车子可能会在某几段马路上重复开，损失燃油和时间。 + S6 O9 j7 g* @4 ^# `0 K
北美的一个大城市多伦多在好好用数学规划之前，每年就白白多花了3百万美金的冤枉钱。
# s' m9 M% h& \& n) ^( d6 n; o- B 9 D7 W% Q( P2 M5 f
! O0 P0 m1 m H* \( N 是这样的，扫马路、洒水车、铲雪车这类问题在数学上属于中国邮差问题，中国邮差问题本身早在20世纪70年代就有了靠谱的解法。
+ ]7 r- S5 y2 ]0 [7 w* Z! } 事情还要从1962年说起。当时，毛主席鼓励科学家们用科学解决人民日常生活中遇到的问题。
/ F% h# M$ u: T0 {/ D) I" a0 N5 v
我国数学家管梅谷就想到了这样一个问题：一个邮差走遍每条街道去送信，最短路径应该是什么样的？
$ h" ?! r# y W! F8 w, p 后来，美国国家标准技术研究所的数学家 Alan J. Goldman 把这个问题命名为“中国邮差问题”。
7 D# m3 h' V0 n" L8 d6 o2 F V1 q7 i% B- D- a1 Q6 N
到了1973年，加拿大滑铁卢大学的数学家 Jack Edmonds 和 IBM 研究院的计算机科学家 Ellis L. Johnson 提出了一个至今无人超越的有效算法。他们的算法要 cue 到三百年前的一个人，那就是欧拉。
- N. |$ a5 J. f 其实，欧拉在1735年就研究过一个和管梅谷类似的问题——七桥问题，并得到了一些重要的结论。 / ]4 Z9 P$ F0 u# ~9 Q) C' I; q \
七桥问题 图片来源：wikipedia ) W a- f& o y+ d5 O8 V+ z5 o& P
七桥问题和我们小时候玩的一笔画的益智问题类似：在普鲁士的柯尼斯堡有两个小岛，两个小岛和附近一共有7座桥连通。现在问题来了，怎样规划路线才能恰好经过每一座桥一次？ + r& x& \+ e# m' ?" z
第二年，欧拉发了一篇论文，证明七桥问题不可解，原因是他给出了能解的一般条件，那就是每块地都必须有偶数座桥，而七桥问题不符合这种情况。
+ H, P0 a' q3 C8 B( i; \( s
! o2 I" S; B! l
后来，这类问题在数学上发展成了图论和拓扑学。而因为欧拉的开创性贡献，能够一笔画的图被叫做欧拉图，一笔画的路径被叫做欧拉路径。
8 J. d4 Y1 h; v$ }0 j
七桥问题等价于右边这个图形。欧拉证明，只有当奇顶点的数量等于0或2时，才存在一笔画。七桥问题的奇顶点（蓝点）的数量等于4，因此无法一笔画。 ' S1 U: E6 M% M: T/ `
欧拉还证明了一张图能一笔画的一般情况：奇顶点（也就是边的数量是奇数的顶点）的数量等于0或2。 u* y4 ?$ b3 i) ^. A
所以按照欧拉证明的定理，中文的“串”就可以一笔写成，因为它的奇顶点只有最上面和最下面一共两个。
" u6 E" S: Y3 ^; f& j串的奇顶点有2个（最上和最下），因此可以一笔画。 + w8 D2 T: M( `+ [# x
下面这个德国儿童的传统娱乐项目——Haus vom Nikolaus puzzle （圣尼古拉房屋）也可以一笔画—— & _) \3 ^3 o% p
1 }9 K- A' i2 W/ Y2 Y
顺便说一下，圣尼古拉房屋有44种解法。 # r3 a# l' ^8 r+ u( D! f) K
: m; Q9 i8 A8 k8 Y, n4 J! N6 _7 b 把欧拉证明的结论推广到中国邮差问题的情况，最难搞定的是奇数分叉的道路，遇到三岔路口、五岔路口，走回头路几乎是必然。
! N5 [# ]. A% M, L U( I9 s- J3 J& J* G9 h) l2 ]
所以 Edmonds 他们的算法是，把奇数路口拎出来单独算，找到这些路口间的最短路径；而偶数岔路之间必然存在只走一次的方法，最后把两部分拼起来就可以了。 x- l$ E5 D5 a% O4 m3 V% x6 t( g
/ A! m* J2 t8 W
但是呢，实际生活中扫马路、洒水和铲雪要比这复杂得多。 : i5 L, c8 a+ {% a- ]; t
比如，高速公路的整洁对司机的生命财产安全更重要，所以要早点清扫完毕；一些路段是单行线，或者对大型车辆限行。此外，“邮差”也不只一个人，而且不能无限“肝”活，清洁车之间的交接班也要考虑在内。
) y) D5 \7 Y' ?7 c" d 因此在现实生活中，中国邮差问题很难找到最优策略，这也是为什么一开始 Edmonds 的算法没有得到广泛应用。 , x Y) C: k0 K( u% G, C
到了20世纪90年代，随着计算机技术的进步，一些数学家开始尝试把中国邮差问题应用到日常生活中。比如，明尼苏达大学的数学教授 Peh Ng 就曾用图论的思想帮明州莫里斯市政府规划冬季的铲雪线路。 # v) _. H: u+ u% n0 O. V. z
而从2001年开始，北美的一些大城市就开始用比较成熟的软件（如 ArcGIS）来规划铲雪车的行车路径。这些软件一般会把一大块城市交通网分割成一小块一小块的，然后分别再进行计算。 , ~1 f: I! z# A2 X& u- i; \# l! Y
g7 n6 R; \' { v3 @ 比如，多伦多在用图论原理对铲雪线路进行规划后，铲雪费用比之前减少了三分之一，每年节省了大约3百万美金（约合2千万人民币）。 6 J# D) N+ r% t$ C$ {) f1 n5 p
多伦多的市政道路交通的运营经理 Hector Moreno 表示，在用ArcGIS之前，行车路线主要靠经验和人工计算，现在就不需要这么麻烦了。
- z3 Y9 m4 U* W C, Q v3 g波士顿市政府的应用数学团队 图片来源：boston.gov
% ?. w8 J' ?& t% `7 v6 t: \3 y- h6 g 2010年，波士顿市政府也组建了自己的数学团队——Mayor's Office of New Urban Mechanics，用数学和计算机来规划铲雪路线。 2 I9 S, N% k( b. \; S; c# x
像波士顿这样的大城市用数学进行规划真的太有必要了。2015年，为了铲雪，波士顿的铲雪车一共开了47万千米，差不多可以绕地球12圈了。铲雪的花费也是惊人的，那年的暴雪让波士顿一共掏出了3500万美金（约合2.3亿人民币）。
" K1 V- q; D5 i) ?" q& a
2015年，波士顿的暴雪创下了记录。图片来源：newyorktimes
8 o! i1 o I" r+ f. J/ g- i 除了道路养护，中国邮差问题的算法在很多领域还有应用。比如在交互设计时，中国邮差问题就被用于终端产品的可用性检测。 % [4 M- g ~) B0 Y
举个例子，一个手机被制造出来以后，手机制造商想要看看每个功能是不是和名称相符。比如按下主键，点开“设置”，再点开“网络”，是不是真的会出现网络设定功能。 8 Q2 { G Z0 g7 ~2 D1 M0 Z
8 r8 s- r) T3 A. h6 d
因为手机的功能很复杂，不同功能之间形成的网络要怎么样才能有效地走个遍，这个问题有时连制造商也搞不太明白。1996年诺基亚出的2110的菜单有88个项目，一共有273种操作。如果随便按，可能一些菜单永远也不会得到检测。
5 `! P& ]& E7 e6 b9 [! e+ {( P8 I4 Z 但是利用中国邮差问题的算法就能规划测试路径和计算步骤数量了：最少就只需要按594次键盘按钮就可以把所有的菜单和功能都过一遍了。
# R3 I4 y: J% B& K# d1 }3 s) T* ]7 x+ u) |* A( V. r, i. Y ]
在检查网页链接有没有“死角”的时候也可以用到中国邮差问题的算法。 ) N. B8 n @5 H# @2 \% Q' D
比如，富兰克林故居的网站(benjaminfranklinhouse.org)有66个网页，1191个超链接。如果网络测试员没有头脑一顿乱点，不但要做无用功，有些网页和链接可能还点不到。但是利用中国邮差问题的算法，测试员知道只要点2248次就可以测试完所有的网页和超链接了。
2 y9 ^' b+ ^' ?. R3 i% j v# Y位于英国伦敦的富兰克林故居
$ F+ f, ]) P" c5 c" ?+ ?( D 欧拉路径判定挺好掌握的呢：口中串串，乃米田共。
0 C) ?0 l3 y; O
0 N8 [* c" ^. K( ^( K
% S) u$ p0 @9 X- |
8 [: {7 x2 G; G% I* W7 }6 w | 
发表于 2020-9-6 17:41:48
QQ好友和群
收藏
淘帖
问题专业，描述清楚
伸手党/灌水/看不懂
楼主
