Skip to content
Snippets Groups Projects

Quelques typos.

Merged MIGNOT JEAN-CHRISTOPHE requested to merge jean-christophe.mig-master-patch-56429 into master
1 file
+ 1
1
Compare changes
  • Side-by-side
  • Inline
+ 10
10
# Structure Union Find et labyrinthes
# Structure Union-Find et labyrinthes
Le but de ce TP est d'aborder le problème de l'Union-Find, et la structure de
données associée, et de l'appliquer pour la création de labyrinthes.
## Union Find
## Union-Find
Le problème de l'union find est de gérer des ensembles disjoints d'objets : un
Le problème de l'union-find est de gérer des ensembles disjoints d'objets : un
objet ne peut pas appartenir à deux ensembles en même temps. Initialement, tous
les objets sont dans leur propre ensemble, qui ne contient qu'eux. Il est
ensuite proposé deux opérations :
@@ -24,8 +24,8 @@ labyrinthes. Cette création de labyrinthes se base sur le principe suivant :
* au début chaque case de la grille est entourée de murs ;
* petit à petit des murs sont abattus pour créer le labyrinthe.
En appliquant naïvement ce principe, il est peu probable que le labyrinthe
obtenu soit intéressant. Tout d'abord, si le nombre de murs n'est pas important,
En n'appliquant que ce principe, il est peu probable que le labyrinthe
obtenu soit intéressant. Tout d'abord, si le nombre de murs abbatus n'est pas grand,
il est peu probable que l'entrée et la sortie du labyrinthe soient accessibles
par un chemin. Ensuite ce procédé va vider le labyrinthe de ses murs sans créer
les recoins tortueux qui rendent les labyrinthes intéressants.
@@ -104,11 +104,11 @@ ensemble, on regarde si les racines de leurs arbres sont identiques.
#### Union
Pour unir deux ensemble, il suffit de s'assurer que deux arbres initialement
Pour unir deux ensembles, il suffit de s'assurer que deux arbres initialement
distincts finissent avec la même racine. Il suffit donc de faire en sorte que le
parent de l'une des deux racines devienne l'autre racine.
Dans l'exemple précédent la fusion des deux premier arbres donnerait donc l'un
Dans l'exemple précédent la fusion des deux premiers arbres donnerait donc l'un
des deux arbres suivants
![exemple de fusion](Images/uf_fusion.png)
@@ -182,7 +182,7 @@ parents de 5 et 4 pour qu'ils se placent directement sous 1.
La complexité d'une recherche dans le pire cas est la hauteur de l'arbre dans
laquelle elle est lancée. Lors de l'union de deux ensembles, il est possible
d'essayer de faire en sorte de n'augmenter les hauteurs des arbres que le moins
possible. Si les deux arbres dont de hauteurs différentes, en spécifiant la
possible. Si les deux arbres sont de hauteurs différentes, en spécifiant la
racine de l'arbre le plus profond comme parente de la racine de l'arbre le moins
profond, la hauteur de l'arbre final est la même que celle de l'arbre le plus
profond. Ce n'est donc que lorsqu'on fusionne deux arbres de mêmes hauteurs
@@ -195,8 +195,8 @@ chemin. Cette approximation est donc toujours pire que la réalité.
Pour stocker les hauteurs, il vous suffit d'ajouter un tableau qui stocke pour
chaque nœud une hauteur. Initialement toutes les hauteurs sont à 1. Lors
d'une fusion, seule les hauteurs des racines sont importantes. Les
hauteurs des nœuds ne restent donc utiles que tant qu'il sont la racine de
d'une fusion, seules les hauteurs des racines sont importantes. Les
hauteurs des nœuds ne restent donc utiles que tant qu'ils sont la racine de
leur arbre. Dès qu'ils se retrouvent sous un parent, il n'est plus nécessaire de
mettre à jour leur hauteur.
Loading