c – 最小的一对 - 前端之家

给定2D平面中的2N点,您必须将它们分组为N对,使得所有对的点之间的距离的总和是最小可能值.期望的输出仅为和.

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

让我们考虑这个测试案例,如果2 * 5分是：
{} 20,20,
{40,20},
{10,10}
{2,2},
{240,6},
{12,12},
{100,120},
{6,48},18},
{0,0}

所需的输出为237.

这不是我的功课,我对不同的方法而不是暴力而感到好奇.

有一些算法可以利用这些事实,即这些点在一个平面上.本文：Mincost Perfect Matching in the Plane有一个算法,并提到了一些以前的工作.

根据要求,这里简要描述一个图中最小加权完全匹配的“简单”算法.这是本书“组合优化,算法和复杂性”一章中关于加权匹配章节的简要总结,由PapadimitrIoU& Steiglitz.

假设你被给予加权无向图G(偶数个节点).该图可以被认为是一个完整的加权图,通过添加缺失的边和赋予它们非常大的权重.

假设顶点被标记为1到n,并且顶点i和j之间的边缘的权重是c(i,j).

我们有n(n-1)/ 2个变量x(i,j),如果i和j之间的边缘在匹配中,则x(i,j)= 1,x(i,j) = 0如果不是.

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

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

以条件为准

Sum x(1,其中j的范围从1到n.

Sum x(2,其中j的范围从1到n.
.
.
.

Sum x(n,其中j的范围从1到n.

(Sum x(1,j)= 1基本上意味着我们正在精确地选择顶点标记为1的一个边缘.)

最后的条件是

x(i,j)> = 0

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

有一种称为Simplex方法的方法,可以解决这个线性规划问题,在多项式时间中给出变量数量的最优解.

现在,如果G是二分的,可以表明我们可以得到一个最优解,使得x(i,j)= 0或1.因此,通过求解这个二分图的线性规划问题,我们得到一组赋值每个x(i,每个都是0或1.我们现在可以通过选择其中x(i,j)= 1的那些边(i,j)来获得匹配.约束保证它将与体重最小

不幸的是,对于一般图(即x(i,j)为0或1),这不是真的.埃德蒙兹认为,这是因为图中存在奇怪的周期.

因此,除了上述的约束之外,埃德蒙兹还补充了附加约束,即在大小为2k 1(即,奇数大小)的顶点的任何子集中,匹配边的数量不大于k

枚举顶点的每个奇数子集,得到集合S(1),S(2),…,S(2 ^ n-n)的列表.使S(r)的大小为2 * s(r)1.

那么上述约束对于每一组S(r)

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

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

不幸的是,现在变量的数量已经变成指数级.因此,单纯形算法如果只是像这样运行就会导致指数时间算法.

为了达到这个目的,埃德蒙兹认为这个线性规划问题是双重的(我不会在这里详细介绍),并且表明在双重运行时的原始 – 双重算法只需要O(n ^ 4)步骤来达到解决方案,从而给出我们一个多项式时间算法！他通过表明在算法的任何步骤(他称之为花),y(r)中的O(n)至多O(n)是非零的.

我之前提到的这本书值得阅读(尽管可能有点干涩),以便更深入地了解.

唷.希望有帮助！

原文链接：https://www.f2er.com/c/116049.html

c – 最小的一对