Java:设计问题 - 集合之间的最小对

Question

我有两套Animal对象。动物之间的距离是通过查看其特征的特定算法来定义的。我正在尝试设计一种方法来从两组(每组一个)中找到一对，以最小化距离。

我的一个想法:创建一个参数化 Tuple配对类 Animals 。创建 PriorityQueue用比较器来排序 Tuple<Animal>根据两个成员之间的距离。然后，从PriorityQueue中选择第一对.

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

如果Tuple是一个参数化类，如何在其上使用仅适用于 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 已被占用。看看它是如何工作的？

这就是我最终所做的。评论？

Answer 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)