从线段中的集合连接点

Question

我被赋予了一项任务，在那里我必须连接2D平面上的所有点。有四项条件需要满足：

1. 连接在一起的所有部分的长度必须是最小的。
2. 一个点只能是一个线段的一部分。
3. 线段不能相交
4. 所有的点都必须使用(一个人不能孤军奋战，但只有当它无法避免时)

用图像来可视化问题：

​

错误的图像正确地连接点，虽然总长度比左边的大。

一开始，我考虑对点进行排序，然后用一条横线进行排序，并构建一棵包含各种可能性的树，尽管它看起来确实是一种复杂而复杂的解决方案。因此，我寻找更好的方法。我很想知道该做些什么，或者如何处理这个问题。

Answer 1

我想说这是对著名的旅行推销员问题的扩展。

一个很好的技术(如果有点过时的话)是使用模拟退火优化技术。

你需要对成本进行调整。(目标)函数忽略路径的部分。但是，给定一个候选连续路径，决定遗漏哪些部分以最小化其长度是相当简单的。(您首先要删除任何相交行的长度)。

Answer 2

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

我认为从编程的角度来看，“最简单”的解决方案可能实际上是循环通过，找到满足最后3个条件的所有可能性，并在循环过程中记录总长度，然后选择最后一个长度最短的方案--蛮力、猜测和检查。我认为这就是你在行动中所指的，当你提到“横扫一条线，建立一棵充满各种可能性的树”时。这种方法在计算上是非常昂贵的，但是如果代码编写正确，那么它最终应该能正常工作。

如果你想要“最好”的解决方案，你只想马上解决单一的最终答案，我恐怕我的数学技能还不够强--我甚至不确定这个问题是否有一个单一的分析解决方案，用于任意的积分集合。也许可以试着和MathOverflow的人商量一下。如果在那里的人可以用计算背后的数学来解释你，那么你仍然需要帮助，用特定的编程语言把数学转换成代码，在这里更新你的问题(也许通过链接到他们提供给你的答案)，我相信从那时起会有人帮你解决问题。

Answer 3

其中一个可能的解决办法是使用图论。

构造一个二分图G，使得每个点在两个部分中都有它的副本。现在把i and j点和weight = i == j ? infinity : distance[i][j]点之间的边缘放在一起。图中的最小权重最大匹配将是您想要的配置。

注意，由于这是在欧几里得2D平面上，结果的“边”的匹配将不会相交。假设边AB和XY相交于点A, B, X, Y。然后匹配不是最小权重，因为无论是AX, BY还是AY, BX都会在没有交集的情况下产生较小的总权重(这来自三角形不等式a+b > c)。