正方形四角四城：最短总路长的道路形状
What is the shape of the road?
题目详情
有四座城镇位于一个正方形的四个顶点。要修建道路系统把四城连通，使总道路长度最小。
问：最优道路网络是什么形状？
There are four towns positioned on the corners of a square.The towns are to be joined by a system ofroads such that the total road length is minimized.What is the shape of the road?
解析
最优不是直接连边或“十字”，而是 Steiner 最小树：
- 在正方形内部引入 2 个 Steiner 点；
- 每个 Steiner 点连接两座相邻城镇，并且两个 Steiner 点之间也相连；
- 在 Steiner 点处三条道路两两夹角均为 。
该网络呈对称的“双 Y”形结构，且比沿边连接（总长 ）更短（其中 为正方形边长）。