4

要素 [0 からN - 1]を持つ基本的な配列があります。各要素は、配列の前の場所を常に指すインデックスを持つ構造体です。

ある時点で、はるかに大規模なアルゴリズムの一部として、ノードXとそれ以降のノードの間で特定のCの最下位共通祖先を見つけたいと考えています。

int LCA(a, b) {
    while (a != b) {
        if (a > b) {
            a = nodes[a].parent;
        } else {
            b = nodes[b].parent;
        }
    }
    return a;
}

for (y = x + 1; y < n; ++y) {
    if (LCA(x, y) == c) {
        //other code
    }
}

上記のコードは実際には疑似コードです。使用時にルックアップ テーブルを生成することで、LCA() のパフォーマンスをわずかに改善することができました。このようなもの：

int LCA(a, b) {
    if (lookup[a, b]) {
        return lookup[a, b];
    }
    oa = a; ob = b;
    while (a != b) {
        if (a > b) {
            a = nodes[a].parent;
        } else {
            b = nodes[b].parent;
        }
    }
    lookup[oa, ob] = a;
    lookup[ob, oa] = a;
    return a;
}

何らかの特殊化された LCA() 関数を作成する方法がある可能性が高いことはわかっています。つまり、上記のすべてのコードを何らかの方法で置き換えて特殊化することで、かなり高速になります。でも、面白いことを思いつきませんでした。

if を見てCとYの間の LCA チェックを簡単に実行できるかどうかを確認しようとしましLCA(c, y) == LCA(x, y)たが、もちろん正確ではありませんでした。

要約すると、 Xは常にYより小さくなります。Cは常にX (したがってY )より小さくなります。親は常に子よりも低いインデックスになります (したがって、順序付けられます)。

深さを知っているノードはまったく役に立ちますか?

このコードは、合計で約 4 分かかるアルゴリズム全体の CPU 時間の 80% を占めています。これに対する解決策は、アルゴリズム全体を簡単に改善します。ありがとう！

4

1 に答える 1

4

のLCAとは、ツリーのオイラー ツアー(*) でのの出現と の出現の間の最小の高さを持つノードになりxます。これを時間内に見つけるには、この方法を使用してRMQ 問題を解決する必要があります。yxyO(1)

(*): これを機能させるには、ツアーを少し変更する必要があります。配列に戻る (子への再帰呼び出しから戻る) たびに、配列に値を追加する必要もあります。wiki ツリーの場合、次のようになります。

1 2 3 4 5 6 7 8 9 10 11
1 2 6 2 4 2 1 3 1 5  1

葉を 2 回表示しても意味がないことに注意してください (正確性には影響しませんが)。

したがって、たとえば、RMQ(2, 5)これらのうち最小の高さを持つノードになります。

2 3 4 5 6 7 8 9 10
2 6 2 4 2 1 3 1 5

これはノード1です。

これは、取得できる唯一の有効な間隔ではありません。の最後の出現を取ることも有効です2:

6 7 8 9 10
2 1 3 1 5

これも として返さ1れますLCA。

LCAこのようにして、前処理に費やされる直線的な時間で一定の時間内にクエリに答えることができます。

于 2013-09-25T21:10:53.030 に答える