algorithm - 连接几何线的算法

Question

我有 n 条开放的 3D 几何线。需要根据线的端点之间的附加线的最小长度的标准将它们连接成一条线。请建议具有最小复杂度的算法。

Answer 1

一个最著名的算法在 O(2 ⁿ ) 时间内运行。正如安德鲁在他的评论中所说，这是一个更普遍的旅行商问题。如果您找到更好的算法，您将获得 1000000 美元的奖金。

您应该尝试近似解决方案，请参阅wikipedia。