4

今日、このスライドの 13 ページのために、Kruskal 最小スパニング ツリー アルゴリズムについて誰かと議論しました。

プレゼンテーションの著者は、(二重) リンク リストを使用して素集合を実装すると、MakeとFindのパフォーマンスはそれぞれ O (1)とO(1 )になると述べています。Union(u,v)操作の時間はmin(nu,nv)です。ここで、nuとnvは u と v を格納するセットのサイズです。

セットの実表現へのポインターを含むロケーターを指す各メンバーの表現ポインターを作成することにより、 Union(u,v)がO(1)になる時間を改善できると述べました。

Java では、データ構造は次のようになります。

class DisjointSet {
    LinkedList<Vertex> list = new LinkedList<Vertex>(); // for holding the members, we might need it for print

    static Member makeSet(Vertex v) {
        Member m = new Member();

        DisjointSet set = new DisjointSet();
        m.set = set;
        set.list.add(m);

        m.vertex = v;

        Locator loc = new Locator();
        loc.representation = m;
        m.locator = loc;

        return m;
    }
}

class Member {
    DisjointSet set;
    Locator locator;
    Vertex vertex;

    Member find() {
        return locator.representation;
    }

    void union(Member u, Member v) { // assume nv is less than nu
        u.set.list.append(v.set.list); // hypothetical method, append a list in O(1)
        v.set = u.set;
        v.locator.representation = u.locator.representation;
    }

}

class Locator {
    Member representation;
}

ミニマルなコードで申し訳ありません。この方法で作成できる場合、互いに素な集合操作 ( Make,Find,Union )ごとの実行時間はO(1)になります。しかし、私が話し合った人は改善を見ることができません。これについてあなたの意見を知りたいです。

また、さまざまな実装における Find/Union の最速のパフォーマンスは? 私はデータ構造の専門家ではありませんが、インターネットをざっと見てみると、これを行う一定時間のデータ構造やアルゴリズムがないことがわかりました。

4

2 に答える 2

4

私の直感はあなたの同僚と一致しています。あなたは言う：

u.set.list.append(v.set.list); // hypothetical method, append a list in O(1)

あなたの意図は、結合が追加を介して行われることであるように見えます。ただし、ユニオンを実装するには、結果がセットになるように重複を削除する必要があります。したがって、たとえば、固定セットサイズの O(1) アルゴリズムを見ることができます...

Int32 set1;
Int32 set2;

Int32 unionSets1And2 = set1 | set2;

しかし、それは私をだましているように思います。Nの一般的なケースでこれを行っている場合、何らかの形式の反復（またはハッシュルックアップ）を回避する方法がわかりません。そして、それはO（n）（またはせいぜいO（log n））になります。

参考までに: あなたのコードをたどるのに苦労しました。makeSet では、関数を決してエスケープしないローカル Locator を構築します。何もしていないように見えます。そして、あなたの意図が追加にあるのかは明らかではありません。あなたのアプローチを編集して詳しく説明したい場合があります。

于 2010-08-14T22:18:36.903 に答える
3

Tarjan のバージョンの Union-Find 構造(パス圧縮とランク加重結合を使用) を使用すると、一連のm 個の検索と(n-1) 個の混合結合は O(m.α(m,n)) になります。ここで α (m,n) は、 mとnのすべての実用的な値に対して値 4 を持つアッカーマン関数の逆関数です。つまり、これは基本的に、Union-Find が定数操作を償却する最悪のケースであることを意味しますが、完全ではありません。

私の知る限り、理論上の複雑さを改善することは不可能ですが、改善によって実際の効率は向上しています。

言語理論で使用されるような素集合の特殊なケースでは、線形 (つまり、O(1) 内のすべて) の適応が可能であることが示されています。一般問題に訳します。スペクトルの一方で、やや類似した核となるアイデアが、最小スパニング ツリーの O(n) アルゴリズム (シャゼルのアルゴリズム) を作成するために、大きな成功と創意工夫で使用されてきました。

したがって、あなたのコードは正しくありません。エラーはMoronが指摘したものです.2つのセットの和集合を作成すると、各リストのリードの「表現」のみが更新され、他のすべての要素は更新されません.同時に、検索関数ですべての要素がその表現を直接知っています。

于 2010-08-14T22:40:07.407 に答える