连接几何线的算法

Question

3

我有n条在三维空间中的打开几何线段，需要根据最小附加线长度的标准将它们连接成一条线段。请建议一个复杂度最小的算法。

- surana4u

3

我可能错了，但这对我来说听起来有点像旅行推销员问题。 - Andrew Cooper

是的，当然，听起来像这样。 - Andreas Brinck

1

在解决这个问题之前，你需要先解决“时间旅行者问题”，才能从未来得到答案。 - Déjà vu

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Yakov Galka · Accepted Answer

一个著名的算法运行时间为O(2ⁿ)。正如安德鲁在评论中所说，这是旅行商问题的更通用版本。如果您找到更好的算法，您将获得100万美元的奖励。

相反，您应该尝试使用近似解决方案，请参见wikipedia。