用最小距离和将一组三维点映射到另一组

在我的头上,空间排序,然后模拟退火。

对空间进行网格划分,并将集合排序为空间单元格。

解决每个小区内的O(NM)问题,然后在小区小区内,等等,得到一个试配。

最后,运行大量模拟退火循环,其中您随机更改匹配,以便探索附近的空间。

这是一种启发式的方法,让您得到一个好的答案,尽管不一定是最好的,而且由于最初的网格排序,它应该是相当有效的。

解决这个问题的一种方法是将其视为经典的赋值问题: http://en.wikipedia.org/wiki/Assignment_problem

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

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

哪里 bigNumber 比你最长的距离大。

很明显你最终得到了一个二部图。然后,您将使用一种标准算法进行最大加权二部分匹配(Web上有很多资源,例如 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(n m max(n,m))算法,其中n和m是您的点集的大小。

虽然我对你的问题没有真正的答案,但我可以建议你研究以下主题。(我对此知之甚少,但以前在堆栈溢出时遇到过。)

• Nearest Neighbour Search
• k d-tree

希望这有点帮助。