木の中心点？

Question

ルート付き順序付けツリーがあるとします。各ノードには、リンクされた子リストがあります。 P [i]はノードiと他のすべてのノードとの距離の和である。最悪の場合にはO（n）時間のコストがかかるツリーの最小P [i]（複数のP [i]が等しいかもしれない）の1つを見つけることができるアルゴリズムはありますか？

Answer 1

ここにいくつかのO（N）コードがあります。この例では、グラフ{0：[1,2,3]、1：[4,5]、2：[6]を使用します。

これを楽しくコーディングしました。下のグラフでは、中心はP [i]の値が9のノード0であることがわかります.i-> P [i]からのマッピングは{0：9,1：10,2：12,3：14、 4：15、5：15、6：17}

nodes={0:[1,2,3],1:[4,5],2:[6]} 
PB={} 
NB={} 
def below(i): 
    if i not in nodes: 
     PB[i]=0 
     NB[i]=1 
     return 0,1 
    tot_nodes_below=0 
    tot_paths_below=0 
    for node in nodes[i]: 
     paths_below,nodes_below=below(node) 
     tot_nodes_below+=nodes_below 
     tot_paths_below+=paths_below 
    tot_paths_below+=tot_nodes_below 
    tot_nodes_below+=1 
    PB[i]=tot_paths_below 
    NB[i]=tot_nodes_below 
    return tot_paths_below,tot_nodes_below 

P={0:below(0)[0]} 
def fill_P(i): 
    for node in nodes[i]: 
     P[node]=P[i]+7-2*NB[node] #7 is the number of nodes 
     if node in nodes: 
      fill_P(node) 
fill_P(0) 

_min=min(P.values()) 
answers=[k for k in P if P[k]==_min] 
print answers 
"[0]" 

説明： このコードはO（N）（？iは右考える）

基本的に接続し、各親ノードを示し=辞書ノードれますその子ノード。

T [i]を「ツリーi」とします。これをノードiから始まるサブツリーとして定義する。

ここで、NB [i]はノード数です（例：T [2] = 2：6、T [0]はツリー全体ですが、T [1]は1：[4,5] T [i]内にある。

NB = {0：7,1：3,2：2,3：1,4：1,5：1,6：1}

PB [i]は、ノードの距離の和でありますT [i]内のiから。 （PB [i]は、T [0]の代わりにT [i]だけを見ていることを除いて、基本的にP [i]となるであろう。

PB = {0：9,1：2,2：1,3 PB [0] = 9として、T [0]に0になる9つのパスがあるのでPB [0] = 9を参照する。PB [6] = 0をNB [0 ] = 1など

だから、実際に我々は、再帰的なO（N）が必要PBとNBを構築するための機能 "（I）の下に"。

（I）以下では、ルートノードから始まり、ダウンそのように動作しますノードが子ノードを持たない場合は、PB [i] = 0、NB [i]を再帰の基本ケースとする。 i] = 1。

子ノードを持つノードでPB [i]とNB [i]を計算するには、再帰式を使用します。 ノードiに子ノードx1..xjを、NB [i] = 1 + sum（NB [x]）とします。

PB [i]を処理する同様の再帰式があります。 NB [i]を追加する理由は、各ノードがサブツリーT [x]から得るために余分な距離1を移動しなければならないからである。ノードiに送信する。

以下、当社の機能は、（i）NBとPBを埋めた後、我々は

fill_P（i）は、単にこれを行うにNBとPBを使用していますP.

を見つけるためにこれら二つの結果を使用することができます。

ノードiとノードjが互いに近くにある場合、P [i]がP [j]の値に近いという考えがあります。

実際、NB [1]、PB [1]、P [0]を使ってP [1]を解くことができます。

これはP [1] = P [0] + 7-2 * NB [1] となります（PBの結果を使用する必要はありませんでしたが、PBは最初のP [0] ]値）。 なぜこの数式が真であるかを知るには、なぜP [1]がP [0]に等しくないのか考えてみてください。それは木の絵を持つのに役立ちます。ノード1を削除することで、ツリーを2つに分割できます。これで、ツリーの左側（ノード0は含まれません）とツリーの右側（ノード0を含む）が得られます。ツリーの左側はちょうどT [1]であり、これに対して結果NB [1]があることに注意してください。 P [1]は、T [1]移動距離1未満のノードからのすべての経路を除いてP [0]と同じである。 T [1]にないノードからのすべての経路はさらに1回進む（ノード0を通ってノード1に到達する）。パスの数は、単にNB [1]と7-NB [1]です。 P [1] = P [0] +（7-NB [1]） - NB [1]これは私たちが必要とする公式を与える。

ここで、P [0]とP [1]に正しいP値があります。ノード1またはノード0の任意の子の値を計算することができます。fill_Pはこの式を適用する各子ノードを通過し、結果Pが残っています。最小値を見つけるためにPを繰り返し実行するだけです。

うまくいけば、今これはうれしいことです。

Answer 2

私はあなたが時間の中のすべてのノードO（n）について計算することができると思います。もちろん、内部ノードはP [i]の小さいものになりがちです。この後、最小のP [i]を見つけることは追加のO（n）であるので、合計はO（n）である。

ノード間でメッセージを送信することを考えてみましょう。任意のノードから開始します。ルートは任意のノードです。そのノードの各ネイバーに、ノードと全長に関する情報の要求を送信します。各ネイバーから、そのネイバーをルートとするサブツリー内のノードの数とそのサブツリー内のすべてのノードの合計距離をそのネイバーに与えるメッセージを受信します。

ルートからP [i]を取り出し、その隣にあるツリーを除くすべてのツリーのルートにノード数と合計距離を示すメッセージを送信します。

発信者でない各ノードで、要求で送信したものを除き、すべての近隣ノードに同様の要求として最初のメッセージを伝播します。ノードの数を合計します。各距離には、それに関連付けられたノードの数と、返信で送信した近隣への距離との積を加えます。これらの合計を合計して、元の要求に応答を返します。

あなたのサブツリー以外のツリー全体の距離と数の合計を与えるメッセージを元に戻すと、あなたのP [i]とその合計を計算するために送り返したメッセージの情報と組み合わせます。クエリメッセージを送信したノードに送り返すのと同じメッセージです。

これは、すべてのノードでP [i]を計算することになります。ノード間の各リンクは、少数の一定数のメッセージしか見ることができません。各メッセージに必要な作業量はわずかです（一部の小計はグループ全体として計算する必要があります）。したがって、コストはO（n）です。

Answer 3

各ノードは、そのノードから最も遠いノードまでの距離を見つける必要があります。合計ではありません。そのような距離が最も短いものは木の「中心」になります。
テイク{R：：（A）、（B、C）、C：合計を使用しているときにhereとhere

[編集]可能な不完全な（またはより悪い）の回答を見ることができるアルゴリズムについては

（D）}次のように使用すると、和を得る：
R - 8
から5
B - 8
C - 6
D - 9
明確中心点

としてaを与えるただし'伝統的な方法：
Rdの3
広告2
BD 3
CR | B 2
のdR | Bの中心点

これは不完全答えをもたらす和を使用して、少なくとも1つの場合を示しているようにaとcを与える3
。 sums-methodでが正しくない場合は、という回答が返されます。