4

パス圧縮を使用して UnionFind 構造アルゴリズムを実装しようとすると、(stackoverflow (hehe) ではなく) Find アルゴリズムに問題があります。

私はintの標準配列を持っていますが、配列はかなり大きくなる可能性があります-> 60.000.000要素までは正常に動作します。

私のユニオン関数は次のようになります。

public void unite(int p, int q) {
    if(p >= 0 && p < id.length && q >= 0 && q < id.length){
        if (isInSameSet(p, q)) return;
        id[find(p)] = find(q); 
        stevilo--;
    }
}

私の isInSameSet は次のようになります。

    public boolean isInSameSet(int p, int q) {
        if(p >= 0 && p < id.length && q >= 0 && q < id.length) 
            return find(p) == find(q);
        return false;
}

私は検索で反復的な方法を試しました:

    public int find(int i) {
        while (i != id[i]){
            id[i] = id[id[i]];
            i = id[i];              
        }       
    return i;
    }

および末尾再帰:

    public int find(int i) {    
        int p = id[i];
        if (i == p) {
          return i;
        }
        return id[i] = find(p);     
     }

私のコードで見逃したものはありますか? この種の問題に対する他のアプローチはありますか？

@edit: コンストラクターをコードに追加:

    public UnionFind(int N) {
        stevilo = N;
        id = new int[N];        
        for(int i = 0; i < N; i++){
            id[i] = i;
        }

@edit2（より良い説明と新しい発見）：60.000.000要素未満の場合、問題はstackoverflowになくなりました。これは、私の問題を解決するのに十分です。

私は次のようにテストユニオンを呼び出しています:

for(i=0;i<id.length-1;i++)
unite(i,i+1)

したがって、エンディングのペアは次のようになります。

0:1, 1:2, 2:3, 3:4,..

これは、手段のみをテストするための最も最適でないオプションの例にすぎません:)

次に、0 の代表がテーブルの最後の要素 (100 要素の場合は 99) であるかどうかを確認し、それが機能するようにします。

問題は、初期要素がそれぞれ独自の結合 (0:0、1:1、2:2、3:3) にある場合にのみ、私のアルゴリズムが機能することです。すでに別のユニオン (0:2、1:6、2:1、3:5、...) を設定している場合、テスト アルゴリズムが機能しなくなります。

私はそれを検索機能の問題に絞り込みました。おそらくパス圧縮に関係しています

id[i] = id[id[i]].
4

3 に答える 3

2

Union-Find データ構造には通常、2 つの異なる最適化が含まれます。1 つはパスの圧縮です。あなたはそれを持っています。

しかし、もう 1 つの最適化はユニオン中に行われます。この場合、2 つのルートのどちらを他方の子にするかを慎重に選択します。通常は、ランク別ユニオンまたはサイズ別ユニオンを使用します。この最適化により、スタック オーバーフローが発生するほどツリーが深くなることはありません。ただし、その最適化は unite 関数に欠けているようです。

于 2014-03-31T15:35:15.533 に答える
1

のアルゴリズムを書いたことがありますがUnionFind、その時間計算量は O(log*(n)) です。それは n の反復対数です。アルゴリズムは、ノードを接続し続けるときにツリーのパスを圧縮して効率を高めます。巨大な配列サイズに対して実際にテストしたことはありませんが、非常に効率的です。コードは次のとおりです。

public class UnionFind
{
  private int[] id;

  public UnionFind(int capacity)
  {
    id = new int[capacity];
    for (int i = 0; i < capacity; i++)
    {
      id[i] = i;
    }
  }

  public boolean isConnected(int p, int q)
  {
    return root(p) == root(q);
  }

  public void connect(int p, int q)
  {
    if (isConnected(p, q))
    {
      return;
    }

    id[root(p)] = root(q);
  }

  private int root(int p)
  {
    int temp = p;

    if (p != id[p] && id[id[p]] != id[p])
    {
      while (p != id[p])
      {
        p = id[p];
      }

      id[temp] = id[p];
    }

    return id[p];
  }
}
于 2014-03-31T15:45:19.120 に答える