algorithm - 将一组 3D 点映射到具有最小距离总和的另一组

Question

给定两组三维点，一组源点和一组目标点。每个集合上的点数是任意的(可能为零)。任务是为每个目标点分配一个或没有源点，以便所有距离的总和最小。如果源点多于目标点，则忽略额外的点。

这个问题有蛮力解法，但是由于点数可能很大，不可行。我听说这个问题在具有相同集合大小的 2D 中很容易，但遗憾的是这里没有给出这些先决条件。

我对近似解和精确解都很感兴趣。

编辑:哈哈，是的，我想这听起来确实像家庭作业。其实不然。我正在编写一个程序来接收大量汽车的位置，并试图将它们映射到各自的 parking 位。 :)

Answer 1

解决此问题的一种方法是将 is 视为经典分配问题:http://en.wikipedia.org/wiki/Assignment_problem

您将点视为图的顶点，边的权重是点之间的距离。因为最快的算法假定您正在寻找最大匹配(而不是像您的情况那样最小)，并且权重是非负的，所以您可以将权重重新定义为例如:

weight(A, B) = bigNumber- distance(A,B)

bigNumber 大于您的最长距离。

显然，您最终会得到一个二分图。然后你使用一种标准算法来进行最大加权二分匹配(网络上有很多资源，例如 http://valis.cs.uiuc.edu/~sariel/teach/courses/473/notes/27_matchings_notes.pdf 或维基百科的概述:http://en.wikipedia.org/wiki/Perfect_matching#Maximum_bipartite_matchings)这样你最终会得到一个 O(NM max(N, M)) 算法，其中 N 和 M 是点集的大小。