Aller au contenu

Labyrinthe et algorithme de Kruskal⚓︎

On souhaite dans cet exercice dessiner des labyrinthes rectangulaires :

📋 Texte
 ___________________
|       | |  ____  _|
| | |_|__  _| |__  _|
|_|  _|____ |__  __ |
|_________|___|_|___|

Un labyrinthe sera représenté en machine par une liste de listes Python. Dans la liste lab, pour chaque couple de coordonnées (i, j), lab[i][j] sera un objet de type Cellule possédant trois attributs :

  • un booléen est indiquant si le mur à l'est de cette cellule est présent ou non (True par défaut),
  • un booléen sud indiquant si le mur au sud de cette cellule est présent ou non (True par défaut),
  • un entier zone donnant la zone à laquelle appartient cette cellule. Deux cellules sont dans la même zone s'il existe un chemin menant de l'une à l'autre dans le labyrinthe.

Remarque

Les cellules n'ont que deux murs et pas quatre afin d'éviter les doublons (le mur au sud d'une cellule pourrait correspondre au mur au nord de la cellule du dessous...).

Lors du dessin du labyrinthe, les murs au nord de la première ligne et à l'ouest de la première colonne seront dessinés par défaut.

🐍 Script Python
class Cellule:
    def __init__(self, zone):
        self.est = True
        self.sud = True
        self.zone = zone

La fonction base_labyrinthe permet de créer un labyrinthe dont tous les murs sont pleins. Elle prend en argument deux entiers strictement positifs, la hauteur hauteur et la largeur largeur du labyrinthe.

🐍 Script Python
def base_labyrinthe(hauteur, largeur):
    lab = []
    for i in range(hauteur):
        ligne = [Cellule(i * largeur + j) for j in range(largeur)]
        lab.append(ligne)
    return lab

Initialement, chaque cellule du labyrinthe est fermée sur elle-même : toutes les cellules sont donc initialement dans des zones différentes.

On peut accéder aux différentes cellules en procédant ainsi :

🐍 Console Python
>>> # Création de la base d'un labyrinthe de hauteur 4 et largeur 10
>>> lab = base_labyrinthe(4, 10)
>>> # Le mur à l'est de la cellule en haut à gauche est présent
>>> lab[0][0].est
True
>>> # La cellule de la 3ème ligne, 8ème colonne est dans la zone 26
>>> lab[2][7].zone
26

La fonction dessin_console renvoie la chaîne de caractères représentant le labyrinthe passé en argument :

🐍 Console Python
>>> print(dessin_console(lab))
 ___________________
|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|

Une variante de l'algorithme de Kruskal permet de construire des labyrinthes dans lesquels toutes les cellules appartiennent à la même zone et ne comportant pas de « boucles ».

On débute avec un labyrinthe dans lequel tous les murs sont présents. Au fil du traitement, on retire des murs de façon à fusionner des zones distinctes.

Les étapes de l'algorithme sont les suivantes :

  • créer un labyrinthe dans lequel tous les murs sont présents ;
  • créer la liste de tous les murs ;
  • mélanger cette liste ;
  • récupérer (et supprimer) le dernier mur de la liste jusqu'à ce qu'elle soit vide :
    • si ce mur sépare deux cellules de la même zone, ne rien faire,
    • s'il sépare deux cellules de zones différentes :
      • supprimer ce mur,
      • fusionner les zones correspondantes.

La dernière étape est importante : il faut non seulement faire en sorte que les deux cellules séparées par le mur soient dans la même zone mais aussi toutes les cellules communicantes. Ainsi, si l'on supprime un mur entre une zone de 5 cellules et une autre de 3 cellules, on obtiendra une nouvelle zone de 8 cellules.

La figure ci-dessous illustre la fusion de plusieurs zones (la construction du labyrinthe n'est pas terminée à la fin de l'animation).

Fusion de zones

La fonction murs_aleatoires prend en argument les dimensions du labyrinthe (hauteur et largeur) et renvoie la liste mélangée de ses murs sous la forme d'une liste de triplets (i, j, orientation). Le triplet (2, 7, "est") désignera par exemple le mur à l'est de la cellule de coordonnées (2, 7).

Cette fonction renvoie l'ensemble des murs « intérieurs » du labyrinthe : les murs à l'est des cellules de la dernière colonne et ceux au sud de la dernière ligne ne figurent pas dans la liste.

Pour faciliter la correction du code l'aspect « aléatoire » est limité et la fonction murs_aleatoires renvoie toujours le même mélange pour des dimensions données.

Remarque

Toutes les classes et fonctions citées plus haut :

  • Cellule,
  • base_labyrinthe,
  • dessin_console,
  • murs_aleatoires

sont déjà chargées en mémoire. Il est inutile de les retaper.

Compléter la fonction labyrinthe prenant en argument deux entiers strictement positifs hauteur et largeur et renvoyant le labyrinthe obtenu grâce à l'algorithme de Kruskal.

Exemple

🐍 Console Python
>>> HAUTEUR, LARGEUR = 4, 10
>>> lab = labyrinthe(HAUTEUR, LARGEUR)
>>> print(dessin_console(lab))
 ___________________
|  _____|  ___|  __ |
| |  ___|  ____  _| |
|   |  ____ | |___|_|
|_|_____|___________|
# Testbksl-nlHAUTEUR, LARGEUR = 4, 10bksl-nllab = labyrinthe(HAUTEUR, LARGEUR)bksl-nlassert (bksl-nl dessinpy-undconsole(lab)bksl-nl == """bksl-nl py-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undbksl-nl| py-und| py-undpy-undpy-und| |py-undpy-und | |bksl-nl|py-und| py-und|py-undpy-und |py-undpy-und py-undpy-undpy-undpy-undpy-und|bksl-nl| |py-undpy-undpy-undpy-und | | |bksl-nl|py-und|py-und|py-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-und|py-und|py-undpy-undpy-und|bksl-nl"""bksl-nl)bksl-nlbksl-nl# Tests supplémentairesbksl-nlHAUTEUR, LARGEUR = 4, 4bksl-nllab = labyrinthe(HAUTEUR, LARGEUR)bksl-nlassert (bksl-nl dessinpy-undconsole(lab)bksl-nl == """bksl-nl py-undpy-undpy-undpy-undpy-undpy-undpy-undbksl-nl| | py-undpy-und |bksl-nl| |py-undpy-undpy-und| |bksl-nl| py-undpy-undpy-und|bksl-nl|py-und|py-undpy-undpy-undpy-undpy-und|bksl-nl"""bksl-nl)bksl-nlbksl-nlHAUTEUR, LARGEUR = 5, 5bksl-nllab = labyrinthe(HAUTEUR, LARGEUR)bksl-nlassert (bksl-nl dessinpy-undconsole(lab)bksl-nl == """bksl-nl py-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undbksl-nl|py-undpy-und |py-undpy-und py-und|bksl-nl|py-undpy-undpy-undpy-und |bksl-nl|py-undpy-und py-und|py-und|py-und|bksl-nl| py-undpy-undpy-undpy-und py-und|bksl-nl|py-undpy-undpy-und|py-undpy-undpy-undpy-undpy-und|bksl-nl"""bksl-nl)bksl-nlbksl-nlHAUTEUR, LARGEUR = 10, 10bksl-nllab = labyrinthe(HAUTEUR, LARGEUR)bksl-nlassert (bksl-nl dessinpy-undconsole(lab)bksl-nl == """bksl-nl py-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undbksl-nl| py-undpy-und py-und| | py-und|py-undpy-und |bksl-nl|py-und| py-und| py-undpy-undpy-und| py-und| |bksl-nl|py-undpy-und py-und|py-und|py-undpy-und py-und|py-undpy-und |py-und|bksl-nl| py-undpy-und py-undpy-undpy-undpy-undpy-undpy-und |bksl-nl|py-und| py-und|py-und| |py-und| py-undpy-undpy-undpy-und |bksl-nl| |py-und| | | | |py-undpy-undpy-und|py-undpy-undpy-und|bksl-nl| py-undpy-undpy-undpy-und py-und|py-undpy-und |py-undpy-und |bksl-nl|py-undpy-und |py-und| py-undpy-undpy-undpy-und |bksl-nl| py-und|py-undpy-und |py-und| py-und|py-und| | |bksl-nl|py-undpy-undpy-und|py-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-und|py-undpy-undpy-und|py-und|bksl-nl"""bksl-nl)bksl-nlbksl-nl ∞/∞

#--- HDR ---#bksl-nlimport randombksl-nlbksl-nlbksl-nlclass Cellule:bksl-nl def py-undpy-undinitpy-undpy-und(self, zone):bksl-nl self.est = Truebksl-nl self.sud = Truebksl-nl self.zone = zonebksl-nlbksl-nl def py-undpy-undstrpy-undpy-und(self) -> str:bksl-nl if self.est and self.sud:bksl-nl return "py-und|"bksl-nl elif self.est:bksl-nl return " |"bksl-nl elif self.sud:bksl-nl return "py-undpy-und"bksl-nl else:bksl-nl return " "bksl-nlbksl-nl def py-undpy-undreprpy-undpy-und(self) -> str:bksl-nl return self.py-undpy-undstrpy-undpy-und()bksl-nlbksl-nlbksl-nldef basepy-undlabyrinthe(hauteur, largeur):bksl-nl lab = []bksl-nl for i in range(hauteur):bksl-nl ligne = [Cellule(i py-str largeur + j) for j in range(largeur)]bksl-nl lab.append(ligne)bksl-nl return labbksl-nlbksl-nlbksl-nldef dessinpy-undconsole(labyrinthe):bksl-nl lignes = ["\n " + "py-undpy-und" py-str (LARGEUR - 1) + "py-und"]bksl-nl for i in range(HAUTEUR):bksl-nl ligne = ["|"] + [str(labyrinthe[i][j]) for j in range(LARGEUR)]bksl-nl lignes.append("".join(ligne))bksl-nl dessin = "\n".join(lignes) + "\n"bksl-nl return dessinbksl-nlbksl-nlbksl-nldef murspy-undaleatoires(hauteur, largeur, graine=1):bksl-nl murs = []bksl-nl for i in range(hauteur - 1):bksl-nl for j in range(largeur - 1):bksl-nl murs.append((i, j, "est"))bksl-nl murs.append((i, j, "sud"))bksl-nl for i in range(hauteur - 1):bksl-nl murs.append((i, largeur - 1, "nord"))bksl-nl for j in range(largeur - 1):bksl-nl murs.append((hauteur - 1, j, "est"))bksl-nl random.seed(graine)bksl-nl random.shuffle(murs)bksl-nl return mursbksl-nlbksl-nlbksl-nl#--- HDR ---#bksl-nldef labyrinthe(hauteur, largeur):bksl-nl # Initialisationbksl-nl lab = basepy-undlabyrinthe(hauteur, largeur)bksl-nl murs = murspy-undaleatoires(hauteur, largeur)bksl-nlbksl-nl # Traitementbksl-nl while ... != 0:bksl-nl i1, j1, orientation = murs.pop()bksl-nl ...bksl-nlbksl-nl return labbksl-nlbksl-nlbksl-nl# Testbksl-nlHAUTEUR, LARGEUR = 4, 10bksl-nllab = labyrinthe(HAUTEUR, LARGEUR)bksl-nlassert (bksl-nl dessinpy-undconsole(lab)bksl-nl == """bksl-nl py-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undbksl-nl| py-und| py-undpy-undpy-und| |py-undpy-und | |bksl-nl|py-und| py-und|py-undpy-und |py-undpy-und py-undpy-undpy-undpy-undpy-und|bksl-nl| |py-undpy-undpy-undpy-und | | |bksl-nl|py-und|py-und|py-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-und|py-und|py-undpy-undpy-und|bksl-nl"""bksl-nl)bksl-nlbksl-nlimport randombksl-nlbksl-nlbksl-nlclass Cellule:bksl-nl def py-undpy-undinitpy-undpy-und(self, zone):bksl-nl self.est = Truebksl-nl self.sud = Truebksl-nl self.zone = zonebksl-nlbksl-nl def py-undpy-undstrpy-undpy-und(self) -> str:bksl-nl if self.est and self.sud:bksl-nl return "py-und|"bksl-nl elif self.est:bksl-nl return " |"bksl-nl elif self.sud:bksl-nl return "py-undpy-und"bksl-nl else:bksl-nl return " "bksl-nlbksl-nl def py-undpy-undreprpy-undpy-und(self) -> str:bksl-nl return self.py-undpy-undstrpy-undpy-und()bksl-nlbksl-nlbksl-nldef basepy-undlabyrinthe(hauteur, largeur):bksl-nl lab = []bksl-nl for i in range(hauteur):bksl-nl ligne = [Cellule(i py-str largeur + j) for j in range(largeur)]bksl-nl lab.append(ligne)bksl-nl return labbksl-nlbksl-nlbksl-nldef dessinpy-undconsole(lab):bksl-nl hauteur, largeur = len(lab), len(lab[0])bksl-nl lignes = ["\n " + "py-undpy-und" py-str (largeur - 1) + "py-und"]bksl-nl for i in range(hauteur):bksl-nl ligne = ["|"] + [str(lab[i][j]) for j in range(largeur)]bksl-nl lignes.append("".join(ligne))bksl-nl dessin = "\n".join(lignes) + "\n"bksl-nl return dessinbksl-nlbksl-nlbksl-nldef murspy-undaleatoires(hauteur, largeur, graine=1):bksl-nl murs = []bksl-nl for i in range(hauteur - 1):bksl-nl for j in range(largeur - 1):bksl-nl murs.append((i, j, "est"))bksl-nl murs.append((i, j, "sud"))bksl-nl for i in range(hauteur - 1):bksl-nl murs.append((i, largeur - 1, "nord"))bksl-nl for j in range(largeur - 1):bksl-nl murs.append((hauteur - 1, j, "est"))bksl-nl random.seed(graine)bksl-nl random.shuffle(murs)bksl-nl return mursbksl-nlbksl-nlbksl-nldef labyrinthe(hauteur, largeur):bksl-nl lab = basepy-undlabyrinthe(hauteur, largeur)bksl-nl murs = murspy-undaleatoires(hauteur, largeur)bksl-nlbksl-nl while len(murs) != 0:bksl-nl i1, j1, orientation = murs.pop()bksl-nl if orientation == "est":bksl-nl di = 0bksl-nl dj = 1bksl-nl else:bksl-nl di = 1bksl-nl dj = 0bksl-nl i2 = i1 + dibksl-nl j2 = j1 + djbksl-nl if lab[i1][j1].zone != lab[i2][j2].zone:bksl-nl if orientation == "est":bksl-nl lab[i1][j1].est = Falsebksl-nl else:bksl-nl lab[i1][j1].sud = Falsebksl-nlbksl-nl nouvellepy-undzone = lab[i1][j1].zonebksl-nl anciennepy-undzone = lab[i2][j2].zonebksl-nl for i in range(hauteur):bksl-nl for j in range(largeur):bksl-nl if lab[i][j].zone == anciennepy-undzone:bksl-nl lab[i][j].zone = nouvellepy-undzonebksl-nlbksl-nl return labbksl-nlbksl-nlbksl-nl# Testbksl-nlHAUTEUR, LARGEUR = 4, 10bksl-nllab = labyrinthe(HAUTEUR, LARGEUR)bksl-nlassert (bksl-nl dessinpy-undconsole(lab)bksl-nl == """bksl-nl py-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undbksl-nl| py-und| py-undpy-undpy-und| |py-undpy-und | |bksl-nl|py-und| py-und|py-undpy-und |py-undpy-und py-undpy-undpy-undpy-undpy-und|bksl-nl| |py-undpy-undpy-undpy-und | | |bksl-nl|py-und|py-und|py-undpy-undpy-undpy-undpy-undpy-undpy-undpy-undpy-und|py-und|py-undpy-undpy-und|bksl-nl"""bksl-nl)bksl-nlbksl-nl

A

Commentaires⚓︎

{{ IDE('exo_corr') }}

L'algorithme⚓︎

L'algorithme de Kruskal est un algorithme permettant de construire un arbre couvrant minimal associé à graphe pondéré.

Dans son fonctionnement classique, on parcourt les arêtes du graphe dans l'ordre de leurs poids croissants. Dans la version proposée ici, le parcours se fait dans un ordre aléatoire.

L'étape compliquée de l'algorithme est la fusion des zones. Le choix proposé ici de stocker la zone de chaque cellule comme attribut de celle-ci n'est pas le plus efficace en termes de complexité : à chaque fusion on doit parcourir l'ensemble des cellules.

On pourrait procéder autrement en utilisant par exemple des ensembles, set avec Python, mais cette structure n'est pas au programme de NSI.

Gestion de l'aléa⚓︎

L'aléatoire est contraint dans cet exercice afin de toujours obtenir les mêmes labyrinthes pour des dimensions données.

Cette contrainte est liée au choix de la graine de l'aléatoire random.seed(graine) qui est ici fixée à 1. Retirer cette ligne fait que Python choisira l'heure actuelle comme graine et génèrera des mélanges pseudo-aléatoires plus vraisemblables. Voir la documentation officielle.

Z

Retour en haut de la page