問題タブ [lowest-common-ancestor]

次のような有向非巡回グラフを想像してください。

• "A" はルートです (ルートは常に 1 つだけ存在します)。
• 各ノードはその親を知っています
• ノード名は任意です - それらから何も推測できません
• 別の情報源から、ノードが A から G の順序でツリーに追加されたことがわかります (たとえば、バージョン管理システムでのコミットです)。

任意の 2 つのノードの最小共通祖先 (LCA) を決定するためにどのアルゴリズムを使用できますか。たとえば、次の共通祖先は次のとおりです。

• B と E は B
• D と F は B

ノート：

• ルートから特定のノードへの単一のパスがあるとは限りません (たとえば、「G」には 2 つのパスがあります)。そのため、ルートから 2 つのノードへのパスを単純にたどって、最後の等しい要素を探すことはできません。
• ツリー、特にバイナリ ツリーの LCA アルゴリズムを見つけましたが、ノードは複数の親を持つことができるため (つまり、これはツリーではない)、ここでは適用されません。

、派生元、派生元A、B派生元の 4 つのクラスがあるとします。(だから私は常に単一の継承を持っています。) Python では、任意の 2 つの (そのようなインスタンスの) クラスの最も近い共通の祖先を決定する最良の方法は何ですか? 具体的には、 、、およびの関数が必要です。ACADCclcoancl(X,Y)clcoancl(A, B) == Aclcoancl(B, C) == Aclcoancl(C, D) == C

与えられた: X -> B -> C -> D -> ChildjQuery に、セレクターに一致する最初のノードまでのすべての祖先を返すようにします。

jQueryは とは対照的に$(Child).parents(X)のみを返します。このアレイを手動で構築するために使用できることはわかっていますが、より良い方法はありますか?XX, B, C, Dparent()

まず第一に、この問題を扱っているスレッドが他にもたくさんあることを知っています。私が知りたいのは、私のソリューションを CodeEval に送信したときに、なぜ私のソリューションが 100% ランク付けされていないように見えるかということです。ランキングは70%にとどまっています。ローカル環境でテストすると、私が投げたすべてのテスト状況で問題なく動作します。

私のソリューションが最も効率的ではないことはわかっています。私がやろうとしたことは、私が理解できる解決策を自分で考え出すことでした. 最後に他社と比較してみます。しかし、その前に、誰かが私がここで間違っていることを説明してもらえますか?

ルートのないツリーに LCA を実装しようとしています。ツリー (循環のない接続された無向グラフ) と、いくつかのルートと 2 つの頂点に対する LCA に関する一連のクエリを指定しました。特定のクエリごとにルートが異なる可能性があるため、最初に任意のルートのツリーを前処理するアルゴリズムを使用することはできません。

これまでのところ、DFS を使用して両方の頂点からルートへのパスを見つけようとしましたが、分岐する場所を確認しましたが、やや遅い (O(nq)、q はクエリの数)。

クエリの準線形複雑性を持たせるためにツリーを前処理する方法について何か提案はありますか?

私の問題は、txt ファイルのリストから作成される一般的なツリーの LCA を見つけることです。最も効率的な実装を探しています。データの形式は次のとおりです: Id、info、ParentId

データはいかなる方法でもソートされません。ツリーを作ろうと思ったのですが、最低でもO(nlogn)かかります。対数ベースは2ではありませんが、私が推測する子供の平均数に依存します。

代わりに、ノードをハッシュテーブルに格納すると、LCA を見つける方が O (nlogn) よりも優れています。右？宛先ノードの各親について、ソース ノードがアクセスしたかどうかを確認する必要があります (ソース ノードからルートまでを開始し、途中のすべての親をアクセス済みとしてマークすると仮定します)。 （ログイン）。親をチェックするだけなので、O(nlogn) よりも優れています。

もっと良いアイデアはありますか？

Say we have this simple ontology as a toy example:

I now receive evidence about a certain object x (for example, "x is a boat", "x is a car") and want to make a statement on what I know about this object.

A sensible approach would be to use my tree and calculate the lowest common ancestor (LCA) of my evidence, and return that as a result. In my example (car and boat), this would result in vehicle.

Let's now say that I have evidence that an object y is a car and a vehicle. The LCA of these is vehicle. In this case, however, I want the result to be car, since the evidence of y being a vehicle does not contradict it being a car.

I implemented this alternative LCA algorithm (by ignoring evidence that's on the path to root of other evidence), but have not found anything about such an approach on the internet. Is there a name for the alternative algorithm I used?

インオーダーおよびポストオーダー トラバーサルによる LCA は、簡単に実装でき、理解できました。

ただし、再帰的なボトムアップ アプローチがあります。

私はオンラインでコードを見ましたが、1行理解できませんでした:

コードは次のとおりです。

val1 と val2 は、LCA を見つける必要がある 2 つのノードの値です。

最後の行は私が立ち往生しているところです。

誰かがこれを説明できますか？

ありがとうございました。

私は、この質問が何度も聞かれたことを知っています。バイナリ ツリー (BST ではない) の LCA について明確にする必要があります。指定されたツリーから 2 つのノード (3,11) の LCA を見つけようとしている場合:

コードは (3,11) に対して 11 を返します。

ここで私は混乱しています。それは正しいはずです。間違っている場合は修正してください。ここで混乱していますか？またはそれはLCAの仕組みですか？