c++ - 最小对数

Question

在2D 平面 中给定2N 个点，您必须将它们分组为N 对，这样它们之间的距离总和所有对的点是可能的最小值。所需的输出只是总和。

换句话说，如果a1,a2,..an分别是第一对，第二对...和第n对的点之间的距离，那么(a1+a2+...一个)应该是最小的。

让我们考虑这个测试用例，如果 2*5 点是:<强>{20,20},{40, 20},{10, 10},{2, 2},{240, 6},{12, 12},{100, 120},{6, 48},{12, 18},{0, 0}

期望的输出是237。

这不是我的作业，我想知道不同的方法而不是蛮力。

Answer 1

您似乎在寻找Minimum weight perfect matching .

有一些算法可以利用这些是平面中的点这一事实。本文:Mincost Perfect Matching in the Plane有一个算法，还提到了一些以前的工作。

---

根据要求，这里简要描述了一个“简单”的图形最小加权完美匹配算法。这是 Papadimitriou 和 Steiglitz 所著的组合优化、算法和复杂性一书中关于加权匹配的部分章节的简短摘要。

假设您有一个带权无向图 G(具有偶数个节点)。通过添加缺失的边并为它们分配非常大的权重，该图可以被认为是一个完整的加权图。

假设顶点标记为 1 到 n，顶点 i 和 j 之间的边的权重为 c(i,j)。

我们有 n(n-1)/2 个变量 x(i,j) 表示 G 的匹配。如果 i 和 j 之间的边在匹配中并且 x(i ,j) = 0 如果不是。

现在匹配问题可以写成线性规划问题:

最小化和 c(i,j) * x(i,j)

条件是

Sum x(1,j) = 1，其中 j 的范围是 1 到 n。

Sum x(2,j) = 1，其中 j 的范围是 1 到 n。...

Sum x(n,j) = 1，其中 j 的范围从 1 到 n。

(Sum x(1,j) = 1 基本上意味着我们选择恰好与标记为 1 的顶点相交的一条边。)

最后的条件是

x(i,j) >= 0

(我们可以说 x(i,j) = 0 或 1，但这不会使它成为线性规划问题，因为约束是线性方程或不等式)

有一种叫做单纯形法的方法可以解决这个线性规划问题，在多项式时间内给出变量个数的最优解。

现在，如果 G 是二分图，可以证明我们可以获得一个最优解，使得 x(i,j) = 0 或 1。因此，通过求解二分图的线性规划问题，我们得到一个集合对每个 x(i,j) 的分配，每个都是 0 或 1。我们现在可以通过选择 x(i,j) = 1 的那些边 (i,j) 来获得匹配。约束保证它将是权重最小的匹配。

不幸的是，对于一般图(即 x(i,j) 为 0 或 1)，情况并非如此。 Edmonds 发现这是因为图中存在奇数环。

因此除了上述约束之外，Edmonds 还添加了额外的约束，即在任何大小为 2k+1(即奇数大小)的顶点子集中，匹配边的数量不超过 k

枚举顶点的每个奇数子集以获得集合 S(1)、S(2)、...、S(2^n - n) 的列表。设 S(r) 的大小为 2*s(r) + 1。

那么上面的约束是，对于每个集合S(r)

Sum x(i,j) + y(r) = s(r)，对于 S(r) 中的 i，j。

Edmonds 然后证明这足以保证每个 x(i,j) 为 0 或 1，从而给我们一个最小权重完美匹配。

不幸的是，现在变量的数量呈指数级增长。所以单纯形算法，如果就这样按原样运行，将导致指数时间算法。

为了解决这个问题，Edmonds 考虑了这个线性规划问题的对偶(我不会在这里详细介绍)，并表明原始对偶算法在对偶上运行时只需 O(n^4) 步即可得出一个解决方案，从而给我们一个多项式时间算法!他通过证明在算法的任何步骤(他称之为开花)最多 y(r) 的 O(n) 不为零来证明这一点。

这里有一个链接可以更详细地解释它:http://www.cs.ucl.ac.uk/staff/V.Kolmogorov/papers/blossom5.pdf , 第 2 节。

我之前提到的这本书值得一读(虽然可能有点枯燥)以加深理解。

呸。希望对您有所帮助!

---