Mam pytanie, które jest częścią mojego programu.Centrum wyszukiwania drzewa
Dla drzewa T = (V, E) musimy znaleźć węzeł v w drzewie, który minimalizuje długość najdłuższej ścieżki od v do dowolnego innego węzła.
więc jak znaleźć środek drzewa? Czy może być tylko jedno centrum lub więcej?
Jeśli ktoś może dać mi dobry algorytm, więc mogę uzyskać pomysł, w jaki sposób mogę dopasować się do mojego programu.
Zastanów się drzewo z dwoma węzłami? Który jest centrum? Każda z nich wystarczy, ergo drzewo może mieć więcej niż jedno centrum.
Teraz pomyśl, co to znaczy być centrum. Jeśli wszystkie gałęzie są tej samej wysokości, centrum jest korzeniem (wszystkie ścieżki przechodzą przez korzeń). Jeśli gałęzie mają różną wysokość, środek musi być korzeniem lub gałęzią o największej wysokości, w przeciwnym razie maksymalna ścieżka jest większa niż wysokość najwyższej gałęzi, a korzeń byłby lepszym wyborem. Teraz, jak daleko do najwyższego oddziału musimy wyglądać? Połowa różnicy wysokości między najwyższą gałęzią (od korzenia) a następną najwyższą gałęzią (jeśli różnica wynosi co najwyżej 1, wystarczy podać korzeń). Po co, ponieważ gdy przechodzimy do najwyższego odgałęzienia o jeden poziom, wydłużamy ścieżkę do najgłębszego węzła następnego najwyższego odgałęzienia o jeden i zmniejszamy odległość do najgłębszego węzła w bieżącej gałęzi o jeden. W końcu będą one równe, gdy pokonasz połowę różnicy w głębi. Teraz, gdy schodzimy do najwyższego oddziału, musimy po prostu wybrać na każdym poziomie najwyższą podgałęzie. Jeśli więcej niż jeden ma taką samą wysokość, po prostu wybieramy jeden arbitralnie.
Zasadniczo to, co robisz, to znalezienie najdłuższej ścieżki na wykresie, która jest odległością między najwyższą gałęzią drzewa i następną najwyższą gałęzią, a następnie znalezieniem środkowego węzła na tej gałęzi. Ponieważ może istnieć wiele ścieżek o tej samej długości co najdłuższa ścieżka, a długość najdłuższej ścieżki może być równa, masz wiele możliwych centrów.
Zamiast zrobić zadanie domowe dla ciebie, mam zamiar zapytać cię przez proces myślowy, który dostaje odpowiedź ...
1) Co byś zrobił z abc milimetrowym (trzy wierzchołki, dwa krawędzie i zdecydowanie acykliczny)? Wyobraź sobie przez chwilę, że musisz umieścić etykiety na niektórych wierzchołkach, wiesz, że dostaniesz minimalną najdłuższą ścieżkę na wierzchołku "centrum". (b, z ostateczną etykietą "1") Ale robienie tego jednym krokiem wymaga mocy psychicznej. Zadaj sobie pytanie, co b dzieli 1 krok. Jeśli najdłuższa ścieżka do b wynosi 1, a my właśnie zrobiliśmy krok do tyłu tą ścieżką, jaka jest długość naszej dotychczasowej ścieżki? (najdłuższa ścieżka = 1, -1 dla tyłu o jeden stopień Aha: 0). To musi być etykieta liści.
2) Co to sugeruje jako pierwsze cięcie algorytmu? Zaznaczyć liście "0", zaznaczyć ich upstream "1", oznaczyć ich upstreams "2" i tak dalej. Maszerujemy z liści i liczymy dystans, kiedy jedziemy ...
3) Umm ... Mamy problem z wykresem a-b-c-d. (Odtąd etykietowany wierzchołek zostanie zastąpiony jego etykietą.) Oznakowanie liści "0" daje 0-bc-0 ... Nie możemy uzyskać dwóch centrów ... Heck, co robimy w prostszym stan 0-b-1? Chcemy oznaczać etykietą b zarówno "1", jak i "2" ... Obsługujemy te w odwrotnej kolejności ...
W 0-b-1, jeśli przedłużysz ścieżkę z b o jeden, otrzymamy ścieżka długości 1. Jeśli rozszerzymy ścieżkę z prawej strony b, otrzymamy 2. Chcemy śledzić "długość najdłuższej ścieżki od v do dowolnego innego węzła", więc chcemy śledzić najdłuższą ścieżkę do b. Oznacza to, że oznaczamy b "2".
0-b-1 -> 0-2-1
W 0-b-c-0, komputer nie faktycznie jednocześnie aktualizacji bi c. Aktualizuje jedną z nich, podając 0-1-c-0 lub 0-b-1-0, a następna aktualizacja daje 0-1-2-0 lub 0-2-1-0. Zarówno b jak i c są "centrum" tego wykresu, ponieważ każdy z nich spełnia żądanie "węzła v w drzewie, który minimalizuje długość najdłuższej ścieżki od v do dowolnego innego węzła". (Ta długość to 2.)
Prowadzi to do innej obserwacji: wynikiem obliczeń nie jest oznaczanie wykresu, to szukanie ostatniego wierzchołka, który oznakujemy i/lub wierzchołka, który kończy się największą etykietą. (Możliwe, że nie znajdziemy dobrego sposobu na zamówienie etykiet, więc w końcu będziemy musieli znaleźć maksimum na końcu, a może to zrobimy, a kto wie.)
4) Tak więc teraz mamy coś w stylu: wykonaj dwie kopie wykresu - oznaczoną etykietą i kopię do wypalenia. Pierwszy będzie przechowywać etykiety i to on będzie miał ostateczną odpowiedź. Spalona kopia będzie coraz mniejsza, ponieważ usuniemy z niej nieoznaczone wierzchołki (aby znaleźć nowe wierzchołki nadające się do etykietowania). (Istnieją inne sposoby, aby to zorganizować tak, że tylko jedna kopia wykresu służy Gdy dojdziesz do końca rozumiejąc tę odpowiedź, należy znaleźć sposób na zmniejszenie tych odpadów..) Zarys:
label = 0
while the burndown graph is nonempty
collect all the leaves in the burndown-graph into the set X
for each leaf in the set X
if the leaf does not have a label
set the leaf's label (to the current value of label)
delete the leaf from the burn-down graph (these leafs are two copies of the same leaf in the input graph)
label = label+1
find the vertex with the largest label and return it
5) Jeśli faktycznie obejrzysz ten bieg, zauważysz kilka możliwości skrócenia czasu. W tym zastąpienie wyszukiwania na ostatniej linii konturu szybszym sposobem rozpoznania odpowiedzi.
A teraz ogólne wskazówki dotyczące strategii rozwiązywania problemów związanych z algorytmem:
* Wykonaj kilka małych przykładów ręcznie. Jeśli nie rozumiesz, jak robić małe przypadki, nie ma możliwości, abyś natychmiast wskoczył do środka i powiedział komputerowi, jak zrobić duże skrzynie. * Jeśli którykolwiek z powyższych kroków wydawał się być pozbawiony motywacji lub całkowicie nieprzejrzysty, będziesz musiał uczyć się o wiele, dużo trudniej zrobić dobrze w dziedzinie informatyki. To może być Informatyka nie jest dla ciebie ...
Istnieją dwa sposoby, aby to zrobić (oba działa w tym samym czasie):
Wybierz dowolny wierzchołek v1 na drzewie. Wykonaj BFS z tego wierzchołka. Ostatni wierzchołek (v2), który wykonasz, będzie najdalszym wierzchołkiem od v1. Teraz uruchom kolejny BFS, tym razem z wierzchołka v2 i uzyskaj ostatni wierzchołek v3.
Ścieżka od v2 do v3 jest średnicą drzewa, a Twoje centrum leży gdzieś na nim. Dokładniej to leży w jego środku. Jeśli ścieżka ma 2n + 1 punktów, będzie tylko 1 centrum (w pozycji n + 1). Jeśli ścieżka ma 2n punktów, będą dwa ośrodki w pozycjach n i n + 1.
Używasz tylko 2 wywołań BFS, które działają w czasie 2 * O(V).
Jeśli dokładnie punkt środkowy nie istnieje, jak możemy wybrać? Mam na myśli, jeśli najdłuższym sposobem jest a-b-c, a-b ma długość 1, a b-c ma długość 2?Lub bardziej złożony przykład? – cnhk
Wybierz jeden arbitralnie, jeśli potrzebujesz tylko jednego węzła, który kwalifikuje się, lub skonstruuj zestaw centralny, jeśli potrzebujesz wszystkich tych kwalifikacji. – tvanfosson