Zabawa z drzewami

15.12.2009 - Łukasz Zatorski
Trudność

„Głupiec i mędrzec nie widzą tego samego drzewa.” - mawiał William Blake. Drzewa dostarczają życiodajnego tlenu, w słoneczny dzień służą cieniem, a ich abstrakcyjne odpowiedniki są nieodzownym elementem arsenału dobrego programisty. Tylko, no właśnie, o czym dokładnie mowa i jak się do tego zabrać? W poszukiwaniu kilku klasycznych problemów informatycznych dotyczących drzew zapraszam do... Puszczy Amazońskiej.

W końcu, jeśli nie w lesie szukać drzew, to gdzie? Nasza odpowiedź nie będzie jednak tak oczywista, jakby się wydawało. Skupimy się na sercu każdej tropikalnej puszczy – rzece. W nieprzebytych i niezbadanych lasach, często jest ona jedyną znaną drogą i szybkim źródłem transportu między położonymi przy niej siedzibami plemion. Jeśli weźmiemy pod uwagę fragment jej dorzecza, w którym dopływy nie tworzą cyklu, a leżące nad nią wioski uznamy za wierzchołki grafu, spełnimy wszystkie konieczne wymagania by powstałą przez nas strukturę nazwać drzewem.

Między każdymi dwoma wierzchołkami wiedzie dokładnie jedna droga.

Gdzie tkwi problem:

Rozważmy lekarza działającego w ramach misji WHO1. Postanawia on założyć szpital w jednej z wiosek, do którego w razie pilnego przypadku (czyli takiego z którym nie potrafią sobie poradzić plemienni znachorzy) przybywałyby rzeką osoby potrzebujące z innych plemion. Załóżmy na razie, że wioski położone są od siebie w równych odległościach (w celu uniknięcia wojen terytorialnych, sprawiedliwie podzielono wybrzeża). Oczywistym jest, że wybór miejsca na szpital nie powinien być przypadkowy – w kwestii ratowania ludzkiego życia, czas ma ogromne znaczenie. Interesuje nas więc, by odległość szpitala do najdalszej wioski, była możliwie najmniejsza.

Za daleko!

Ta wioska nie nadaje się na szpital!

Stojące przed nami zadanie jest popularnym w algorytmice problemem optymalizacyjnym. W tym przypadku za kryterium wyboru uznajemy najgorszą możliwą sytuację, tzn. konieczność udzielenia pomocy osobie z najdalej położonej wioski. Kryterium to będziemy dla ułatwienia nazywać „postawą lekarza”.

 

małe drzewo.Wierzchołek którego szukamy to intuicyjnie ten „najbliżej środka” - nazywany również wierzchołkiem centralnym drzewa. Myślę że błyskawicznie udało Ci się go odnaleźć na mapie wiosek z naszego przykładu. Jednak w sytuacji, kiedy trzeba zmierzyć się z dużo większymi danymi, odpowiedź nie jest już taka oczywista.

Czy potrafisz znaleźć wierzchołek centralny drzewa po lewej?

Skoro intuicyjna metoda poszukiwania rozwiązania nie sprawdza się w przypadku większych drzew, spróbujmy   zapisać ją pod postacią jakiegoś algorytmu. Z pewnością pierwsze co zrobiłeś, to wykluczyłeś wszystkie liście.

 

Obserwacja:

Jeśli mamy do czynienia z więcej niż 2 wierzchołkami, to rozwiązaniem nie jest liść – widzimy bowiem, że gałąź, z której wyrasta, ma bliżej do wszystkich pozostałych wierzchołków, a dalej tylko do niego samego.

Spróbujmy zatem dalej postępować drogą eliminacji. Mając dane drzewo T1, odetnijmy wszystkie liście naraz i zobaczmy co się stało:

 

Obcinanie liści.

Żaden z liści nie mógł być wierzchołkiem centralnym, zatem zgodnie z naszą obserwacją nadal znajduje się on nowo powstałym drzewie T2.

Co więcej:

Najdłuższa ścieżka zawsze kończy się w jakimś liściu – w przeciwnym wypadku, moglibyśmy ją przedłużyć w dowolną stronę inną niż ta z której przyszliśmy (pamiętajmy, że w drzewie nie ma cykli!).

Oznacza to, że poprzez usunięcie liści, wartość najdłuższej ścieżki od każdego wierzchołka zmniejszyła się dokładnie o jeden.

Skoro wszystkim zabraliśmy tyle samo, w takim razie wierzchołek centralny drzewa T1 i T2 „nie zmienił swojego miejsca” - to nadal ten sam wierzchołek! Nie pozostaje nic innego, jak powtórzyć rekurencyjnie nasz algorytm. Z radością bierzemy więc do ręki nożyczki i ponownie tniemy, i tniemy, i tniemy, i... chwila, chwila, nie rozpędzajmy się!

Sytuacje końcowe.

 

No właśnie, każda przyjemność kiedyś się kończy. W momencie kiedy drzewo Tn składa się z samych liści, dokonanie cięcia nie jest już możliwe, lub spowoduje, że pozbędziemy się wszystkich wierzchołków. Rysunek obok  przedstawia dwie możliwe sytuacje końcowe. Oczywiście otrzymany wynik to wierzchołki centralne – dowiedliśmy tym samym, że czasem drzewo może posiadać dwa (ale zawsze sąsiadujące ze sobą).

 

 

 

Załóżmy że posiadamy już listę wierzchołków naszego drzewa. Jak zaimplementować taki algorytm?

  1. Dla każdego wierzchołka $ v $ możemy wyznaczyć jego stopień (przyjmijmy oznaczenie $ DEG[v] $).

  2. Liście (tzn. te dla których $ DEG[v]=1 $) umieszczamy we wspólnej kolejce $ Q_1 $ – aktualną porcję liści do usunięcia.

  3. Dopóki nie zostaną nam dwa wierzchołki:

    1. Usuń wierzchołek z kolejki $ Q_1 $ (oznaczmy go jako $ p $)
    2. Dla każdego sąsiada wierzchołka $ p $ który jeszcze nie został usunięty:
      1. Zmniejsz stopień sąsiada o $ 1 $
      2. Jeśli stopień sąsiada wynosi $ 1 $, dodaj go do kolejki $ Q_2 $ (oznacza to, że jest liściem do usunięcia w ,,następnej rundzie")
    3. Jeśli kolejka $ Q_1 $ jest pusta - zamień ją z kolejką $ Q_2 $

Dla chętnych:

Zamiast kolejek możemy użyć stosów, bądź odpowiednio zmodyfikowanej, jednej kolejki (jak?).

Dla każdej krawędzi i każdego wierzchołka w naszym algorytmie wykonujemy stałą liczbę operacji, zatem jego złożoność jest liniowa względem wielkości danych (mówimy też, że należy do klasy $  O(n)  $).

 

4.727275
Twoja ocena: Brak Ocena: 4.7 (11 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com