12

そのため、私は最も低い共通祖先アルゴリズムの実装を検討してきました。私は多くの異なるアルゴリズム（主にTrajanのソリューションのバリエーションまたはRMQのバリエーション）を調べました。

非二分木を使用しています。私のツリーはクエリ間で頻繁に変更されるため、前処理は必ずしも価値がありません。ツリーには、50〜75を超えるノードを含めることはできません。私が疑問に思っているのは、彼らのアルゴリズムをわざわざ使用するべきか、それとも自分のアルゴリズムに固執するべきかということです。

私のアルゴリズム

myLCA(node1, node2) {
    parentNode := [ ]
    while (node1!=NULL) {
         parentNode.push(node1)
         node1 := node1.parent
    }
     while (node2!=NULL) {
         for i in parentNode.size {
             if (parentNode(i) == node2) {
                 return node2; 
             }
         }
         node2 := node2.parent
     }

}
4

6 に答える 6

17

他の人が述べているように、あなたのアルゴリズムは現在二次式です。これは、50〜75ノードの小さなデータセットでは問題にならないかもしれませんが、いずれの場合も、各ノードのルートへの完全なパスを記録するだけで、セットやハッシュテーブルを使用せずに線形時間に変更するのは簡単です。ルートから戻って、最初の別のノードを探します。その場合、直前のノード（これら2つの異なるノードの共通の親）はLCAです。

linearLCA(node1, node2) {
    parentNode1 := [ ]
    while (node1!=NULL) {
         parentNode1.push(node1)
         node1 := node1.parent
    }
    parentNode2 := [ ]
    while (node2!=NULL) {
         parentNode2.push(node2)
         node2 := node2.parent
    }
    while (node1 == node2 && !isEmpty(parentNode1) && !isEmpty(parentNode2)) {
        oldNode := node1
        node1 := parentNode1.pop()
        node2 := parentNode2.pop()
    }
    if (node1 == node2) return node1    // One node is descended from the other
    else return oldNode                 // Neither is descended from the other
}

編集27/5/2012： 1つのノードが他のノードから派生している場合を処理します。そうしないとpop()、スタックが空になります。これを指摘してくれてありがとう。（私はまた、単一を追跡することで十分であることに気づきましたoldNode。）

于 2011-06-14T11:06:02.233 に答える
4

小さいツリーの場合、これ以上複雑なものを実装する必要はありません。時間計算量はツリーの高さで2乗されますが、ソリューションは良さそうです。Set（ほとんどの言語に組み込まれている）簡単に実装できる場合は、アルゴリズムを微調整して、

  1. 最初のノードからルートまでトラバースし、セット内のすべてのノードを収集します
  2. 2番目のノードからルートまでトラバースし、現在のノードがそのセットに存在するかどうかを確認します。もしそうなら、それは共通の祖先です。

また、このアルゴリズムは、ノードがそれ自体の祖先になることができることを前提としています。それ以外の場合は、アルゴリズムを少し調整する必要があります。この例を考えてみましょう。

A
|
B
|
C

BおよびCの最も低い共通の祖先を見つけようとすると、このアルゴリズムはBを報告します。これは、祖先の定義方法によっては真である場合とそうでない場合があります。

于 2011-06-14T02:48:21.043 に答える
3

どちらのアルゴリズムの詳細も検討せずに、このアルゴリズムの効率がアプリケーション全体にとってどれほど重要であるか、および別のアルゴリズムを実装するためにどれだけの労力が必要になるかを検討することをお勧めします。

このアルゴリズムは、アプリケーションの通常の（またはストレスのある）操作で何回実行されますか？ユーザーが必要以上に待機する原因になりますか？桁違いに異なる他のアルゴリズムは、あなたのアルゴリズムよりも高速ですか？（アルゴリズムに精通している人は、これについてより詳細な答えを与えることができます。）

かなりの結果が得られない限り、コードを少し最適化する価値はないと思います（一部の人々は、時期尚早の最適化がすべての悪の根源であると非常に強く感じています）

于 2011-06-14T02:49:10.673 に答える
2

アルゴリズムは2次式ですが、簡単に線形化できます。

parentNodeリストの代わりに、ハッシュテーブル（つまりセット）を使用するだけです。したがって、ノードが入っているかどうかのチェックは、の代わりにparentNodeなります。O(1)O(n)

于 2011-06-14T06:07:08.980 に答える
2

この問題に対して独自のアルゴリズムを実装する方法についてブログに投稿しましたが、任意の長さのノードのセットに拡張しました。あなたはそれをここで見つけることができます（それがどのように機能するかについての段階的なグラフィカルな説明とともに）

http://bio4j.com/blog/2012/02/finding-the-lowest-common-ancestor-of-a-set-of-ncbi-taxonomy-nodes-with-bio4j/

乾杯、

パブロ

于 2012-02-09T09:17:09.400 に答える
1

2つの要素を並べ替える1つの単純なソリューションがあり、最も低いものが左に、最も高いものが右になります。rootdef recurse（root）return nil if root.empty？if left <= root && right> = root return root elsif left <= root && right <= root recurse（root.left）else recurse（root.right）end

したがって、これは各トラバーサルをチェックします。平均および最悪のO（log n）時間とO（log

于 2012-07-07T05:45:43.577 に答える