Centrum w drzewo (w minimalnej sumy odległości sensie)

Question

Mój problem jest następujący:

Biorąc pod drzewem (V, E), znaleźć węzła centrum v takie, że suma {W, V} [ dist (v, w)] jest minimalne, gdzie dist (v, w) jest liczbą krawędzi najkrótszej ścieżki od v do w. Algorytm powinien działać w czasie O (n) (n oznacza liczbę węzłów w drzewie).

Pytania here i here również wymagają centralnego węzła, ale definiują go inaczej.

Nie rygorystycznie przechodziłem przez kolejne etapy, ale uważam, że rozwiązanie mojego problemu powinno być podobne do rozwiązania this problem.

Jednak zdecydowałem, że powinienem podzielić się moim problemem ze społecznością, ponieważ zabrało mi to trochę czasu na nawigację do the link, która jednak nie odpowiada bezpośrednio na pytanie.

Answer 1

wymyśliłem tego rozwiązania:

1) Należy wybrać dowolny węzeł jako korzeń r, tworzą drzewo. Dla każdego poddrzewa w tym drzewie obliczyć liczbę węzłów w poddrzewie (liście to drzewa z jednym węzłem).

Jako przykład tego drzewa

  1 
     /| \ 
     2 3 4 
    /\  \ 
    5 6  7 
     /\ 
     8 9  

wynik byłby

  9 
     /| \ 
     5 1 2 
    /\  \ 
    1 3  1 
     /\ 
     1 1  

2) Oblicz sumę odległości do tego wybranego korzenia. Na przykład, jeśli wybierzesz wierzchołek 1 jako korzeń, suma odległości wynosi 0 + 1 + 1 + 1 + 2 + 2 + 2 + 3 + 3 = 15

3) Przemierzaj drzewo w depth-first-search sposób. Na przykład, zaczynając od wierzchołka 1, przechodzimy do wierzchołka 4. Obserwujemy, że dla 7 węzłów (1,2,3,5,6,8,9), idziemy dalej o 1 (dodać 7 = 9-2 do wynik), dla pozostałych 2 (4,7) zbliżamy się o 1 (odjąć 2). Daje to sumę odległości równą 15+ (9-2) -2 = 20.

Załóżmy, że przechodzimy od 4 do 7 dalej. Teraz otrzymujemy sumę odległości równą 20+ (9-1) -1 = 27 (coraz dalej od 8 wierzchołków i zbliżamy się do 1 wierzchołka).

Jako kolejny przykład, jeśli przechodzimy od 1 do 2, otrzymujemy sumę odległości równą 15+ (9-5) -5 = 14. W rzeczywistości Vertex 2 jest rozwiązaniem dla tego przykładu.

To byłby mój algorytm.

Answer 2

Każda krawędź e = {A, B}, ma następujące właściwości:

• a_count = liczba węzłów do boku (tym)
• b_count = liczba węzłów strony B (włącznie b)
• a_sum = suma odległości od jej węzłach SUBTREE
• b_sum = suma odległości od b do jego SUBTREE węzłów

a_count dla węzeł e = {a, b} mogą być oceniane w następujący sposób: * uzyskać wszystkie krawędzie, a nie w tym e, suma ich a_count * dodać 1 do sumy

a_sum dla węzła e = {a, b} można ocenić w następujący sposób: * uzyskać wszystkie krawędzie, a nie w tym e, suma ich a_sum * dodać a_count (zawiera +1 wyliczone dla każdej krawędzi i +1 do a)

można swobodnie zrobić obliczenia w funkcja rekurencyjna akceptująca parametry węzła i kierunku, zapisująca uzyskane wyniki w tablicy globalnej.

Jeśli uruchomisz tę funkcję na wszystkich krawędziach drzewa w obu kierunkach, otrzymasz pełne obliczenie krawędzi. Całkowity czas dla wszystkich obliczeń to O (n), ponieważ gdy dojdziesz do jakiegoś poddrzewa, natura rekursywna zamknie całe poddrzewo w tym kierunku, a następne wywołania uzyskają wynik z globalnej tablicy, a ty tylko wykonasz 2 * n połączeń dla twojej funkcji .

Dla węzła Ostatnią miarą jest suma wszystkich B_count + B_sum wszystkich krawędzi połączonych z węzłem. Wykonaj jeden przebieg tej oceny na węzłach i wybierz węzeł o minimalnej wartości.