以最小距离总和将一组 3D 点映射到另一组 3D 点

Question

给定两组三维点，源集和目标集。每组上的点数是任意的（可以为零）。任务是为每个目标点分配一个或不分配一个源点，以使所有距离的总和最小。如果源点多于目标点，则忽略附加点。

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

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

编辑：哈哈，是的，我想这听起来确实像家庭作业。事实上，事实并非如此。我正在编写一个程序，该程序接收大量汽车的位置，并尝试将它们映射到各自的停车位。:)

Answer 1

离开我的头顶，进行空间排序，然后进行模拟退火。

网格空间＆amp;将集合分类为空间单元格。

解决每个单元格内的O（NM）问题，然后解决单元格区域内的问题，以此类推，以获得试验匹配。

最后，运行大量的模拟退火循环，随机改变匹配，以便探索附近的空间。

这是启发式的，给你一个很好的答案，虽然不一定是最好的，并且由于最初的网格排序，它应该是相当有效的。

Answer 2

解决这个问题的一种方法是将待遇视为经典的分配问题： 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是您的点集的大小。

Answer 3

虽然我并没有真正回答您的问题，但我可以建议您研究以下主题。（我对此知之甚少，但之前在 Stack Overflow 上遇到过。）

• 最近邻搜索
• kD树

希望这个对你有帮助。