1

私は2セットのAnimalオブジェクトを持っています。動物間の距離は、その特性を調べる特定のアルゴリズムを使用して定義されます。距離を最小化する 2 つのセット (それぞれから 1 つ) からペアを見つける方法を設計しようとしています。

私が持っていたアイデアの 1 つは、パラメーター化Tupleされたクラスを作成してペアを組むことAnimalsです。2 つのメンバー間の距離に従ってPriorityQueue並べ替えるには、コンパレータを使用して を作成します。Tuple<Animal>次に、 から最初のペアを選択しPriorityQueueます。

これは良いデザインですか、それとも無駄ですか？m と n が各コレクションのサイズである場合、O(m+n) 時間で実行されると思います。

パラメータ化されたクラスの場合Tuple、でのみ機能する Comparator を使用するとどのように機能しAnimalますか?

findMinimalPairこの方法を使用して、オブジェクトのグラフの距離を最小化するスパニング ツリーを作成したいと考えていAnimalます。からペアを継続的にポップしPriorityQueue、各ペアに各コレクションのメンバーが 1 つずつ含まれていることを確認して、これを行ったらどうなるでしょうか。

これが基本的な例です。距離は次のとおりです。

     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)) です - 優先キューを使用しても (O で mn 個の挿入があります) (それぞれの log(mn)) の複雑さ)。

編集

上記のソリューションでエラーが発生しました。最小のペアを見つけたいだけの場合、すべてのペアで 1 つのパスが必要なため、実際の複雑さは O(mn) です。最小スパニング ツリーを取得するために距離で並べ替えられたすべてのペアのリストが必要な場合は、O(mn*log(mn)) です。いずれにせよ、それは O(m+n) ではありません

于 2009-11-03T20:18:08.630 に答える
0

私の提案は、uがO（n + m）ではなくO（nm）を与えるタプルを使用することです。次に、バケットソートアルゴリズムを使用します。バケットソートでは、各バケットがタプルになります。したがって、uは問題に対してO（nm）を取得します。（私があなたの問題について理解したことから、uはバケットソートを使用できます。そうでない場合、uはO（nlogn）アルゴリズムを使用する必要があります）

于 2009-11-03T20:24:55.130 に答える
0

セット 1 とセット 2 の間で考えられるすべてのタプル間の距離を見つけたい場合は、ネストされたループに行き詰まり、O(m*n) になる可能性があると思います。O(m+n) を得る方法はないと思います。

私の記憶が正しければ、最小全域木を見つける前に完成したグラフが必要です。グラフには O(V^2) 個のエッジがあるようです (動物の各ペアの間に距離があるため)。したがって、プリムのアルゴリズムを使用して最小スパニング ツリーを見つける場合は、フィボナッチ ヒープと隣接リストを使用することをお勧めします。 (つまり、O(E + V log(V)))。

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

于 2009-11-03T21:02:29.033 に答える