Najlepsza odpowiedź
Różnica między wykresem a strukturą danych drzewa:
Wykres
- Na grafie może być więcej niż jedna ścieżka, tj. graf może mieć jednokierunkowe lub dwukierunkowe ścieżki między węzłami.
- Na grafie nie ma takiej koncepcji root .
- Wykres może mieć pętle, obwody, a także może mieć własne pętle.
- Na wykresie nie ma takiego relacja rodzic-dziecko.
- Wykresy są bardziej złożone w porównaniu z drzewami, ponieważ mogą mieć cykle, pętle itp.
- Na wykresie przechodzi DFS : algorytm pierwszego wyszukiwania w głębi oraz w BFS : algorytm wyszukiwania wszerz.
- Wykres może być cykliczny lub acykliczny.
- Istnieją głównie dwa rodzaje wykresów: wykresy ukierunkowane i nieukierunkowane.
- Aplikacja Graph likacje: kolorowanie map, algorytmy, kolorowanie wykresów, planowanie zadań itp.
- Na Graph, nr. krawędzi zależy od wykresu.
- Wykres jest modelem sieci.
Drzewa
- Drzewo jest specjalną formą grafu, tj. minimalnie połączonym grafem i posiadającym tylko jedną ścieżkę między dowolnymi dwoma wierzchołkami.
- Drzewo to szczególny przypadek wykresu bez pętli, obwodów i pętli własnych.
- W drzewie jest dokładnie jeden root i każde dziecko ma tylko jednego rodzica.
- W drzewach istnieje relacja między rodzicem a dzieckiem, więc przepływ może być zgodny z kierunkiem z góry na dół lub na odwrót.
- Drzewa są mniej złożone niż wykresy, ponieważ nie mają cykli, nie mają własnych pętli i są nadal połączone.
- Przechodzenie po drzewie jest rodzajem specjalnego przypadku przechodzenia wykresu. Drzewo jest przemierzane w zamówieniu w przedsprzedaży , zamówieniu i Post-Order (wszystkie trzy w DFS lub w BFS algorytm)
- Drzewa należą do kategorii DAG: Skierowane wykresy acykliczne to rodzaj skierowanego wykresu, który nie ma cykli.
- Różne typy drzew to: Drzewo binarne , Drzewo wyszukiwania binarnego, drzewo AVL, sterty.
- Aplikacje drzewa : sortowanie i wyszukiwanie jak przechodzenie po drzewie i wyszukiwanie binarne.
- Drzewo zawsze ma n-1 krawędzi.
- Drzewo jest modelem hierarchicznym.
Odpowiedź
Tak więc drzewa kd, na pierwszy rzut oka, mogą wydawać się bardziej teoretyczne niż praktyczne. Ale tak naprawdę tak nie jest.
Drzewa kd zawierają wiele ważnych aplikacji, z których niektóre obejmują:
1 . Wyszukiwanie najbliższego sąsiada
Powiedzmy, że zamierzasz utworzyć Social Cop w smartfonie. Social Cop pomaga ludziom zgłaszać przestępstwa na najbliższy posterunek policji w czasie rzeczywistym.
Więc co wydaje się być problemem?
Tak, dobrze zgadłeś. Musimy znaleźć posterunek policji najbliżej miejsca przestępstwa, zanim spróbujemy coś zgłosić.
Jak mogliśmy to zrobić szybko ?
Wydaje się, że drzewa k-d mogą pomóc Ci znaleźć najbliższego sąsiada do punktu na dwuwymiarowej mapie Twojego miasta. Wszystko, co musisz zrobić, to zbudować dwuwymiarowe drzewo kd z lokalizacji wszystkich posterunków policji w twoim mieście, a następnie przeszukać drzewo kd, aby znaleźć najbliższy posterunek policji w dowolnym miejscu w mieście.
OK, rozumiem, co potrafią. Ale jak oni to robią?
Jeśli wiesz już, jak działają drzewa wyszukiwania binarnego , zrozumienie, jak działają drzewa kd nic nowego. Drzewa k-d pomagają w partycjonowaniu przestrzeni, tak jak drzewa wyszukiwania binarnego pomagają w partycjonowaniu prawdziwej linii . drzewa k-d rekurencyjnie dzielą obszar przestrzeni, tworząc binarną partycję przestrzeni na każdym poziomie drzewa.
Tak wygląda trójwymiarowy region przestrzeni podzielony przez trójwymiarowe drzewo kd [1]:
Trójwymiarowe drzewo kd. Pierwszy podział (czerwony) tnie komórkę korzeniową (białą) na dwie podkomórki, z których każda jest następnie dzielona (zielona) na dwie podkomórki. Wreszcie każda z tych czterech jest podzielona (niebieska) na dwie podkomórki. Ponieważ nie ma już podziału, ostatnie osiem to komórki liści.
A jak zbudowane jest drzewo?
Na początek masz zbiór punktów w k-wymiarowej przestrzeni.Podajmy przykład dwuwymiarowego drzewa kd:
Dane wejściowe: (2,3), (5,4), (9,6), (4,7), (8, 1), (7,2)
Wynik: dwuwymiarowe drzewo kd [2]:
W przypadku drzew wyszukiwania binarnego binarny podział rzeczywistej linii w każdym węźle wewnętrznym jest reprezentowany przez punkt na linii rzeczywistej. Podobnie, w przypadku dwuwymiarowego drzewa kd, binarny podział dwuwymiarowej płaszczyzny kartezjańskiej w każdym węźle wewnętrznym jest reprezentowany przez linia w płaszczyźnie.
Na wszelki wypadek binarnych drzew wyszukiwania, punkt reprezentowany przez węzeł wewnętrzny służy jako punkt używany do podziału rzeczywistej linii. Jak wybrać linię podziału w przypadku dwuwymiarowych drzew kd?
Zasadniczo , możesz wybrać dowolną linię przechodzącą przez punkt reprezentowany przez węzeł wewnętrzny aby podzielić dwuwymiarową płaszczyznę kartezjańską.
Powyższe dane wyjściowe drzewa kd zostały utworzone przy użyciu prostej metody wyboru linii podziału w każdym wewnętrznym węźle drzewa: –
Poziom 0 : – Wybierz linię podziału prostopadłą do pierwszego wymiaru ( X w tym przypadku) i przechodząc przez punkt reprezentowany przez dany węzeł.
Poziom 1 : – Wybierz linię podziału prostopadle do drugiego wymiaru (w tym przypadku Y ) i przechodząc przez punkt reprezentowany przez odpowiedni węzeł.
: : :
Poziom k-1 : – Wybierz linię podziału prostopadłą do k-ty wymiar i przechodzący przez reprezentowany punkt przez dany węzeł. Poziom k : – Wybierz linię podziału prostopadłą do pierwszego wymiaru ( X w tym przypadku) i przechodząc przez punkt reprezentowany przez dany węzeł.
Zasadniczo na każdym poziomie zmieniamy wymiary X i Y w celu wybrania linii podziału w każdym węźle wewnętrznym drzewa kd.
Etykiety, które widzisz obok każdego z węzłów drzewa kd [2], reprezentują wybór wymiaru dla linii podziału w węzłach na tym poziomie.
Niech ” Teraz zobacz, jak nasze dwuwymiarowe drzewo kd dzieli dwuwymiarową płaszczyznę [3]:
Dobra, jak mam przeprowadzić wyszukiwanie?
Nie powiem, że zostawię to Tobie, ale Tobie Będę musiał skorzystać z pomocy innych zasobów, aby w pełni to zrozumieć. Mogę jednak powiedzieć, że to partycjonowanie przestrzeni przez drzewo kd może pomóc w znalezieniu najbliższego sąsiada określonego punktu w przestrzeni bez konieczności eksplorowania wszystkich partycji , czego potrzebowaliśmy, aby wykonywać raportowanie w czasie rzeczywistym dla Social Cop.
W celu zrozumienia algorytmu najbliższego sąsiada w drzewach kd, oto dobry zasób: http://www.stanford.edu/class/cs106l/handouts/assignment-3-kdtree.pdf
Pozwólcie, że szybko przeprowadzę was przez niektóre inne zastosowania drzew kd, ponieważ większość tła drzew kd została już omówiona w omówieniu pierwszej aplikacji.
2. Zapytania do bazy danych obejmujące wielowymiarowy klucz wyszukiwania
Zapytanie o wszystkich pracowników w grupie wiekowej (40, 50 lat) i otrzymujących wynagrodzenie w przedziale (15000, 20000) miesięcznie można przekształcić w problem geometryczny, w którym na osi X naniesiony jest wiek a pensja jest wykreślona wzdłuż osi y [4]
[4] Oś x oznacza wiek pracownika za lat , a oś Y oznacza miesięczne wynagrodzenie w tysiącach rupii .
Dwuwymiarowe drzewo kd na złożonym indeksie (wiek, wynagrodzenie) może pomóc w skutecznym wyszukiwaniu wszystkich pracowników, którzy mieszczą się w prostokątnym obszarze przestrzeni określonym przez zapytanie opisane powyżej.
3. Problem n-ciał [5]
W jaki sposób możemy skutecznie symulować ruchy zbioru obiektów poruszających się pod wpływem wzajemnego przyciągania grawitacyjnego?
Naiwna metoda polegałaby na obliczeniu siły grawitacji między obiektem wywołanej przez każdy inny obiekt w celu zasymulowania jego ruchu pod wpływem przyciągania grawitacyjnego. Co więcej, musielibyśmy to zrobić dla każdego obiektu, co zajęłoby O (n ^ 2) czasu.
Używając drzew k-d, możemy jednak podzielić przestrzeń i dla każdego podziału przestrzeni obliczyć jego całkowity wpływ na pozostałą przestrzeń. Poniżej znajduje się pseudokod [6] algorytmu.
Umieść obiekty w drzewie. Zacznij od dolnego poziomu drzewa, Dla każdego regionu na głębokości d w drzewie: Jeśli jakieś dzieci są liśćmi, oblicz interakcję bezpośrednio Oblicz „ Rozwinięcie wielobiegunowe „Przekształć to w rozszerzenie lokalne dla węzła nadrzędnego i przepuść. Przejdź na poziom d-1. Kiedy osiągniemy wierzchołek drzewa, cofnij się z powrotem w dół, sumując lokalne ekspansje.
4. Redukcja kolorów [7]
Co to jest inteligentny sposób na wybranie 256 kolorów do przedstawienia pełnokolorowego obrazu?
Naiwną metodą mogłoby być wybranie najczęściej używanych kolorów.
Jednak bardziej wydajna metoda mogłaby przedstawiać kolory w kategoriach ich RGB i utwórz trójwymiarowe drzewo kd w celu podzielenia przestrzeni zawierającej wszystkie kolory obrazu. Konstrukcja drzewa k-d zatrzymałaby się, gdy liczba węzłów liścia stałaby się równa 256. Średnia wartość RGB każdej z 256 partycji mogłaby zostać następnie wykorzystana do uzyskania palety 256 kolorów dla pełnego obrazu kolorowego.
Referencje: [1], [2], [3]: http://en.wikipedia.org/wiki/Kd-tree [4]: Klasyfikacja z wykorzystaniem najbliższych sąsiadów [5], [6], [7] : Drzewa KD