给定两组三维点，一个源集和一个目标集。每组上的点数是任意的（可能为零）。任务是为每个目标点分配一个或不分配一个源点，以使所有距离的总和最小。如果源点多于目标点，则忽略附加点。
这个问题有一个蛮力的解决方案，但是由于点的数量可能很大，所以不可行。我听说这个问题在具有相同大小的 2D 中很容易，但遗憾的是这里没有给出这些先决条件。
我对近似值和精确解都感兴趣。
编辑：哈哈，是的，我想这听起来确实像家庭作业。事实上，它不是。我正在编写一个程序来接收大量汽车的位置，并且我正在尝试将它们映射到它们各自的停车单元。:)
您可以解决此问题的一种方法是将其视为经典分配问题：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或 Wikipedia概述：http ://en.wikipedia.org/wiki/Perfect_matching#Maximum_bipartite_matchings ）这样你最终会得到一个 O(NM max(N,M)) 算法，其中 N 和 M 是你的集合的大小点。
在我的脑海中，空间排序，然后是模拟退火。
对空间进行网格化并将集合分类为空间单元格。
在每个单元格内求解 O(NM) 问题，然后在单元格邻域内求解，以此类推，以获得试验匹配。
最后，运行大量模拟退火循环，在其中随机改变匹配，以探索附近的空间。
这是启发式的，虽然不一定是最好的，但可以为您提供一个很好的答案，并且由于初始网格排序，它应该是相当有效的。