用最小道路连接正方形顶点

hbghlyj

Steiner tree problem
我有四个城市，A=(0,0)、B=(1,0)、C=(1,1)、D=(0,1)。我被要求修建一条最短的高速公路来连接这些城市。我该怎么做？

hbghlyj

使用一个附加点，您无法获得比 $2\sqrt{2}=2.828\ldots$ 更好的结果

使用两个附加点（以及从它们出发的道路，形成 $120^\circ$ 的角度，因为这是三角形的 费马点 的最佳配置），我们可以实现等于 $1+\sqrt{3}=2.732\ldots$ 的长度：

上面证明了使用两个附加点可以达到比使用一个附加点更短。如何证明使用三个或更多点不能更短？

hbghlyj

假设有一条连接所有城市的最优高速公路。假设从A到C的道路与从D到B的道路有多个交点。设第一个交点为P，最后一个为Q。

现在，只需要有由直线AP、DP、PQ、QC、QB组成的高速公路，因为所有其他路径都会更长。此外，考虑通过P的垂直线，很明显（从反射原理）P应该与A和D等距，否则AP+DP会更长。同样地，Q应该与B和C等距。这也会使PQ比其他情况更短，因此最优安排必须使P和Q在直线$y=\frac12$上。

所以设P的坐标为$(x, \frac12)$。通过对称性，Q的坐标必须为$(1-x, \frac12)$。总距离为AP+DP+PQ+QC+QB = $4\sqrt{x^2+\frac14}+1-2x$。你可以使用微积分来最小化这个距离，当$x = \frac1{2\sqrt3}$时，最小距离为$1+\sqrt3$。