Rekonstrukcja drzewa z zapytań separatora

18

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 nTTxabnn .

Czy istnieje o(n2) 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 ) .DO(nDlogn)

algorytm losowyO(nlog2n). (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 yxy . Sprawdź, czy jest to separator, jeśli nie, wykonaj wyszukiwanie binarne.

Wymaga oczekiwany czas na znalezienie separatora. Otrzymujemy więc O ( nO(nlogn) algorytm losowy.O(nlog2n)


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.

Jagadish
źródło
7
Pokaż, co już wiesz o problemie, abyśmy nie tracili czasu na wymyślanie nowego koła.
Jeffε
@ Jɛ ff E Zredagowałem swoje pytanie.
Jagadish

Odpowiedzi:

5

Nie . Poniższa prosta strategia przeciwnika implikuje, że każdy algorytm do rekonstrukcji drzewa węzłowego wymaga co najmniej ( n - 1nzapytań „między”.(n12)=n(n1)/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,,n100

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)yz(0,y,z)0xy

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 )0n-1(2)n-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ń.

Jeffε
źródło
Moje pytanie dotyczy drzew stałego stopnia. Ten argument nie działa w tym przypadku, prawda?
Jagadish,
2
@Jadadish: (1) Nie sądzę, że ten dowód dolnej granicy działa w przypadku algorytmów losowych. Przeciwnik wciąż może skonstruować błędny przykład, ale nie jest to sprzeczne z hipotezą, że losowy algorytm działa poprawnie z dużym prawdopodobieństwem. (2) Nawiasem mówiąc, wydaje się, że zadałeś pytanie znając odpowiedź. Po co to zrobiłeś?
Tsuyoshi Ito
2
Widzę. Dziękuję za wyjaśnienie, a także dziękuję za edycję pytania!
Tsuyoshi Ito
4
Jeśli masz algorytm losowy, masz algorytm. Determinizm jest przereklamowany.
Jeffε
1
Ten problem przypomina mi sortowanie / dopasowywanie nakrętek i śrub. Randomizowany algorytm działający z dużym prawdopodobieństwem w czasie jest łatwy - to po prostu losowy szybki sortowanie . Istnieje deterministyczny algorytm czasu O ( n log n ) , ale jest on poważnie nietrywialny . O(nlogn)O(nlogn)
Jeffε
5

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.O~(nn)

Jagadish
źródło