Rekonstrukcja drzewa z zapytań separatora

Załóżmy, że jest drzewem o stałym stopniu, którego struktury nie znamy. Problem polega na wyprowadzeniu drzewa T przez zadawanie zapytań o postać: „Czy węzeł x leży na ścieżce od węzła a do węzła b ?”. Załóżmy, że na każde zapytanie można odpowiedzieć w stałym czasie przez wyrocznię. Znamy wartość n , liczbę węzłów w drzewie. Celem jest zminimalizowanie czasu potrzebnego do wygenerowania drzewa w kategoriach $T$$T$$x$$a$$b$$n$$n$ .

Czy istnieje $o(n^2)$ algorytm dla powyższego problemu?

Załóżmy, że stopień dowolnego węzła w wynosi co najwyżej 3.$T$

Co wiem

Sprawa o ograniczonej średnicy jest łatwa . Jeśli średnica drzewa wynosi $D$ , możemy uzyskać algorytm dzielenia i zdobywania:

Każde drzewo binarne ma dobry separator, który dzieli drzewo na komponenty o wielkości nie mniejszej niż 1 / 3n.

1. Wybierz dowolny wierzchołek x. Jeśli jest to dobry separator, oznacz to i powtórz.
2. Znajdź wszystkich 3 sąsiadów x.
3. Przejdź w kierunku sąsiada, który ma największą liczbę węzłów. Powtórz krok 2 z sąsiadem.

Ponieważ znalezienie separatora wymaga co najwyżej kroków, otrzymujemy algorytm O ( n D log n ) .$D$$O(nD\log n)$

algorytm losowy$O(n\;\log^2 n)$. (przeniesiono z komentarzy poniżej)

Wybierz losowo dwa wierzchołki xiy. Z prawdopodobieństwem 1/9 będą leżeć po przeciwnych stronach separatora. Wybierz środkowy węzeł ścieżki od do $x$$y$ . Sprawdź, czy jest to separator, jeśli nie, wykonaj wyszukiwanie binarne.

Wymaga oczekiwany czas na znalezienie separatora. Otrzymujemy więc O ( $O(n\;\log n)$ algorytm losowy.$O(n\;\log^2 n)$

Tło. Dowiedziałem się o tym problemie od znajomego, który pracuje w probabilistycznych modelach graficznych. Powyższy problem z grubsza odpowiada nauce struktury drzewa skrzyżowań przy użyciu wyroczni, która, biorąc pod uwagę trzy zmienne losowe X, Y i Z, może powiedzieć wartość wzajemnej informacji między X i Y, biorąc pod uwagę wartość Z. Jeśli wartość jest bliska do zera możemy założyć, że Z leży na ścieżce od X do Y.

Nie . Poniższa prosta strategia przeciwnika implikuje, że każdy algorytm do rekonstrukcji drzewa węzłowego wymaga co najmniej ( n - $n$zapytań „między”.$\binom{n-1}{2} = n(n-1)/2$

Arbitralnie oznacz węzły . Przeciwnik odpowiada na wszystkie pytania, jakby drzewo było gwiazdą z wierzchołkiem 0 pośrodku; myśl o 0 jako katalogu głównym, a pozostałe węzły jako o jego dzieciach.$0,1,2,\dots,n-1$$0$$0$

Between?(a,x,b)
    if x=0 return TRUE else return FALSE

Załóżmy teraz, że algorytm zatrzymuje się po wykonaniu mniej niż zapytań. Następnie muszą być dwa wierzchołki y i z , żadne równe zero, tak że algorytm nie sprawdził żadnej permutacji potrójnej ( 0 , y , z ) . Jeśli algorytm twierdzi, że drzewo nie jest gwiazdą o środku 0 , przeciwnik ujawnia swoje dane wejściowe, co dowodzi, że algorytm jest błędny. Przeciwnik ujawnia następnie, że x jest faktycznie jedynym dzieckiem y , co ponownie potwierdza algorytm.$n(n-1)/2$$y$$z$$(0,y,z)$$0$$x$$y$

Aktualizacja: Ups, właśnie zauważyłem ograniczenie stopnia. Na szczęście nie jest to poważna przeszkoda. Zastąp węzeł ulubionym drzewem binarnym, a pozostałe n - 1 węzły pozostawiają w nieznanej kolejności, a następnie ujawnij to poddrzewo algorytmowi rekonstrukcji. Rekonstrukcja wynikowego drzewa binarnego z węzłem ( 2 n - 3 ) nadal wymaga co najmniej n ( n - 1 ) / 2 zapytań. Odpowiednio odtworzenie drzewa binarnego z węzłem m wymaga co najmniej ( m + 3 $0$$n-1$$(2n-3)$$n(n-1)/2$$m$ zapytań. (Jestem pewien, że bardziej subtelna konstrukcja poprawiłaby stałą.)$(m+3)(m+2)/8$ Jak zauważa Jagadish, to uogólnienie nie działa; zapytania o wewnętrzne węzły w drzewie narzucają porządek na liściach, co zmniejsza liczbę niezbędnych zapytań.

Anindya Sen i ja mamy artykuł w ALT '13, w którym podajemy algorytm dla tego problemu. Nie wiemy, czy możliwy jest lepszy algorytm.$\tilde O(n \sqrt{n})$