Spis Treści
Wymagania i kryteria oceniania
Należy zaimplementować algorytm wyznaczający najbliższego wspólnego przodka (ang. Lowest Common Ancestor, LCA) dwóch wierzchołków w drzewie oraz opanować (ze zrozumieniem) dotyczącą go teorię.
Najbliższym wspólnym przodkiem wierzchołków u i v w drzewie ukorzenionym nazywamy położony najgłębiej (najdalej od korzenia) wierzchołek, który jest jednocześnie przodkiem u i v (leży na obu ścieżkach: od korzenia do u i od korzenia do v); przyjmujemy przy tym, że każdy wierzchołek jest swoim własnym przodkiem.
Program powinien wczytać drzewo (np. do list sąsiedztwa) albo mieć je wprowadzone na stałe w programie, a następnie odpowiadać na kolejne zapytania o najbliższego wspólnego przodka podanej pary wierzchołków.
Maksymalna ocena zależy od wybranego wariantu.
Poniżej przez V oznaczamy liczbę wierzchołków drzewa.
Warianty
Algorytm bez wstępnego przetwarzania (na ocenę 3)
Algorytm odpowiadający na pojedyncze zapytanie w czasie O(V).
Algorytm ze wstępnie policzonymi głębokościami wierzchołków (na ocenę 3,5)
Algorytm odpowiadający na zapytanie o LCA dla dowolnych wierzchołków u i v w czasie proporcjonalnym do długości ścieżki pomiędzy u i v (w pesymistycznym przypadku O(V)), po wstępnym policzeniu głębokości wszystkich wierzchołków w czasie O(V) i zapamiętaniu ich w tablicy (dodatkowa pamięć O(V)).
Wariant ten można zrealizować poprzez wstępne policzenie (w czasie O(V), np. algorytmem DFS) i zapisanie w tablicy głębokości każdego wierzchołka. To pozwoli na wyrównanie głębokości, czyli znalezienie przodka głębszego z wierzchołków podanych w zapytaniu, który jest na tej samej głębokości, co drugi z wierzchołków. Poczynając od wspólnej głębokości, można kontynuować dalszą, tym razem równoległą, wędrówkę w górę drzewa, aż do napotkania wspólnego przodka.
Wykonanie tego wariantu można traktować jako dobry wstęp do wariantu na 4,5.
Metoda wskaźników skokowych (na ocenę 4,5)
Algorytm używający metody ze wskaźnikami skokowymi (ang. binary lifting), by odpowiadać na pojedyncze zapytanie w czasie O(log(V)). Wymaga wstępnego przetwarzania drzewa i zbudowania struktury wspomagającej w czasie i pamięci O(V log(V)).
Opcjonalne rozszerzenia (dotyczy wszystkich wariantów)
Wyznaczanie LCA względem dowolnego korzenia (+0,5 do oceny)
Należy wzbogacić swój program o wyznaczanie najbliższego wspólnego przodka zadanej pary wierzchołków względem korzenia wskazanego w zapytaniu (potencjalnie innego w każdym zapytaniu; zapytanie zawiera wtedy trójkę wierzchołków: parę, dla której wyznaczamy przodka, oraz korzeń), bez wydłużenia asymptotycznego czasu potrzebnego na odpowiedź lub wstępne przetwarzanie drzewa (dla wariantu na ocenę 3,5 czas odpowiedzi jest wtedy proporcjonalny do łącznej długości ścieżek łączących oba wierzchołki z zapytania i wskazany korzeń).
Wskazówka: należy ustalić dowolny pomocniczy korzeń r0 (np. ten użyty we wstępnym przetwarzaniu) i odpowiadać na zapytania bazowym algorytmem względem niego; dla zapytania (u, v, r) wystarczy wyznaczyć a = LCA(u, v), b = LCA(u, r) oraz c = LCA(v, r) względem r0 i jako wynik zwrócić najgłębszy (względem r0) spośród wierzchołków a, b i c (głębokości względem r0 są już zapamiętane w tablicy w wariantach na 3,5 i 4,5, a w wariancie na 3 można je wyznaczyć na bieżąco w czasie O(V)).
Wykorzystanie LCA do znalezienia długości ścieżek (+0,5 do oceny)
W tym wariancie zakładamy, że drzewo ma nieujemne wagi na krawędziach, a program ma wykorzystywać LCA(u, v) do policzenia długości ścieżki (sumy wag krawędzi) pomiędzy dowolnymi wierzchołkami u i v w czasie O(1) (nie licząc czasu potrzebnego na wyznaczenie LCA).
Program może w tym celu zbudować dodatkową strukturę w czasie i pamięci O(V).
Wskazówka: w strukturze warto zapamiętać odległość (sumę wag krawędzi) każdego z wierzchołków od korzenia.
Przykładowe pytania sprawdzające
Dla wszystkich wariantów
- Jak zdefiniowany jest najbliższy wspólny przodek dwóch wierzchołków w drzewie zakorzenionym? Czym różni się od dowolnego wspólnego przodka?
- Zilustrować działanie zaimplementowanego algorytmu dla zadanego drzewa i wskazanej pary wierzchołków.
- Jaka jest złożoność czasowa oraz pamięciowa zaimplementowanego algorytmu? Wskazać miejsca w kodzie (pętle, rekurencje), które za to odpowiadają.
- Jaka jest złożoność czasowa pojedynczego zapytania, a jaka – wstępnego przetwarzania drzewa (o ile program je wykonuje)?
- Czym różni się drzewo od grafu? Jakie własności drzewa wykorzystuje zaimplementowany algorytm?
Dla wariantu ze wstępnie policzonymi głębokościami (na ocenę 3,5)
- Jak wyznacza się głębokości wszystkich wierzchołków i dlaczego można to zrobić w czasie O(V) oraz pamięci O(V)?
- Na czym polega wyrównanie głębokości obu wierzchołków z zapytania i dlaczego po nim wystarczy równoległa wędrówka w górę drzewa?
- Dlaczego odpowiedź na zapytanie działa w czasie proporcjonalnym do odległości pomiędzy wierzchołkami z zapytania (a w pesymistycznym przypadku w czasie O(V))?
Dla metody wskaźników skokowych (na ocenę 4,5)
- Jak zbudowana jest struktura wspomagająca, tj. tablica wskaźników skokowych – jakie informacje przechowuje dla każdego wierzchołka?
- Jak wyznaczyć 2^i-tego przodka wierzchołka na podstawie wskaźników obliczonych dla mniejszych wartości i? Podaj odpowiednią zależność.
- W jaki sposób wskaźniki skokowe pozwalają pominąć („przeskoczyć”) wiele wierzchołków naraz oraz wyrównać głębokość obu wierzchołków?
- Zilustrować działanie wskaźników skokowych przy odpowiedzi na przykładowe zapytanie.
- Dlaczego wstępne przetwarzanie drzewa (budowa tablicy wskaźników skokowych) ma złożoność (czasową oraz pamięciową) O(V log(V))?
- Jak działa użyty w implementacji algorytm przechodzenia drzewa (np. DFS) i jaką ma złożoność?
Dla wariantu z dowolnym korzeniem
- Jak zmienia się wynik, gdy drzewo zostanie zakorzenione w innym wierzchołku? W jaki sposób obsłużyć korzeń wskazany w zapytaniu, nie powtarzając wstępnego przetwarzania drzewa?
Dla wariantu ze znajdowaniem długości ścieżek
- Jak wyznacza się odległości wszystkich wierzchołków od korzenia i dlaczego można to zrobić w czasie O(V) oraz pamięci O(V)?
- Mając wyznaczone LCA(u, v) oraz odległości wierzchołków od korzenia, jak policzyć długość ścieżki pomiędzy u i v w czasie O(1)? Dlaczego ten sposób działa?
- Zilustrować wyznaczanie długości ścieżki dla przykładowego drzewa z wagami i wskazanej pary wierzchołków.