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

  1. guillaume

    Bonjour, je souhaiterais écrire en python 3 un programme capable de générer un labyrinthe à l’aide de cet algorithme de Prim. Auriez-vous en stock un script pas trop compliqué permettant de faire ça ? Etant débutant complet j’avoue être un peu perdu, même si je comprends bien l’idée de cet algorithme…Merci dans tous les cas et bravo pour votre blog.

    • Olivier Pons

      Bonjour,

      Malheureusement non, je n’ai aucun script pas trop compliqué, voire aucun script python tout court qui génère un labyrinthe… Je suis désolé, je ne peux pas vous aider plus que ça… 🙁

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>