Pie*_*Guy 11 c c++ algorithm math
给定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},{12,18},{0,0}
所需的输出是237.
这不是我的功课,我对不同的方法而不是蛮力很好奇.
小智 7
您似乎正在寻找最小重量完美匹配.
有一些算法可以利用这些是平面中的点的事实.本文:平面中的Mincost完美匹配有一个算法,并且还提到了一些以前的工作.
根据要求,这里是对图中最小加权完美匹配的"简单"算法的简要描述.这是Papadimitriou和Steiglitz撰写的" 组合优化,算法和复杂性 "一书中有关加权匹配的章节的简短摘要.
假设您获得了加权无向图G(具有偶数个节点).通过添加缺失边并为它们分配非常大的权重,可以将该图视为完整的加权图.
假设顶点标记为1到n,并且顶点i和j之间的边的权重是c(i,j).
我们有n(n-1)/ 2个变量x(i,j),如果i和j之间的边在匹配中,则表示G. x(i,j)= 1的匹配,x(i,j)如果不是,则= 0.
现在匹配问题可以写成线性规划问题:
最小化Sum c(i,j)*x(i,j)
受条件限制
和x(1,j)= 1,其中j的范围从1到n.
和x(2,j)= 1,其中j的范围从1到n....
和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)
和x(i,j)+ y(r)= s(r),对于i,j在S(r)中.
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节.
我之前提到的这本书值得一读(虽然可能有点干)但要深入了解.
唷.希望有所帮助!