1

我有两组Animal对象。动物之间的距离是使用一种特定的算法来定义的，该算法着眼于它们的特征。我正在尝试设计一种方法来从两组（每个一组）中找到最小化距离的对。

我有一个想法：创建一个参数化Tuple类来配对Animals. PriorityQueue使用比较器创建一个以Tuple<Animal>根据两个成员之间的距离进行排序。然后，从PriorityQueue.

这是好的设计，还是浪费？我相信它会在 O(m+n) 时间内运行，其中 m 和 n 是每个集合的大小。

如果Tuple是一个参数化类，那么在其上使用仅适用于的 Comparator 将如何工作Animal？

我想使用这种findMinimalPair方法来创建一个生成树，以最小化Animal对象图的距离。如果我通过不断地从 中弹出对来做到这一点PriorityQueue，检查以确保每对仍然包含每个集合的一个成员，该怎么办？

这是一个基本的例子。以下是距离：

     A0     A1     A2     A3
A0   0      20     33     8
A1   20     0      102    73
A2   33     102    0      6
A3   8      73     6      99

假设集合是：

A0

A1、A2、A3

这是元组的排序顺序，按距离：

(A0, A3) - 8 
(A0, A1) - 20 
(A0, A2) - 33

所以我们看到 A3 是最接近的。然后将 A3 移动到第一个集合中：

A0, A3

A1, A2

再次，我们检查最小对：

(A3, A2) - 6
(A0, A1) - 20 
(A0, A2) - 33
(A3, A1) - 73

现在A2被拿走了。看看它怎么运作？

这就是我最终做的。注释？

4

3 回答 3

1

实际上，您需要创建 m*n 元组才能拥有所有可能的元组，这将花费 O(mn)。您需要对最少占用 O(mn*log(mn)) 的元组列表进行排序，因此复杂度为 O(mn*log(mn)) - 即使使用优先级队列（您将有 mn 插入，O （log（mn））每个复杂度）。

编辑

刚刚在上述解决方案中看到了一个错误 - 如果您只想找到最小的对，实际复杂度是 O(mn)，因为您需要在所有对上都有一条路径。如果你想要一个按距离排序的所有对的列表以获得最小生成树，那么它是 O(mn*log(mn))。在任何情况下，它都不是 O(m+n)

于 2009-11-03T20:18:08.630 回答
0

如果您想找到集合 1 和集合 2 之间所有可能的元组之间的距离，我认为您可能会陷入嵌套循环，导致 O(m*n)。我认为没有任何方法可以获得 O(m+n)。

如果我没记错的话，你需要一个完整的图表才能找到它的最小生成树。看起来该图将具有 O(V^2) 边（因为每对动物之间存在距离），因此如果您使用 Prim 算法来查找最小生成树，您可能需要使用 Fibonacci 堆和邻接表（即 O(E + V log(V))）。

http://en.wikipedia.org/wiki/Prim%27s_algorithm

于 2009-11-03T21:02:29.033 回答
0

我的建议是让你使用会给你 O(nm) （而不是 O(n+m)）的元组。然后使用桶排序算法桶排序，其中每个桶将是一个元组..所以你会在你的问题上得到 O(nm)。（根据我对您问题的理解，您可以使用桶排序，否则您将不得不使用 O(nlogn) 算法）

于 2009-11-03T20:24:55.130 回答