1

要点是......我们有两组点A和B。集合A和B具有相同数量的点n。

正式问题：

在A和B中的点之间构造最小成本完全二分匹配。匹配(a, b)的成本是距离 (a, b)。是否存在比O(n^3)更快的算法？

笔记：

  • A中的每个点a和B中的每个点b都在匹配(a, b)中。
  • A或B中的每个点a都恰好在一个匹配中。
  • sum( 每一个(a, b)匹配的距离(a, b ) )被最小化。

例子：

  • 点 a (0,0)
  • b 点 (2,0)
  • 点 c (0,1)
  • 点 d (-2,2)
  • 设置 Z {a, d}
  • 设置 Y {b, c}

解决方案：

匹配1：（a，b）（d，c）

sum (距离(a, b),距离(d, c)) = 2 + sqrt(5) ~ 4.23

匹配2：（a，c）（d，b）

sum (距离(a, c),距离(d, b)) = 1 + sqrt(20) ~ 5.47

匹配 1 (a, b) (d, c) 是最小成本完全二分匹配！

4

1 回答 1

3

是的。如果将顶点之间的距离作为它们之间的边的权重，那么这是一个加权二分图。找到最大/最小权重匹配的任务称为分配问题。

可以使用Fredman 和 Tarjan (1987)中开发的方法在O(|V|(|E|+|V| log |V|)时间内解决该问题。

欧几里得空间可能有进一步的改进。正如这里所讨论的。值得注意的是，Vaidya (1988)提出了一种用于 L1、L2 和 L∞ 度量的O(n² log n)算法，该算法改进了 L1 和 L∞ 度量的O(n² (log n)³)。Agarwal、Efrat 和 Sharir（2006 年，第 7 节）对此进行了改进，给出了一种在O(n^(2+ε))时间内运行的算法。

如果你牺牲精确性，你可以做得更好。Agarwal 和 Varadarajan (2004)提出了一种概率算法，给定值0<ε<1，在O(n^(1+ε))时间内找到与乘法O(log(1/ε)内的预期成本的匹配)的最优值。

您的点是否恰好位于凸多边形的边缘？然后Marcotte 和 Suri (1991)会很有趣：他们为此提出了一个精确的O(n log n)算法。如果多边形是非凸的，但仍然很简单，那么您可以在同一篇论文中使用他们的O(n² log n)算法。

于 2017-04-18T18:43:18.573 回答