Math
Largeur et profondeur
Deux copies d'un labyrinthe, deux parcours, une case par tic. La couche où la largeur trouve une case EST la distance la plus courte : une identité. La profondeur n'est jamais plus courte, et de combien elle l'est dépend de la destination.
Ce qui se passe
Un labyrinthe, deux recherches, une découverte par pas. À gauche, le parcours en largeur prend les cases dans une FILE - premier entré, premier sorti -, il s'étend donc en anneaux, et l'anneau où il trouve une case est sa distance la plus courte : dans un labyrinthe non pondéré, le parcours en largeur EST la recherche du plus court chemin. À droite, le parcours en profondeur les prend dans une PILE - dernier entré, premier sorti -, il plonge donc dans le premier tournant et ne recule qu'au cul-de-sac ; son chemin est un chemin, sans promesse d'être court. Les cases bleues attendent dans la structure, les gris-vert sont terminées, le carré doré est en cours d'expansion, et sous chaque labyrinthe la vraie file et la vraie pile sont listées, la case suivante en premier. Dessinez des murs, cliquez dans un labyrinthe pour prédire où va ensuite cette recherche, puis avancez d'un pas. Si le but est emmuré, les deux recherches s'arrêtent au bord de la composante du départ et le disent.
Équations du module
Équations labyrinthe sur une grille m x m, quatre voisins, départ dans le coin supérieur gauche ; ordre des voisins haut, droite, bas, gauche - le même dans les deux recherches en largeur : la couche sur laquelle une cellule est trouvée EST la longueur du plus court chemin - une identité, vérifiée par rapport à une relaxation INDÉPENDANTE jusqu'à un point fixe et, sur de petites grilles, par rapport à une énumération complète des chemins simples grille vide : distance à (i, j) = i + j ; cellules à la distance d = min(d, m−1) − max(0, d−m+1) + 1 ; couche la plus large = m pour d = m − 1 ; coin opposé = 2(m−1) = 40 pour m = 21 les deux recherches couvrent le MÊME ensemble - la composante du départ, comptée indépendamment par une forêt d'ensembles disjoints - et chacune regarde chaque arête deux fois : 2|E| = 1196 pour 21x21 avec 20 % de murs la recherche en profondeur n'est jamais plus courte, et de combien elle est plus longue dépend de la CELLULE : jusqu'au coin opposé d'une grille vide elle prend les mêmes 2(m−1) pas, jusqu'à la cellule située un pas sous le départ elle en prend 421 pour m = 21 sur une grille vide l'arbre de la recherche en profondeur est un CHEMIN HAMILTONIEN - chaque cellule a au plus un enfant, la plus profonde est à m²−1, et la parité décide où le serpent finit : (1,0) pour m pair, (m−1,0) pour m impair 21x21, 20 % de murs, but dans le coin opposé : largeur 40 pas après avoir touché 370 cellules ; profondeur 50 pas après avoir touché 53 - toutes deux paient, mais en monnaie différente le même labyrinthe, but au centre : largeur 20, profondeur 156 ; et sur 297 des 371 cellules atteignables le chemin en profondeur est au moins trois fois plus long
