3

Pythonで最小共通祖先を実装する最も簡単な方法は何ですか? 親へのポインターを持つ各ノードで表されるツリーがあり、2 つのノードが与えられた場合に最初の共通の祖先を見つけられるようにしたいと考えています。いくつかのアイデアを思いついたが、どれも特に魅力的ではなかった

  1. 各ノードにそのベースのリストを含め、結合を実行するには、最長の共通プレフィックスを見つけてから最後の要素を取ります。残念ながら、最長の共通プレフィックスを実行する組み込みの方法を知らないため、これには手動のループが必要です。

  2. 各ノードにそのベースのセットを含め、セットの交差を実行し、最大の要素を取ります。しかし、これには独自の比較演算子を定義する必要があり、それが機能するかどうかさえわかりません。

私は何をすべきか？パフォーマンスよりもシンプルさを優先するものを探しているので、複雑な処理を必要とするソリューションは出ていません。

編集：組み込みの方法はありませんが、zipを使用して1行で最長の共通プレフィックスを実行できるため、それでもかなり簡単です。

common = [x for x in zip(*baselists) if len(set(x)) == 1][-1]
4

6 に答える 6

6

ツリーを修正して深さを含めることができないという前提の下で、次のことができます。

ノードごとに、ルートに到達するまでツリーを上方向に再帰的にトラバースします。各親ノードで、ノードを に挿入しますlist。list_aこれにより、 とが得られるはずですlist_b。各リストの要素を比較して、最短のリストを反復処理します。一致しないものが見つかった場合、前のエントリが最大の親要素です。

于 2012-08-10T17:22:32.757 に答える
5

各ノードの深さ (ルートからの距離) を取得します。一方が他方よりも低い場合は、深さが等しくなるまで下のノードからツリーを上ります。次に、身元をチェックし、チェックが失敗するたびに各側を上に移動します。

これは、単一の while ループで実行できます。深さが等しい祖先を選択したら、次のようにします。

while (ancestorA !== ancestorB) {
    ancestorA = ancestorA.parent();
    ancestorB = ancestorB.parent();
}

while ループが終了するancestorAと、ancestorBそれぞれが共通の祖先になります。

これは非常に単純であるだけでなく、かなり高速である必要があります。

于 2012-08-10T17:03:33.410 に答える
2

Python には組み込みセットがあります。（疑似コード）の行に沿って何かを使用しないのはなぜですか：

a_ancestors = set()
while a:
  a_ancestors.add(a)
  a = a.parent

while b:
  if b in a_ancestors:
    return b
  b = b.parent

return None # <- can't reach that for a *tree* !!!

これにより、ノードaのすべての祖先 ( a自体を含む) の (順不同) セットが構築されます。

次に、もう一度、bのすべての祖先をループします。定義により、a の祖先である b の最初の祖先は、最初の共通の祖先になります。これはO(n) (空間と時間) で機能します

aとbの両方の先祖のセットを同時に収集することにより、(最終的にはスペースの占有を犠牲にして) プロセスを高速化できる可能性があります。共通のノードが見つかったらすぐに a を停止します。ブランチの 1 つが他のブランチより先にルートに到達したことに対処する必要があるため、コードは少し不自然です。

visited = set()
while a or b:
  if a:
    if a in visited:
      return a
    visited.add(a)
    a = a.parent

  if b:
    if b in visited:
      return b
    visited.add(b)
    b = b.parent

return None # <- can't reach that for a *tree* !!!
于 2016-03-10T21:35:22.380 に答える
0

どちらの場合も親ノードへのポインタがすでにあるので、そうしないでください:( weirdcanadaが言ったことと似ていますが...）

各ノードの親のリストを作成し、各段階でリストを順番に作成します。だからlist_a、list_bあなたが高くなるにつれて成長します。各リストの最後に追加されたアイテムを他のアイテムと比較します。list_aのアイテムがlist_bのアイテムと一致するとすぐに、共通の祖先が最も低くなります。

while (parent_a not in list_b) or (parent_b not in list_a):
    ...

ルートまでチェーンを再構築する必要はありません。いずれの場合も、各親を順番に（順方向または逆方向に）チェックする必要があります。

于 2012-08-11T07:33:47.183 に答える
0

親のコレクションを維持するには、= でハッシュ マップを使用することをお勧めします。この場合、親リストでの検索に logn を費やさないためです。したがって、各反復でこのマップを確認し、現在のノードの親がマップに既に存在する場合、この親が結果になります。最悪のシナリオでは O(n) になりますが、同時に両方のノードの分析を開始すると、より速く見つけることができる場合があります。

于 2012-08-10T22:02:48.683 に答える
0

それはあなたのツリーとそれに含まれるオブジェクトの数に依存すると思います。数がメモリ的に妥当な場合 (おそらく数百万ノード未満ですが、それは私の勝手な推測です)、私はあなたの提案 #2 を使用します。セットでは、各ベースの文字列表現を保持するだけなので、組み込みの比較が機能します。非常に高速である必要があり、わずか数行のコードで実装できると思います。文字列表現が実用的でない場合、またはオブジェクト自体が必要で、すべてのオブジェクトのマスター dict を実装できない場合は、ノード オブジェクトで比較メソッドを定義するだけです (思い出すとeqとneq )。

于 2012-08-10T17:47:10.693 に答える