8

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

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

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

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

4

3 回答 3

3

您可以解决此问题的一种方法是将其视为经典分配问题: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 是你的集合的大小点。

于 2009-03-09T15:02:15.347 回答
1

尽管我对您的问题没有真正的答案,但我可以建议您研究以下主题。(我对此知之甚少,但之前在 Stack Overflow 上遇到过。)

希望这个对你有帮助。

于 2009-03-09T15:01:19.250 回答
1

在我的脑海中,空间排序,然后是模拟退火。

对空间进行网格化并将集合分类为空间单元格。

在每个单元格内求解 O(NM) 问题,然后在单元格邻域内求解,以此类推,以获得试验匹配。

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

这是启发式的,虽然不一定是最好的,但可以为您提供一个很好的答案,并且由于初始网格排序,它应该是相当有效的。

于 2009-03-10T11:44:06.767 回答