Meilleure réponse
Différence entre la structure de données graphique et arborescente:
Graphique
- Dans le graphe, il peut y avoir plus dun chemin, cest-à-dire que le graphe peut avoir des chemins unidirectionnels ou bidirectionnels entre les nœuds.
- Dans le graphe, il ny a pas de concept de root node.
- Le graphe peut avoir des boucles, des circuits ainsi que des auto-boucles.
- Dans Graph, il ny en a pas relation parent-enfant.
- Les graphiques sont plus complexes que les arbres car ils peuvent avoir des cycles, des boucles, etc.
- Le graphique est parcouru par DFS : première recherche en profondeur et dans BFS : algorithme de première recherche en largeur.
- Le graphique peut être cyclique ou acyclique.
- Il existe principalement deux types de graphiques: les graphiques dirigés et non dirigés.
- Application graphique lications: coloration des cartes, algorithmes, coloration des graphes, planification des travaux, etc. des arêtes dépendent du graphe.
- Le graphe est un modèle de réseau.
Arbres
- Larbre est une forme spéciale de graphe, cest-à-dire un graphe minimalement connecté et nayant quun seul chemin entre deux sommets.
- Larbre est un cas particulier de graphe nayant ni boucles, ni circuits, ni auto-boucles.
- Dans larborescence, il y a exactement une racine nœud et chaque enfant nont quun seul parent.
- Dans les arbres, il existe une relation parent-enfant, donc le flux peut être là avec la direction de haut en bas ou vice versa.
- Les arbres sont moins complexes que les graphiques car ils nont pas de cycles, pas dauto-boucles et sont toujours connectés.
- La traversée darbre est une sorte de cas particulier de traversée du graphique. Larbre est parcouru en Pré-commande , En ordre et Post-commande (les trois dans DFS ou dans BFS )
- Les arbres entrent dans la catégorie des DAG: les graphes acycliques dirigés sont une sorte de graphe orienté qui nont pas de cycles.
- Différents types darbres sont: Arbre binaire , Arbre de recherche binaire, arbre AVL, tas.
- Applications darborescence : tri et recherche comme la traversée darbre et la recherche binaire.
- Larbre a toujours n-1 bords.
- Arbre est un modèle hiérarchique.
Réponse
Ainsi, les arbres kd, à première vue, peuvent sembler plus théoriques que pratiques par nature. Mais ce nest vraiment pas le cas.
Les arbres kd contiennent une variété dapplications importantes, dont certaines incluent:
1 . Recherche de voisin le plus proche
Supposons que vous ayez lintention de créer un Social Cop sur votre smartphone. Social Cop aide les gens à signaler les crimes au poste de police le plus proche en temps réel.
Alors quest-ce qui semble être un problème ici?
Oui, vous lavez bien deviné. Nous devons rechercher le poste de police le plus proche du lieu du crime avant de tenter de signaler quoi que ce soit.
Comment pourrions-nous le faire rapidement ?
Il semble que les arbres k-d peuvent vous aider à trouver le voisin le plus proche dun point sur une carte à deux dimensions de votre ville. Tout ce que vous avez à faire est de construire un arbre kd en 2 dimensions à partir des emplacements de tous les postes de police de votre ville, puis dinterroger larbre kd pour trouver le poste de police le plus proche de nimporte quel endroit donné de la ville.
Daccord, jai ce quils peuvent faire. Mais comment font-ils?
Si vous savez déjà comment fonctionnent les arbres de recherche binaires , comprendre comment fonctionnent les arbres kd être rien de nouveau. Les arbres k-d aident à partitionner lespace tout comme les arbres de recherche binaires aident à partitionner la ligne réelle . Les arbres k-d partitionnent récursivement une région despace, créant une partition despace binaire à chaque niveau de larborescence.
Voici à quoi ressemble une région despace en 3 dimensions partitionnée par un arbre kd en 3 dimensions [1]:
Un arbre kd en 3 dimensions. La première division (rouge) coupe la cellule racine (blanche) en deux sous-cellules, dont chacune est ensuite divisée (verte) en deux sous-cellules. Enfin, chacun de ces quatre est divisé (bleu) en deux sous-cellules. Puisquil ny a plus de division, les huit dernières sont appelées cellules feuilles.
Et comment larbre est-il construit?
Pour commencer, vous avez un ensemble de points dans un espace à k dimensions.Donnons-nous un exemple darbre kd à 2 dimensions:
Entrée: (2,3), (5,4), (9,6), (4,7), (8, 1), (7,2)
Résultat: Un arbre kd à 2 dimensions [2]:
Dans le cas darbres de recherche binaires, la partition binaire de la ligne réelle à chaque nœud interne est représentée par un point sur la ligne réelle. De même, dans le cas dun arbre kd à 2 dimensions, la partition binaire du plan cartésien à 2 dimensions à chaque nœud interne est représentée par un ligne dans le plan.
Donc, au cas où des arbres de recherche binaires, le point représenté par le nœud interne sert de point utilisé pour partitionner la ligne réelle. Comment choisir une ligne de partitionnement dans le cas darbres kd à 2 dimensions?
Essentiellement , vous pouvez choisir nimporte quelle ligne passant par le point représenté par le nœud interne pour partitionner le plan cartésien à 2 dimensions.
La sortie de larbre kd ci-dessus a été construite en utilisant une méthode simple pour choisir la ligne de partitionnement à chaque nœud interne de larbre: –
Niveau 0 : – Choisissez la ligne de partitionnement perpendiculaire à la première dimension ( X dans ce cas) et en passant par le point représenté par le nœud en question.
Niveau 1 : – Choisissez la ligne de partitionnement perpendiculaire à la deuxième dimension ( Y dans ce cas) et passant par le point représenté par le nœud en question.
: : :
Niveau k-1 : – Choisissez la ligne de partition perpendiculaire à la kème dimension et passant par le point représenté par le nœud en question. Niveau k : – Choisissez la ligne de partitionnement perpendiculaire à la première dimension ( X dans ce cas) et en passant par le point représenté par le nœud en question.
Donc en gros, à chaque niveau on alterne entre les dimensions X et Y afin de choisir une ligne de partitionnement à chaque nœud interne de larbre kd.
Les étiquettes que vous voyez à côté de chacun des nœuds de larbre kd [2] représentent le choix de la dimension de la ligne de partitionnement aux nœuds de ce niveau.
Soit » Voyons maintenant comment notre arbre kd à 2 dimensions partitionne le plan à 2 dimensions [3]:
Très bien, comment puis-je effectuer la recherche?
Je « ne dirai pas que je » laisserai cela à vous, mais à vous » ll devra prendre laide dautres ressources pour le comprendre complètement. Je peux cependant vous dire que ce partitionnement de lespace par un arbre kd peut vous aider à trouver le voisin le plus proche dun point spécifique de lespace sans avoir besoin dexplorer toutes les partitions , ce dont nous avions besoin, pour faire des rapports en temps réel pour Social Cop.
Afin de comprendre lalgorithme du plus proche voisin sur les arbres kd, voici une bonne ressource: http://www.stanford.edu/class/cs106l/handouts/assignment-3-kdtree.pdf
Permettez-moi de vous expliquer rapidement certaines des autres applications des arbres kd, car la plupart des arrière-plans des arbres kd ont déjà été traités dans la discussion de la première application.
2. Requêtes de base de données impliquant une clé de recherche multidimensionnelle
Une requête demandant tous les employés de la tranche dâge (40, 50) et gagnant un salaire de lordre de (15000, 20000) par mois peut être transformée en un problème géométrique où lâge est tracé le long de laxe des x et le salaire est tracé le long de laxe des y [4]
[4] Laxe des x indique lâge de lemployé en ans , et laxe des y indique le salaire mensuel en mille roupies .
Un arbre kd à deux dimensions sur lindice composite de (âge, salaire) pourrait vous aider à rechercher efficacement tous les employés qui se trouvent dans la région rectangulaire de lespace définie par la requête décrite ci-dessus.
3. Problème n-corps [5]
Comment pouvons-nous simuler efficacement les mouvements dune collection dobjets se déplaçant sous lattraction gravitationnelle mutuelle?
La méthode naïve impliquerait de calculer la force gravitationnelle entre un objet due à tous les autres objets afin de simuler son mouvement sous attraction gravitationnelle. De plus, nous devrions le faire pour chaque objet qui prendrait un temps O (n ^ 2).
En utilisant des arbres k-d, cependant, nous pouvons partitionner lespace et pour chaque subdivision de lespace, déterminer son effet total sur le reste de lespace. Ci-dessous le pseudo code [6] de lalgorithme.
Mettez les objets dans un arbre. Commencez au niveau inférieur de larborescence, Pour chaque région à une profondeur d dans larborescence: si des enfants sont des feuilles, calculez directement linteraction Calculez le » Expansion multipolaire « Convertissez-la en une expansion locale pour le nœud parent et transmettez-la. Passez au niveau d-1. Lorsque nous atteignons le sommet de larbre, redescendez larbre, en additionnant les extensions locales.
4. Réduction des couleurs [7]
Quest-ce que une façon intelligente de choisir 256 couleurs pour représenter une image en couleur?
La méthode naïve pourrait être de choisir les couleurs qui sont les plus utilisées.
Une méthode plus efficace, cependant, pourrait représenter les couleurs en fonction de leur RVB et construisez un arbre kd en 3 dimensions afin de diviser lespace contenant toutes les couleurs de limage. La construction de larbre k-d sarrêterait lorsque le nombre des nœuds feuilles deviendrait égal à 256. La moyenne de la valeur RVB de chacune des 256 partitions pourrait alors être utilisée pour obtenir une palette de 256 couleurs pour limage en couleurs.
Références: [1], [2], [3]: http://en.wikipedia.org/wiki/Kd-tree [4]: Classification utilisant les voisins les plus proches [5], [6], [7] : Arbres kD