Cel mai bun răspuns
Diferența dintre grafic și structura de date arborescentă:
Grafic
- În grafic poate exista mai multe căi, adică graficul poate avea căi unidirecționale sau bidirecționale între noduri.
- În grafic nu există un astfel de concept de rădăcină .
- Graficul poate avea bucle, circuite și poate avea autocirculări.
- În Grafic nu există astfel relația părinte copil.
- Graficele sunt mai complexe în comparație cu arborii, deoarece pot avea cicluri, bucle etc.
- Graficul este parcurs de DFS : Căutare Depth First și în BFS : algoritm Breadth First Search.
- Graficul poate fi ciclic sau aciclic.
- Există în principal două tipuri de grafice: grafice direcționate și nedirecționate.
- Aplicație grafică licențe: colorarea hărților, algoritmi, colorarea graficelor, programarea lucrărilor etc.
- În grafic, nr. de margini depinde de grafic.
- Graficul este un model de rețea.
Copaci
- Arborele este o formă specială de grafic, adică un grafic minim conectat și având o singură cale între oricare două vârfuri.
- Arborele este un caz special al graficului fără bucle, fără circuite și fără autocircuituri.
- În arbore există exact o rădăcină / span> nod și fiecare copil are un singur părinte.
- În copaci, există relația copil părinte, astfel încât fluxul poate fi acolo cu direcția de sus în jos sau invers.
- Arborii sunt mai puțin complecși decât graficii, deoarece nu au cicluri, nu au bucle de sine și sunt încă conectați.
- Traversarea arborelui este un fel de caz special de traversare de grafic. Arborele este parcurs în precomandă , în ordine și Post-Comandă (toate trei în DFS sau în BFS algoritm)
- Arborii aparțin categoriei DAG: Graficele aciclice direcționate este un fel de grafic direcționat care nu are cicluri.
- Diferite tipuri de arbori sunt: Arborele binar , Arborele de căutare binar, arborele AVL, grămezi.
- Aplicații arborescente : sortare și căutare ca arborele transversal și căutarea binară.
- Arborele are întotdeauna n-1 margini.
- Arborele este un model ierarhic.
Răspuns
Deci, arborii kd, la prima vedere, pot părea mai teoretici decât practici. Dar acest lucru nu este cazul.
Arborii kd conțin o varietate de aplicații importante, dintre care unele includ:
1 Cea mai apropiată căutare de vecini
Să spunem că intenționați să creați un Social Cop în smartphone-ul dvs. Social Cop îi ajută pe oameni să raporteze infracțiuni la cea mai apropiată secție de poliție în timp real.
Deci, ce pare a fi o problemă aici?
Da, ai ghicit bine. Trebuie să căutăm secția de poliție cea mai apropiată de locul crimei înainte de a încerca să raportăm ceva.
Cum am putea face acest lucru rapid ?
Se pare că copacii k-d vă pot ajuta să găsiți cel mai apropiat vecin de un punct de pe o hartă bidimensională a orașului dvs. Tot ce trebuie să faceți este să construiți un copac kd bidimensional din locațiile tuturor secțiilor de poliție din orașul dvs. și apoi interogați arborele kd pentru a găsi cea mai apropiată secție de poliție de la orice locație dată din oraș.
Bine, primesc ce pot face. Dar cum o fac?
Dacă știți deja cum funcționează copaci binari de căutare , înțelegând cum ar funcționa copacii kd nu fi nimic nou. copacii k-d ajută la partiționarea spațiului, la fel cum arborii binari de căutare ajută la partiționarea linia reală . k-d copaci partiționează recursiv o regiune a spațiului, creând o partiție spațială binară la fiecare nivel al arborelui.
Așa arată o regiune tridimensională a spațiului partiționată de un arbore kd tridimensional [1]:
Un arbore kd tridimensional. Prima divizare (roșie) taie celula rădăcină (albă) în două subcelule, fiecare dintre acestea fiind apoi împărțită (verde) în două subcelule. În cele din urmă, fiecare dintre aceste patru este împărțit (albastru) în două subcelule. Deoarece nu mai există divizare, ultimele opt sunt numite celule frunze.
Și cum este construit arborele?
Pentru început, aveți un set de puncte într-un spațiu k-dimensional.Să ne oferim un exemplu de arbore kd bidimensional:
Intrare: (2,3), (5,4), (9,6), (4,7), (8, 1), (7,2)
Ieșire: Un arbore kd bidimensional [2]:
În cazul arborilor binari de căutare, partiția binară a liniei reale la fiecare nod intern este reprezentată de un punct pe linia reală. În mod similar, în cazul unui arbore kd bidimensional, partiția binară a planului cartesian bidimensional la fiecare nod intern este reprezentată de un linie în plan.
Deci, în cazul din arborii de căutare binari, punctul reprezentat de nodul intern servește ca punct folosit pentru partiționarea liniei reale. Cum alegem o linie de partiționare în cazul arborilor kd 2 dimensiuni?
În esență , puteți alege orice linie care trece prin punctul reprezentat de nodul intern să partiționăm planul cartesian bidimensional.
Ieșirea arborelui kd de mai sus a fost construită folosind o metodă simplă pentru alegerea liniei de partiționare la fiecare nod intern al arborelui: –
Nivel 0 : – Alegeți linia de partiționare perpendiculară pe prima dimensiune ( X în acest caz) și trecând prin punctul reprezentat de nodul în cauză.
Nivel 1 : – Alegeți linia de partiționare perpendicular pe a doua dimensiune ( Y în acest caz) și trecând prin punctul reprezentat de nodul în cauză.
: : :
Nivel k-1 : – Alegeți linia de partiționare perpendiculară pe kth dimension și trecând prin punctul reprezentat de către nodul în cauză. Nivel k : – Alegeți linia de partiționare perpendiculară pe prima dimensiune ( X în acest caz) și trecând prin punctul reprezentat de nodul în cauză.
Deci, practic, la fiecare nivel alternăm între dimensiunile X și Y pentru a alege o linie de partiționare la fiecare nod intern al arborelui kd.
Etichetele pe care le vedeți lângă fiecare dintre nodurile arborelui kd [2] reprezintă alegerea dimensiunii pentru linia de partiționare la nodurile de la acel nivel.
Let ” Vedem acum cum împarte arborele nostru cu 2 dimensiuni planul cu 2 dimensiuni [3]:
Bine, cum pot efectua căutarea?
„Nu voi spune că„ voi lăsa asta la latitudinea ta, dar tu ” Va trebui să vă ajutați cu alte resurse pentru a o înțelege complet. Cu toate acestea, vă pot spune că această partiționare spațială printr-un arbore kd vă poate ajuta să găsiți cel mai apropiat vecin de un punct specific din spațiu fără a fi nevoie să explorăm toate partițiile care este ceea ce aveam nevoie, pentru a face raportare în timp real pentru Social Cop.
Pentru a înțelege cel mai apropiat algoritm vecin pe copacii kd, iată o resursă bună: http://www.stanford.edu/class/cs106l/handouts/assignment-3-kdtree.pdf
Permiteți-mi să vă trec rapid prin unele dintre celelalte aplicații ale copacilor kd, deoarece cea mai mare parte a fundalului copacilor kd a fost deja acoperită în discuția primei aplicații.
2. Interogări în baza de date care implică o cheie de căutare multidimensională
O interogare care solicită toți angajații din grupa de vârstă (40, 50) și câștigă un salariu în intervalul (15000, 20000) pe lună poate fi transformată într-o problemă geometrică în care vârsta este reprezentată de-a lungul axei x iar salariul este trasat de-a lungul axei y [4]
[4] Axa x indică vârsta de angajatul în ani , iar axa y indică salariul lunar în mii de rupii .
Un arbore kd bidimensional pe indexul compozit al (vârstă, salariu) vă poate ajuta să căutați eficient toți angajații care se încadrează în regiunea dreptunghiulară a spațiului definită de interogarea descrisă mai sus.
3. n-body Problem [5]
Cum putem simula în mod eficient mișcările unei colecții de obiecte care se mișcă sub atracție gravitațională reciprocă?
Metoda naivă ar presupune calcularea forței gravitaționale dintre un obiect datorată fiecărui alt obiect pentru a simula mișcarea acestuia sub atracția gravitațională. Mai mult, ar trebui să o facem pentru fiecare obiect care ar dura O (n ^ 2) timp.
Cu toate acestea, folosind copaci k-d, putem împărți spațiul și, pentru fiecare subdiviziune a spațiului, putem afla efectul total al acestuia asupra restului spațiului. Mai jos este pseudo codul [6] al algoritmului.
Puneți obiectele într-un copac. Începeți de la nivelul inferior al copacului, pentru fiecare regiune la o adâncime d din copac: dacă un copil are frunze, calculați interacțiunea direct Calculați ” Extindere multipolă „Convertiți-o într-o expansiune locală pentru nodul părinte și transmiteți-o. Treceți la nivelul d-1. Când ajungem în vârful copacului, recurgeți înapoi în jos, însumând expansiunile locale.
4. Reducerea culorii [7]
Ce este un mod inteligent de a alege 256 de culori pentru a reprezenta o imagine color?
Metoda naivă ar putea fi de a prelua culorile care sunt utilizate cel mai des.
O metodă mai eficientă, totuși, ar putea reprezenta culorile în ceea ce privește valorile RGB și construiește un arbore kd 3 dimensiuni pentru a împărți spațiul care conține toate culorile imaginii. Construcția arborelui k-d s-ar opri atunci când numărul nodurilor frunzei va fi egal cu 256. Media valorii RGB a fiecăreia dintre cele 256 partiții ar putea fi apoi utilizată pentru a obține o paletă de 256 de culori pentru imaginea color completă.
Referințe: [1], [2], [3]: http://en.wikipedia.org/wiki/Kd-tree [4]: Clasificare utilizând vecinii cei mai apropiați [5], [6], [7] : Arbori kD