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 n .
Czy istnieje algorytm dla powyższego problemu?
Załóżmy, że stopień dowolnego węzła w wynosi co najwyżej 3.
Co wiem
Sprawa o ograniczonej średnicy jest łatwa . Jeśli średnica drzewa wynosi , 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.
- Wybierz dowolny wierzchołek x. Jeśli jest to dobry separator, oznacz to i powtórz.
- Znajdź wszystkich 3 sąsiadów x.
- 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 ) .
algorytm losowy. (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 y . Sprawdź, czy jest to separator, jeśli nie, wykonaj wyszukiwanie binarne.
Wymaga oczekiwany czas na znalezienie separatora. Otrzymujemy więc O ( n algorytm losowy.
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.
Odpowiedzi:
Nie . Poniższa prosta strategia przeciwnika implikuje, że każdy algorytm do rekonstrukcji drzewa węzłowego wymaga co najmniej ( n - 1n zapytań „między”.(n−12)=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,…,n−1 0 0
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 ( 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ń.źródło
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~( n n--√)
źródło