您当前的位置:首页 > 学习 > 阅览室

Steiner问题的肥皂膜解法

时间:11-20来源:作者:点击数:

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

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

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

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门