Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 14-03-2021 18:39:51

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 910
Lieu: Seahaven island

kabyrinthe fractal (création)

Hello!

Ici il s'agit de questions mathématiques sur le concept de labyrinthe fractal


Les détails concernant le jeu lui même et la résolution du labyrinthe en lui même se trouve dans cet autre post:
http://www.prise2tete.fr/forum/viewtopic.php?id=13987

http://www.prise2tete.fr/upload/Clydevil-EwBe8tJWgAApm9H.jpg

Mes questions existentielles:

On peut voir qu'un labyrinthe fractal se caractérise entre autre:
-par le nombre d'entrées externes E qu'il possède.
-par le nombre de copies C de lui même qu'il contient.
Je nomme segment n'importe quel chemin sur un niveau qui peut donc aller de l'extérieur vers l'intérieur (exemple ci dessus de 1 vers A1), de l'exterieur vers l'exterieur (exemple ci dessus de 1 vers 16), de l'intérieur vers l'extérieur, ou de l'intérieur vers l'intérieur (exemple de A5 vers C1, ou de A10 vers A16)

On considère que start et finish sont une des entrées externes de notre choix au top niveau.

Etant donnés les nombres E et C:
Quel est le pire labyrinthe en terme de profondeur (nombre de niveau) et quelle est cette profondeur du pire cas?
Quel est le pire labyrinthe en terme de distance entre start et finish comptées en segments?

Bonne chance!

  • |
  • Répondre

#0 Pub

 #2 - 16-03-2021 20:15:46

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 910
Lieu: Seahaven island

Labyrnithe Fractal (création)

Tips: plus abordable dans un premier temps c'est chercher des constructions simples qui font des "quasi pire cas" pour les 2 questions. Sur la profondeur et sur la longueur en nombre de segments. J'ai personnellement 2 constructions simples qui ne sont peut être pas optimales mais déjà satisfaisamment extrêmes.

 #3 - 23-03-2021 10:58:39

Clydevil
Expert de Prise2Tete
Enigmes résolues : 29
Messages : 910
Lieu: Seahaven island

lavyrinthe fractal (création)

Merci à tous les participants!

Mes résultats:

Sur la profondeur:
On peut déjà montrer facilement qu'elle est bornée par le nombre E (entrées externes), ça se fait en procédant itérativement: on regarde le labyrinthe en se demandant quelles entrées sont liées ensemble en autorisant une profondeur "N", et on injecte ce composant dans lui même (on rajoute une couche de profondeur à l’extérieur), ce qui nous permet de déduire la nouvelle partition des entrées, représentant qui est relié à qui en autorisant N+1 niveaux. Lors de cet itération, on ne peut que "fusionner" des listes d’entrées qui étaient reliées ensemble en autorisant N niveau pour construire les listes d'entrées qui sont maintenant reliées ensemble en autorisant N+1 niveau. Donc au pire on démarre d'une partition ou chaque entrée serait seule (liée à personne en autorisant 0 récursion) et on voit bien qu'en opérant des fusions entre les ensembles de ces partitions on n'en fera qu'au max E (ou alors on aura 2 étapes qui ne changent pas la partition des entrées liées ensemble et du coup ça veut dire qu'elles ne le seront jamais qq soit le nombre d’itération, c'est stable).
Un bon candidat de labyrinthe pour maximiser cela s'obtient en généralisant la partie gauche du petit labyrinthe gris de d'entrainement de l'autre thread (la flemme de dessiner)

Sur la longueur:
Cette construction itérative est déjà très intéressante:
http://www.prise2tete.fr/upload/Clydevil-LongLaby.png
Et ça peut continuer autant qu'on veut et quelque soit le nombre C, il suffit de rajouter des paires d’entrées pour avoir l’itération suivante.
Si C est le nombre de copies du labyrinthe dans lui même, on voit qu'entre une itération et la suivante (un ajout de paire d’entrées selon ce motif de construction) on multiplie le trajet par C et on ajoute C+1 segments.
C'est a dire que pour un labyrinthe avec 12 entrées externes et 4 copies internes, cette construction assure qu'une certaine paire de ses entrées sera liée par un chemin de longueur minimale 2729!

Mais je sais aussi que ce n'est pas le max car certaines constructions sont plus efficaces, par exemple:
http://www.prise2tete.fr/upload/Clydevil-longerLaby.png
Ici on a que E=4 et C=4 et pourtant la distance entre 2 entrées éloignées est de longueur 17! (alors que la construction précédente donnerait seulement 9)

Mais cette construction ne se généralise pas facilement. En fait on se rend compte souvent que la "dernière itération" (dans une construction incrémentale) peut souvent être optimisée mais que c'est au détriment de pouvoir continuer la construction itérative (si on continue cette optimisation fournit un "raccourci" pour les itérations suivante et donc met fin à une construction exponentielle efficace).

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez (numériquement) à la petite énigme suivante : 

Dans une course, vous doublez le 42ème, en quelle position êtes-vous ?

Sujets similaires

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete