Zabawa z drzewami

15.12.2009 - Łukasz Zatorski
Trudność

Im dalej w las, tym więcej drzew:

Wierzchołek centralny nie jest niestety uniwersalną odpowiedzią na wszystkie pytania optymalizacyjne. Rozwiązania zależą od podjętego przez nas kryterium.

Przykładowo - wysyłanie codziennie dzieci do szkoły nie bardzo podobałoby się wodzom – wyraźnie destabilizuje to życie plemienne. Dlatego nauczyciele UNESCO korzystając z motorówek, każdego dnia odwiedzają którąś z wiosek i na noc wracają do bazy. Czas dojazdu nie jest aż tak istotny – w przypadku zaplanowanych wizyt nie trudno wyruszyć odpowiednio wcześniej. Większy problem stanowi natomiast zużycie paliwa – nauczyciele gotowi są przenieść swoją siedzibę w lepiej usytuowane miejsce, a za zaoszczędzone w ten sposób pieniądze woleliby kupić podręczniki i materiały do nauki. Zauważmy, że nauczycieli interesuje możliwie najniższe średnie zużycie paliwa na jedną podróż. Postawa ta oznacza w szczególności, że myślą bardziej globalnie i są czasem gotowi na daleką i kosztowną wyprawę, jeśli średni przypadek dzięki temu będzie mniejszy.

Różne odpowiedzi dla różnych kryteriów.

 

 

Drzewo po prawej przedstawia możliwość istnienia różnicy między postawą lekarza (preferowany wierzchołek - fioletowy), a postawą nauczyciela (preferowany wierzchołek - żółty).

 

 

 

Na dodatek, zużycie paliwa nie musi być na każdym odcinku koniecznie takie samo – zależy ono min. od siły prądu na danym fragmencie rzeki, czy głębokości koryta – uzupełniamy zatem nasz graf o wagi na jego krawędziach, a za odległość między dwoma wioskami uznajemy sumę krawędzi na łączącej je ścieżce. Metoda z obcinaniem liści nie bierze pod uwagę krawędzi, dlatego potrzebujemy świeżego podejścia.

Graf wiosek z wagami na krawędziach.

Mapa z wioskami i wskaźnikami zużycia paliwa na trasie.


Jak zatem wyznaczyć dla danego wierzchołka $ v $ jego średnią odległość do pozostałych?

Obserwacja:

Średnia odległość to suma odległości do wszystkich wierzchołków, podzielona przez ich ilość.

Ścieżki do wszystkich wierzchołków.

Dla danego drzewa, ilość wierzchołków nie zmienia się w trakcie wykonywanego algorytmu, dlategonasze kryterium możemy utożsamiać z najmniejszą sumą odległości do pozostałych wierzchołków.

Zauważmy, że sumując po kolei odległości do wszystkich wierzchołków, każdą krawędź liczymy wielokrotnie. Częstość użycia krawędzi zależy od ilości wierzchołków w poddrzewie, do którego ona prowadzi. Na rysunku obok krawędź między wierzchołkami 3 i 5 liczymy trzykrotnie - jako fragment drogi do wierzchołków 1,2,3.

Ukorzenione drzewo ma w naturalny sposób zdefiniowaną strukturę rekurencyjną. Niezależnie od użytej metody przeszukiwania (BFS, DFS), możliwe jest korzystanie z zależności między rodzicem a synem.  

Niech $ D[v] $ oznacza sumę odległości do korzenia w poddrzewie wyznaczonym przez wierzchołek $ v $,

 $ S[v] $ – ilość wierzchołków w tym poddrzewie, $ k_x $ - wagę krawędzi do wierzchołka $ x $.

Konstruujemy zależność rekurencyjną:

1. Dla liści drzewa: $ D[v]:=0, S[v]:=1 $  Obliczone wartości S i D.

2. Dla wierzchołka wewnętrznego:

$ S[v]:= 1+ \sum_{x \in child(v)} S[x] $

$ D[v] =\sum_{x \in child(v)} (S[x] * k_x + D[x]) $

(każda droga jest dotychczasową drogą do $ x $, i jeszcze pokonaniem odległości $ k_x $).

Jeśli zastosujemy tę zależność przy algorytmie przeszukiwania DFS dla każdego z wierzchołków z osobna, otrzymamy złożoność rzędu: $ n * O(n) = O(n^2) $. Wielkość ta nas nie zadowala – możemy odnieść wrażenie, że nie wykorzystujemy w pełni wszystkich posiadanych informacji – w końcu rozwiązania dla wierzchołków które znajdują się blisko, intuicyjnie powinny być zbliżone. Dlatego po obliczeniu rozwiązania dla jednego wierzchołka, spróbujmy ponownie wykorzystać zależność rekurencyjną, ale teraz w odwrotnym kierunku – tzn. „jaki ojciec, taki syn”.

Załóżmy zatem, że policzyliśmy wielkość $ D[v] $ dla korzenia $ v $, oraz dla każdego poddrzewa mamy już zapisane $ S[] $. Co stanie się teraz, kiedy przeniesiemy bazę nauczycieli do jego syna $ q $?

Przesunięcie.

Widzimy że część dróg ulega wydłużeniu, a część skróceniu.

Do $ S[q] $ wierzchołków mamy bliżej o wartość $ k_q $, natomiast odległość do pozostałych $ N – S[q] $ wierzchołków zwiększyła się o tę wartość. Tym samym możemy wyznaczyć:

$ D[q]=D[v]+k_q*(N–S[q])–k_q*S[q] $ $ =D[v]+k_q*(N–2*S[q]) $

Teraz możemy powtórzyć naszą operację dla synów wierzchołka $ q $, w rezultacie przez indukcję obliczymy dla każdego wierzchołka średnią odległość do wszystkich pozostałych. Wierzchołek o najmniejszej wartości $ D[] $ jest oczywiście najlepszym miejscem na założenie bazy dla nauczycieli.


Średnie odległości.

Mapa z zaznaczonymi średnimi odległościami dla każdej z wiosek.

Jeśli dotrwałeś do tego miejsca, drogi czytelniku – gratuluję! Wiesz już zatem jak znaleźć punkty szczególne i poznałeś tym samym podstawowe rodzaje sposobów i podejść do problemów informatycznych związanych z drzewami. Gorąco zachęcam do odprężającego spaceru w parku w ramach odpoczynku od komputera, a następnie proponuję zmierzyć się z zadaniami umieszczonymi na portalu :)

 


1 - Więcej o światowej organizacji zdrowia i jej misjach możesz przeczytać na http://www.who.int/.  

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com