Jak znaleźć wszystkie ścieżki równości w zdegenerowanym drzewie, które zaczynają się na określonym wierzchołku?

Question

Mam kilka degenerate tree (wygląda jak tablica lub podwójnie powiązane listy). Na przykład, że jest to drzewo:

Każda krawędź ma pewną wagę. Chcę znaleźć wszystkie równe ścieżki, które zaczynają się w każdym wierzchołku.

Innymi słowy, chcę uzyskać wszystkie krotki (v1, v, v2), gdzie v1 i v2 są arbitralnym przodkiem i potomkiem takim, że c(v1, v) = c(v, v2).

Niech krawędzie mają następujące wagi (to tylko przykład):

a-b = 3

b-c = 1

c-d = 1

d-e = 1

Następnie:

1. Werteks A nie ma żadnej równej ścieżki (nie ma wierzchołka od lewej strony).
2. W wierzchołku B ma jedną równą parę. Ścieżka B-A jest równa ścieżce B-E(3 == 3).
3. Węzeł C ma jedną równą parę. Ścieżka B-C jest równa ścieżce C-D(1 == 1).
4. Węzeł D ma jedną równą parę. Ścieżka C-D jest równa ścieżce D-E(1 == 1).
5. Węzeł E nie ma żadnej równej ścieżki (nie ma wierzchołka od prawej strony).

Implementuję prosty algorytm, który działa w O(n^2). Ale dla mnie jest to zbyt wolne.

Answer 1

pisać w komentarzach, że obecne podejście jest

Wydaje się, że szuka sposobu, aby zmniejszyć stałą w czasie O (n^2). Wybieram jakiś wierzchołek. Następnie tworzę dwa zestawy. Następnie wypełniam te zbiory sumami cząstkowymi , podczas iteracji od tego wierzchołka do początku drzewa i do zakończenia drzewa . Następnie znajduję punkt przecięcia i otrzymuję liczbę ścieżek z tego wierzchołka. Następnie powtarzam algorytm dla wszystkich pozostałych wierzchołków.

Istnieje prostsze i, jak sądzę, szybsze podejście O(n^2), oparte na metodzie tzw. Dwóch wskaźników.

Dla każdego vertikusa v przejdź w tym samym czasie do dwóch możliwych kierunków.Masz jeden "wskaźnik" do wierzchołka (vl) przesuwający się w jednym kierunku i drugim (vr) w innym kierunku i staraj się zachować odległość od v do vl tak blisko odległości od v do vr, jak to możliwe. Za każdym razem, gdy odległości te stają się równe, masz równe ścieżki.

for v in vertices 
    vl = prev(v) 
    vr = next(v) 
    while (vl is still inside the tree) 
       and (vr is still inside the tree) 
     if dist(v,vl) < dist(v,vr) 
      vl = prev(vl) 
     else if dist(v,vr) < dist(v,vl) 
      vr = next(vr) 
     else // dist(v,vr) == dist(v,vl) 
      ans = ans + 1 
      vl = prev(vl) 
      vr = next(vr) 

(Przez precalculating sum przedrostek, można znaleźć dist w czasie O (1)).

Łatwo zauważyć, że nie ma sobie równych para zostaną pominięte, pod warunkiem że nie mają krawędzie zerowej długości .

Jeśli chodzi o szybsze rozwiązanie, jeśli chcesz listę wszystkie pary, to nie można zrobić go szybciej, ponieważ liczba par będzie O (n^2) w najgorszym przypadku. Ale jeśli potrzebujesz tylko tych par, mogą istnieć szybsze algorytmy.

UPD: Wpadłem na inny algorytm obliczania ilość, co może być szybciej w przypadku, gdy krawędzie są dość krótkie. Jeśli oznaczymy całkowitą długość łańcucha (suma wszystkich krawędzi) jako L, wówczas algorytm działa w O(L log L). Jest jednak znacznie bardziej zaawansowany koncepcyjnie i bardziej zaawansowany w kodowaniu.

Po pierwsze niektóre teoretyczne rozumowanie. Zastanów się nad wierzchołkiem v. Pozwól nam mieć dwie tablice: a i b, a nie tablice indeksowane zero w stylu C, ale tablice z indeksacją od -L do L.

Zdefiniujmy

• dla i>0, a[i]=1 IFF do prawo z v od odległości dokładnie i tam jest wierzchołek, inaczej a[i]=0
• dla i=0, a[i]≡a[0]=1
• dla i<0 , a[i]=1 iff pod numerem po lewej stronie z v od odległości dokładnie -i istnieje wierzchołek, inaczej a[i]=0

Prosty zrozumienie tej tablicy jest następująca. Rozciągnij swój wykres i ułóż go wzdłuż osi współrzędnych, tak aby każda krawędź miała długość równą swojej wadze, a ten wierzchołek v leży w punkcie początkowym. Następnie a[i]=1 iff jest wierzchołek na współrzędnej i.

