Labyrinthe et algorithme de Kruskal⚓︎
On souhaite dans cet exercice dessiner des labyrinthes rectangulaires :
___________________
| | | ____ _|
| | |_|__ _| |__ _|
|_| _|____ |__ __ |
|_________|___|_|___|
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.
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.
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 :
>>> # 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 :
>>> 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).
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
>>> HAUTEUR, LARGEUR = 4, 10
>>> lab = labyrinthe(HAUTEUR, LARGEUR)
>>> print(dessin_console(lab))
___________________
| _____| ___| __ |
| | ___| ____ _| |
| | ____ | |___|_|
|_|_____|___________|
#--- 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