6

私はこの質問を見て、次にTarjan の最小共通祖先アルゴリズムについて読んでいました。これまで、LCA アルゴリズムのアプリケーションに出くわしたことはありません。

そのような LCA アルゴリズムはどこで一般的に使用されていますか?

4

3 に答える 3

6

コンパイラでは、2 つの基本ブロックの LCA は計算を配置できる場所であるため、両方で使用できます。これは、一般的な部分式を削除したり、SSA 変換用の phi-node を挿入したりするのに役立つ場合があります。ただし、これらのアルゴリズムは十分に進化し、高度に最適化されているため、 SSAやPREなどの LCA 自体はわかりにくい場合があります。

于 2010-08-22T17:37:54.547 に答える
5

どこで使用されるかはわかりませんが、使用される可能性のあるアイデアがいくつかあります。

  • コンピュータ グラフィックス: 多くの場合、3D シーンは、ツリー構造を形成する立方体に分割されます。そのような 2 つの立方体に含まれるオブジェクトがある場合、LCA アルゴリズムは、より大きな立方体を含む最小のものを提供します。

  • 種とそれらの最も低い共通の祖先との間の関係を見つけるための属の分析

  • バージョン管理システムのマージ アルゴリズム

于 2010-08-22T17:34:02.247 に答える
-1

メタゲノミクスのコンテキストで、分類ツリーのこの問題 (任意の長さのノードのセットに拡張) に対して独自のアルゴリズムを実装する方法について、ブログ投稿を書きました。

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

乾杯、

パブロ

于 2012-02-09T09:12:16.037 に答える