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

f8rj6qna  于 2021-06-30  发布在  Java
关注(0)|答案(3)|浏览(336)

我有两套 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被拿走了。看看它是怎么工作的?
这就是我最后要做的。评论?

t2a7ltrp

t2a7ltrp1#

实际上,为了得到所有可能的元组,需要创建mn元组,这需要o(mn)。您需要对元组列表进行排序,这些元组的最小值为o(mnlog(mn)),因此复杂性为o(mnlog(mn))——即使使用优先级队列(您将有mn个插入,每个插入都有o(log(mn))复杂性)。
编辑
刚才在上面的解决方案中看到一个错误-如果您只想找到最小的对,那么实际的复杂性是o(mn),因为您需要所有对上的一条路径。如果你想有一个按距离排序的所有对的列表,以便得到最小生成树,那么它就是o(mn
log(mn))。在任何情况下,它都不是o(m+n)

2nc8po8w

2nc8po8w2#

我的建议是使用元组,元组会给出o(n.m)(而不是o(n+m))。然后使用bucket sort算法bucket sort,其中每个bucket都是一个元组。。所以你会得到o(n.m)对你的问题(根据我对你的问题的理解,你可以使用bucket sort,否则你将不得不使用o(nlogn)算法)

unguejic

unguejic3#

如果你想找出集合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

相关问题