Algorithme Retour-récursif

Labyrinthes : différents algorithmes

Algorithme Retour-récursif

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 !

Retour-récursif (« Recursive backtracker ») : cette méthode nécessite une pile qui doit pouvoir aller jusqu’à la taille totale du nombre de cellules. Lorsque vous creusez, soyez le plus gourmand possible, et creusez toujours dans une cellule sur laquelle vous n’avez jamais été, dans la mesure où elle touche celle qui est en cours. Chaque fois que vous creusez :

  1. Placez la cellule courante en haut de la pile ;
  2. Creusez ;
  3. Si, dans la cellule courante, vous ne pouvez plus creuser (donc il n’y a aucune cellule pas encore faite collée à la cellule courante), retirez la dernière cellule de la liste et considérez la comme la cellule courante.

Le labyrinthe est terminé lorsque votre pile est vide. Cet algorithme crée des labyrinthes avec le facteur « rivière » le plus grand possible, avec moins de cul-de-sac, et une grande distance entre eux, et la solution pour aller de l’un à l’autre est en générale longue et tortueuse. Cet algorithme est assez rapide, même si il l’est moins que l’algorithme de Prim.

Publié dans

One comment

  1. zanzan

    Bonjour,
    excusez-moi de vous déranger, votre article est très intéressant, en particulier en ce qui concerne l’algorithme d’Eller. En effet, j’ai besoin d’un programme utilisant peu de mémoire puisque je programme sur calculette. Malheureusement, je manque de connaissances en anglais pour comprendre correctement la fin de cet algorithme. Excusez-moi si vous étiez justement en train de l’écrire.
    zanzan

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>