最小化总长度的非相交线段

Question

我希望能找到一种更好的算法来解决以下问题：

在二维平面上有N个起点(紫色)和N个目标点(绿色)，我想要一个连接起点和目标点的算法，通过线段(棕色)相连接，且不出现任何相交(红色)，同时最小化所有线段长度的总和。

我第一次尝试使用C++来枚举所有可能状态，寻找无相交状态，并在其中选取总线段长度最短的状态 O(n!)。但我认为必须有更好的方法。

有什么想法吗？或者说有哪些有效的搜索关键词？

- masoud

---

也许是某种拓扑排序？ - Kerrek SB

@DietmarKühl：切换端点可能会导致出现不同的冲突。 - Oliver Charlesworth

@OliCharlesworth: 是的，我知道这一点。这就是保证进度的部分：如果事情以创建循环的形式得到解决，它将无法正常工作。 - Dietmar Kühl

@Masoud M：你预计要处理多少个点对？ - RBarryYoung

@MasoudM：哇，那你肯定不会用暴力方法解决100对数据，因为这是100的阶乘，这个数字真的很大。我很想知道你决定实现什么算法，因为qq3提供的参考算法比O(n!)好得多，但也非常复杂。 - RBarryYoung

Answer 1

这是二维欧几里得最小匹配问题。该链接包含有关该问题已知的参考文献。鉴于您想要最小化总长度，因此非交叉约束是多余的，因为可以通过取消交叉来减少任何交叉线段对的长度。

- qq3

---

@Walkerneo，这不是交叉双腿的问题，因为你的脚之间和臀部之间的距离比你的腿长要短。 - zzzzBov

@qq3：严格来说，我认为这是二分图最小欧几里得匹配问题，是你链接中提到的一个子集。 - RBarryYoung

@dmckee：qq3说，在最小总长度约束条件下，不相交规则是冗余的，而不是与之“冲突”（在数学上，这些是非常不同的事情）。对于二分图问题（这个问题就是），局部可分离的改进也总是全局有效的改进，因此局部长度交叉规则也适用于全局。（我不确定这是否适用于非二分图情况，二分图要简单得多）。 - RBarryYoung

@RBarryYoung> 啊...我现在要删除的评论不再有意义了，因为我回复的那条评论已被删除。我们达成了一致。 - dmckee --- ex-moderator kitten

Answer 2

您可以选择一个随机的连接，然后每次通过更改其端点的连接来删除一个交叉点。这个操作会减少总长度（通过三角不等式）。由于线相互交叉的方式有限，在有限步骤内我们就可以到达一个非交叉的解决方案。在实践中，它应该迅速收敛。

- Saeed Amiri

---

总长度会减少，但它是有限的，因为它至少会是零。 - Saeed Amiri

这是一个救命稻草的解决方案！在我的研究中帮了我很多忙！谢谢！！ - Aaron John Sabu

@AaronJohnSabu，我已经重新表述了一下，希望现在更好了。我不知道确切的时间复杂度，但如果我们将其视为随机拉斯维加斯算法，我相信它应该会非常快地收敛。我认为这个算法被称为民间传说，但我不知道是否有任何对这个算法的适当分析发表（如果你想在某个地方引用它，你也可以将链接指向这个页面，但我不是第一个想出类似于这个算法的人，它太自然了）。 - Saeed Amiri

@SaeedAmiri 谢谢！嗯，它的时间复杂度肯定小于或等于 n!，因为有 n! 种可能的行组合方式。我想我会把它命名为贪心算法，因为它在每一步都进行短视的优化，接近最终的最优解。 - Aaron John Sabu

@AaronJohnSabu，我实际上希望看到n^2或n^3的随机化预期时间。我认为n!不能成为最坏情况，因为要创建最坏情况，必须从某个位置X开始，并在解决交叉时访问几乎所有可能的组合。这听起来是不可能和太悲观的。 - Saeed Amiri

Answer 3

根据qq3的回答，交叉约束是多余的，只需再进行一步操作：在最小化总长度的同时为起点分配终点。幸运的是，这个问题有一个多项式时间算法：

匈牙利算法 是一个组合优化算法，可以在多项式时间内解决分配问题。

它将时间复杂度从O(n!)降低到O(n³)。

- masoud

Answer 4

看起来你可以使用 BSP 类型算法。

- Krumelur