Algorithme de Kruskal

Labyrinthes : différents algorithmes

Algorithme de Kruskal

Traduit en Français par moi-même. Les originaux sont ici.

L’algorithme de Kruskal : cet algorithme est intéressant parce qu’il ne « grandit » pas en créant le labyrinthe selon le principe d’un arbre, mais en enlevant des segments de murs au hasard dans tout le labyrinthe, et malgré ce, le labyrinthe est de type Parfait au final. ll requiert un espace mémoire proportionnel à la taille du labyrinthe. Il faut juste avoir la capacité d’énumérer toutes les séparations du labyrinthe et d’en tirer au hasard (habituellement, cela implique de créer une liste de tous les murs et la mélanger). Donnez à chaque cellule un numéro unique (Id), et faite une boucle sur toutes les séparations du labyrinthe aléatoirement. Pour chaque séparation, si les cellules de chaque côté de ce mur ont un Id différent, alors supprimez ce mur, gardez un des deux Ids et appliquez cet Id des deux côtés partout ou vous retrouvez l’un des deux Ids dans le labyrinthe. Si les cellules de chaque côté de la séparation ont déjà le même Id cela signifie qu’il existe déjà un chemin de tracé pour les relier, donc la séparation doit être transformée en mur afin de ne pas créer de boucle. Cet algorithme donne des labyrinthes avec un facteur « rivière » bas, mais pas aussi bas que l’algorithme de Prim. L’opération de « fusion » des Ids peut être lente si elle est mal pensée. Il faut imaginer le labyrinthe en terme d’arbre et, lors de la fusion des « Ids », ne faire que déplacer les cellules dans les bonnes branches, afin de faire une fusion pratiquement instantanée. Bien programmé, cet algorithme est moyennement rapide.

Publié dans

Poster un commentaire

Vous devriez utiliser le HTML:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>