连接线段中set的点

Question

我有一个任务,我必须连接2D平面中的所有点.有四个条件需要满足:

1. 连接在一起的所有段的长度必须是最小的.
2. 一个点可以是仅一个线段的一部分.
3. 线段不能相交
4. 必须使用所有点(一个不能单独留下,但只有在无法避免的情况下)

图像可视化问题:

错误的图像正确连接点,虽然总长度大于左侧的长度.

起初,我考虑对点进行排序,并使用扫描线进行排序并构建所有可能性的树,尽管它看起来像是一种复杂解决方案,具有巨大的复杂性.因此,我寻找更好的方法.我会很感激一些提示要做什么,或者我怎么能解决这个问题.

Answer 1

哇，这是一个棘手的问题。这需要满足很多条件。

我认为从编程的角度来看，“最简单”的解决方案实际上可能就是循环遍历，找到满足最后3个条件的所有可能性，并在循环时记录总长度，然后选择长度最短的一个最后 - 蛮力，猜测并检查。我认为这就是你在OP中提到“扫线并构建一棵包含所有可能性的树”时所指的内容。这种方法的计算成本非常高，但如果代码编写正确，它最终应该总是有效的。

如果你想要“最佳”解决方案，即你只想立即解决单个最终答案，恐怕我的数学技能还不够强 - 我什至不确定是否有任何单一的分析对于任意点集合，该问题的解决方案。也许尝试与MathOverflow 的人员核实。如果那边有人可以向您解释该计算背后的数学，那么您仍然需要帮助将该数学转换为某种编程语言的代码，请在此处更新您的问题（也许带有他们为您提供的答案的链接）并且我确信从那时起有人能够帮助您。