Algorithme de Prim

L’algorithme de Prim

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

Si vous voyez des fautes d’orthographe ou des corrections à apporter signalez-le moi je me ferai un plaisir de vous écouter !

L’algorithme de Prim : il faut une place mémoire équivalente à la taille du labyrinthe. Tout au long de la création, chaque cellule est dans l’un de ces 3 états :

  1. « Dedans » : la cellule est une partie du labyrinthe et on a déjà creusé dedans au moins une fois ;
  2. « Frontière » : la cellule n’est pas une partie du labyrinthe et on n’a pas encore creusé dedans, mais est à côté d’une cellule de type (1) ;
  3. « Vierge »: la cellule n’est ni « Dedans » ni « Frontière ».

Commencez par choisir une cellule « Vierge » au hasard, marquez la comme « Dedans », puis marquez tous ses voisins en tant que « Frontière ». Le labyrinthe est terminé lorsqu’il n’y a plus de cellules « Frontière » (ce qui signifie par conséquent qu’il n’y a plus de cellules « Vierges », elles sont toutes « Dedans »). Cet algorithme génère des labyrinthes avec un facteur « rivière » très bas, plein de petits culs-de-sac, et la solution est rapide à trouver en général. Lorsqu’il est correctement implémenté, c’est l’algorithme le plus rapide, en seconde position après celui d’Eller.

Publié dans

3 comments

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>

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.