Dla przykładu, na wierzchołku „b” wybrany jako v:

  a--------b--c--d--e 
    --|--|--|--|--|--|--|--|--|--> 
     -4 -3 -2 -1 0 1 2 3 4 
a: ... 0 1 0 0 1 1 1 1 0 ... 

W innej tablicy, tablicy b określamy wartości w sposób symetryczny w stosunku do pochodzenia, czy mamy odwrócony kierunek osi:

• dla i>0, b[i]=1 IFF do lewo z v od odległości dokładnie i tam jest wierzchołek, inaczej b[i]=0
• dla i=0, b[i]≡b[0]=1
• dla i<0, b[i]=1 IFF do prawo z v na odległość dokładnie -i istnieje wierzchołek, inaczej b[i]=0

Teraz rozważmy trzecia tablica c taka, że ​​c[i]=a[i]*b[i], gwiazdka pozostaje tutaj dla zwykłego mnożenia. Oczywiście po ścieżce o długości abs(i) po lewej stronie w wierzchołku, a ścieżka o długości abs(i) po prawej stronie w wierzchołku. Tak więc dla i>0 każda pozycja w c, która ma c[i]=1, odpowiada potrzebnej ścieżce. Istnieją również pozycje ujemne (c[i]=1 z i<0), które odzwierciedlają tylko pozycje dodatnie i jeszcze jedną pozycję, gdzie c[i]=1, a mianowicie pozycja i=0.

Oblicz sumę wszystkich elementów w c. Ta suma będzie wynosić sum(c)=2P+1, gdzie P jest całkowitą liczbą ścieżek, których potrzebujesz, przy czym v jest jej centrum. Więc jeśli znasz sum(c), możesz łatwo określić P.

Rozważmy teraz dokładniej tablice a i b i jak one się zmieniają po zmianie wierzchołka v. Oznaczmy: v0 skrajny lewy wierzchołek (korzeń drzewa) i a0 i b0 odpowiednie macierze dla tego wierzchołka.

Dla dowolnego wierzchołka v oznacza d=dist(v0,v). To łatwo zauważyć, że na wierzchołku v Macierze a i b tylko tablic a0 i b0 przesunięty o d:

a[i]=a0[i+d] 
b[i]=b0[i-d] 

Jest oczywiste, jeśli pamiętać zdjęcie z drzewa rozciągniętej wzdłuż osi współrzędnych.

Teraz weźmy pod uwagę jeszcze jedną tablicę, S (jedną tablicę dla wszystkich wierzchołków), a dla każdego wierzchołka v połóżmy wartość sum(c) do elementu S[d] (d i c zależą v).

Dokładniej, niech nam określić tablicę S tak, że dla każdego d

S[d] = sum_over_i(a0[i+d]*b0[i-d]) 

Gdy wiemy tablicę S możemy iteracyjne nad wierzchołkami i dla każdego wierzchołka v uzyskać jego sum(c) prostu jako S[d] z d=dist(v,v0), ponieważ dla każdego wierzchołka v mamy sum(c)=sum(a0[i+d]*b0[i-d]).

Ale formuła S jest bardzo prosta: S jest tylko convolution z a0 i b0 sekwencji. (Formuła nie dokładnie śledzić definicji, ale jest łatwe do modyfikacji do dokładnej formie definicji.)

Więc co teraz musimy podano a0 i b0 (który możemy obliczyć w O(L) czasie i przestrzeni), obliczyć S tablica. Następnie możemy wykonać iterację po tablicy S i po prostu wyodrębnić numery ścieżek z S[d]=2P+1.

Bezpośrednia aplikacja powyższego wzoru to O(L^2). Jednak splot dwóch sekwencji can be calculated in O(L log L) przez zastosowanie algorytmu szybkiej transformacji Fouriera. Co więcej, możesz zastosować podobne Number theoretic transform (nie wiesz, czy istnieje lepszy link) do pracy z liczbami całkowitymi i uniknąć problemów z precyzją.

Więc Ogólny zarys algorytmu staje

calculate a0 and b0 // O(L) 
calculate S = corrected_convolution(a0, b0) // O(L log L) 
v0 = leftmost vertex (root) 
for v in vertices: 
    d = dist(v0, v) 
    ans = ans + (S[d]-1)/2 

(ja to nazywam corrected_convolution ponieważ S nie jest dokładnie splot, ale bardzo podobny obiekt, dla którego można zastosować podobny algorytm. Ponadto, można zdefiniuj nawet S'[2*d]=S[d]=sum(a0[i+d]*b0[i-d])=sum(a0[i]*b0[i-2*d]), a następnie S' jest właściwym splotem.)