Recherche du nombre de parcour possible dans un cube en 3D

Posté par djanos djanos

Bonsoir
Ma raison de m'a venu est un besoin d'idée pour traiter un problème
Je voudrai réalisé un labyrinthe, contenu dans un cube de dimension 5 × 5 × 5
Je cherche donc a trouver un parcoure passant par tous les cubes unitaires (un peu comme si je cherchais à tracer un parcoure allant d'un bout à l'autre d'une grille 5×5 en passant par toute les cases mais dans l'espace)
La recherche manuelle d'un parcoure est faisable mais longue, coince souvent sur la fin (il reste des cases libre) et surtout, peu intéressante, d'où l'idée de faire un programme qui recherche les différentes possibilité.
J'ai déjà quelques idées pour traiter ce problème mais je pense que des idées extérieurs peuvent être les bienvenus
Tous d'abord, j'aimerai trouver un majorant du nombre de chemin possible
Celui que j'ai trouver est très élevé : 5^125 (un parcoure comporte 125 déplacement d'un cube unitaire à un autre, et pour passer d'un cube à un autre, il y a 5 possibilités, les 5 autres faces du cube unitaire si l'on enlève la face par laquelle on arrive)(On comtpe énormément de parcoures impossible et ne convenant pas (ne passe pas par toute les cases) dont j'aimerai m'affranchir). Cette majoration me permettrai de savoir combien de temps mon programme tournera au maximum. Ici, si on est optimiste et que l'on considère le programme teste 1 parcoure par milisecondes, il lui faudrai 10^76 années.
Ensuite, j'aimerai essayer d'associé une variable à chaque parcoure représentative de "l'aléatoirité" de celui-ci, enfin de trouver un parcoure pas trop facile en ignorant les parcours lorsque la variable est trop faible. Je n'ai pas encore d'idée pour cela.
En attente de vos idées et suggestions smiling smiley

Posté par fatal_error fatal_error

salut,

Ton cube peut se modéliser par un graphe.
Prenons un plan horizontal du cube. Celui-ci contient 25 carrés (base des cubes unitaires). Prenons un sommet commun aux quatre carrés alentours. On dit que c'est un noeud. Il suffit de relier ce noeud à celui qui est sur le plan juste au dessus, et celui sur le plan juste en dessous.

Bon après tu veux passer d'un cube à l'autre. Ben c'est la même chose, sauf qu'au lieu de prendre un noeud sur le plan et a l'intersection de quatre carrés, tu places le noeud au centre du cube!

Concernant l'estimation de tous les chemins possibles sans passer par une case déjà parcourue :
il suffit d'orienter le graphe. (Au début, il est donc double sens). Au fur et à mesure que tu le parcours, tu enlèves des connexions (si tu vas du noeud A vers le noeud B, tu enlèves la connexion du noeud B vers le noeud A). MAIS, comme tu cherches le plus court chemin, il est évident que si tu boucles (A->B->A), alors ton chemin n'est pas le chemin optimal. Donc tu peux parfaitement utiliser Warshall-Floyd ou tout autre algo de prog dynamique, en ne t'occupant pas du problème du retour arrière!

Posté par djanos djanos

merci pour cette réponse
je me lance dans des recherches pour en savoir plus sur la théorie des graphes, l'algorithme de Warshall-Floyd ...
Je ne connaissait pas du tout !
Par contre, je ne cherche pas le chemin le plus court, mais d'un chemin exactement 125 déplacements, vu qu'il doit passer par toute les cases.
Remarque : dans mon cas, si je ne m'occupe pas de revenir en arrière, je doit tester tout les chemins en entier (puis qu'il faut alors repartir du début), c'est contre-productif non ?
Enfaite, je me demandais si il était possible de calculer le nombre de chemin possible, sans les compter un par un :p

Posté par djanos djanos

J'ai fait un programme qui recherche un parcoure : il ce place dans une case de départ, et passe détermine aléatoirement quel est la case suivant contigüe qu'il va visiter. Si cette case à déjà été visiter, alors il fait demi tour et recherche une autre case pas encore visiter. Le problème c'est que j'en suis déjà à une dizaine de millions de déplacement effectué (changement de case, en arrière ou en avant) sans avoir trouver encore un seul parcoure :s
Une idée pour donner une estimation du nombre de parcoure, nombre de parcoure complet...?

Posté par djanos djanos

Il semblerai que mon problème rejoigne les cycle hamiltonien en théorie des graphes
des connaisseurs ?