Steiner问题的肥皂膜解法

给定 n 个村庄的位置，要想把他们全部连通，最少需要修建多长的公路？这个问题被称为 Steiner 问题，是由数学家 Jakob Steiner 提出来的。注意，和最小生成树不同的是，公路是可以在中间汇合、分岔的。目前已经知道，Steiner 问题是 NP-hard 的，在规模很大的情况下，不能有效地得出最优解来。

然而，大自然却是无敌的，它可以迅速秒杀这样的难题。由于肥皂膜总会试图让自己的表面积最小，利用肥皂膜实验，我们可以轻易获得 Steiner 问题的解。我在很多书上都看到过肥皂膜实验的方法，不过却从没见过真正的实验视频。今天我终于看到了这样的视频(http://www.youtube.com/watch?v=dAyDi1aa40E)，把它搬进墙来，和大家分享。这个视频也很好地解释了一个普遍存在的误区：说肥皂膜实验一举解决了 NP 问题是不恰当的，因为这个实验只能找到极小值，并不能找到最小值，运气不好的话，实验结果会是失败的。

用物理方法解决数学问题，还有一个经典的例子：广义 Fermat 点问题。虽然实验的视觉感官可能没有那么振奋人心，不过还是召唤一下实验党吧。