主题
Search

斯坦纳线段问题


给定 n 个点,找到连接这些点的线段,使其总长度尽可能短。这些线段不一定需要是点与点之间的直线。

对于三个点,如果所有都小于 120 degrees, 则线段是将这三个点连接到一个中心点 P 的线段,该中心点 P 使角 <A>PB, <B>PC, 和 <C>PA 都为 120 degrees。如果一个 大于 120 degrees, 则 P 与这个较大的 重合。

对于四个点,P 是两条对角线的交点,但所需的最小线段不一定是这些对角线。

该问题的一个修改版本是,给定两个点,找到连接这些点的线段,使其总长度最短,且每个分支点只能连接到三个线段。这个版本的问题没有通用的解决方案。


使用 Wolfram|Alpha 探索

请引用为

Weisstein, Eric W. “斯坦纳线段问题。” 来自 MathWorld—— Wolfram Web 资源。 https://mathworld.net.cn/SteinersSegmentProblem.html

主题分类