最省的运法里,两条路不会相交
把一堆土搬去填一个坑,每一粒的运费是重量乘路程。他证的第一件事:总运费最小的时候,任何两粒土的路线都不交叉。
《挖方与填方的理论》开头就把题说清了:挖出来的叫挖方,要填的地方叫填方,运一粒土的价与它的重量和走过的路程成正比;挖方与填方的形状、位置给定之后,哪一粒送到哪一处并不是无所谓的,有一种分配能让「每一粒乘上它走的路」之和最小,他要找的就是这一种。第 667 页第二条只有三行:当运法最省时,任意两粒 A、B 的路线不能在半途相交,因为相交的 Ab + Ba 总大于不相交的 Aa + Bb——三角形两边之和大于第三边。这条性质本身一眼就懂,要紧的是他拿它往下走:挖方与填方都按面积一条一条对齐切开,每一小条都送到对面等面积的那一条上去。科学院为这篇写的摘要说它是「一类全新的极大极小问题」。演示在七粒土、七个坑之间一步步拆交叉,每拆一处总路程都变短;可拆到没有交叉,不一定就是 5040 种配法里最省的那一种——不相交只是必要条件。一粒土只许去一个地方,这道题一般很难解;1942 年康托罗维奇允许把一粒拆开分送,它才成了能解的线性规划。今天衡量两个概率分布差多远的瓦瑟斯坦距离,就是这个「把一堆搬成另一堆的最小运费」。
点「拆一个交叉」,看总路程怎么一步步往下走;拆完了再点「直接看最省的」,比一比差多少;换一组试试
现在的总路程 3.5958,交叉 8 处;5040 种配法里最省的是 2.4870,它没有一处交叉。每拆一处,总路程都严格变短。
