1

coursera のクラスを使用してアルゴリズムを調べてきました。最初の講義の 1 つで、Quick Union Weighted が議論されています。私はそれが何をするかを理解し、彼らのコードを使用してテストし、小さなテストを書きました。

すべてが明確ですが、1 つの点があります。2 つのオブジェクトの結合を作成すると、最小のツリーを持つオブジェクトが最大のツリーに追加されます。同時に、どのツリーが大きいかを決定するために使用される別の配列で、大きい方のツリーのサイズが小さい方のツリーのサイズで増分されます。配列はすべてのインデックスに対して値 1 で開始されるため (基本的に、それ自体のすべてのノードは 1 つのオブジェクトのツリーです)、このインデックスの値が 1 のままではなく 0 に設定されないのはなぜですか?

これを説明するために：

// Quick Union Weighted
ID: 0 1 2 3 4 5 6 7 8 9 
SZ: 1 1 1 1 1 1 1 1 1 1 

quw.union(2, 4);
ID: 0 1 2 3 2 5 6 7 8 9 
SZ: 1 1 2 1 1 1 1 1 1 1 

quw.union(5, 4);
ID: 0 1 2 3 2 2 6 7 8 9 
SZ: 1 1 3 1 1 1 1 1 1 1 

quw.union(2, 7);
ID: 0 1 2 3 2 2 6 2 8 9 
SZ: 1 1 4 1 1 1 1 1 1 1 

// Whereas I would've expected to end up with this 
// to point out that the index is empty. 
SZ: 1 1 4 1 0 0 1 0 1 1

マージされたインデックスのサイズが 0 ではなく 1 になるのはなぜですか? ここでテストするコードを見つけることができます。実装は講師が提供する例と同じであることに注意してください。そのため、私のコードが正しいと仮定しています。

4

1 に答える 1

1

これは、ノード自体もサイズ 1 であり、子を持たないためだと思います。ただし、子を持つことはできます。私は実際にはQuick-Union Weightedに精通していませんが、他のユニオン検索アルゴリズムに少し似ている場合は、たとえば次のことができます

quw.union(0, 1);
ID: 0 0 2 3 2 2 6 2 8 9 
SZ: 1 1 4 1 1 1 1 1 1 1

quw.union(0, 2);
ID: 2 2 2 3 2 2 6 2 8 9 
SZ: 2 1 6 1 1 1 1 1 1 1

これで 0 と 1 がマージされ、0 から始まるツリー全体が 2 と再びマージされ、0 から始まるサブツリーのサイズは 2 のままになります。

私が言ったように、Quick-Union Weighted でそれが可能かどうかはわかりませんが、「1」の理由は、それ自体もサイズ 1 であるためです。

于 2013-02-06T11:54:11.480 に答える