Répondre à la discussion
Affichage des résultats 1 à 11 sur 11

Calcul du nombre de chemins possibles dans une grille à 2Dimensions



  1. #1
    morphdown

    Calcul du nombre de chemins possibles dans une grille à 2Dimensions


    ------

    Calcul du nombre de chemins possibles dans une grille à 2Dimensions

    Bonjour,

    Voici la problématique:

    Sur une grille carrée de nxn, comment calculer le nombre de chemins possibles, en partant depuis chacune des cases et ne pouvant passer 1seule fois par case.

    Se problème se pose dans un programme informatique, ou je fais appel a des fonctions récursives qui font tous les chemins possibles.
    Enfaite la grille comporte des lettres, et je dois pouvoir savoir tous les mots qu'il est possible de faire.

    Je voudrais établir une fonction
    f(n)= nb chemins possibles et ou n et la taille de la grille.

    J'ai essaye de mettre ça sous forme mathématique mais c'est vite le cauchemar, à cause des chemins ou le serpent se mort la queue.


    Est-ce qu'une telle formule existe déjà?
    Si une formule générale existe pour n Dimensions, elle est aussi la bienvenue.

    Merci d'avance, Mathématiquez bien!

    -----

  2. Publicité
  3. #2
    invite986312212
    Invité

    Re : Calcul du nombre de chemins possibles dans une grille à 2Dimensions

    salut,

    il faut que tu présises:
    1) les mouvements autorisés (tour, fou, reine?)
    2) les chemins : longueur fixée, extrémités fixées, juste le point de départ, etc.

  4. #3
    morphdown

    Re : Calcul du nombre de chemins possibles dans une grille à 2Dimensions

    PS: oublié de préciser:
    on peut se déplacer Gauche ou Droite, Haut ou Bas
    mais pas en diagonale.


  5. #4
    morphdown

    Re : Calcul du nombre de chemins possibles dans une grille à 2Dimensions

    Déplacement sur les cases voisinnes du haut-bas-gauche-droite
    Point de départ possible depuis n'importe quelle case
    Longueur jusqu'à ce qu'on ne puisse plus bouger ( donc les cases voisinnes sont déja toutes "traversées", ou plus de cases a visiter.

  6. #5
    }{uman

    Re : Calcul du nombre de chemins possibles dans une grille à 2Dimensions

    Salut,
    qu'est ce que t'appelle un chemin? S'arrête-t-il lorsqu'on arrive à l'extremité?

    Cordialement,

  7. A voir en vidéo sur Futura
  8. #6
    }{uman

    Re : Calcul du nombre de chemins possibles dans une grille à 2Dimensions

    Dsl ya déja le réponse

  9. Publicité
  10. #7
    invite986312212
    Invité

    Re : Calcul du nombre de chemins possibles dans une grille à 2Dimensions

    avec une approche empirique,
    je trouve f(1)=1, f(2)=2
    f(3)... en jouant un peu j'ai déjà dénombré 80 chemins différents
    partant d'un coin donc f(3) est largement supérieur à 100 et la fonction
    f croît très vite. Ce qui signifie qu'il y a peu d'espoir d'utiliser un
    algorithme pour dénombrer tous les chemins sauf si ta grille
    est petite. Il y a peut-être des formules asymptotiques
    (du genre f(n)~O(n!) ou exp(n) ou peut-être polynomial mais
    ça n'en prend pas le chemin).

    Il est possible et même probable que les gens qui s'intéressent
    aux marches aléatoires aient creusé la question.
    Il faudrait chercher le net avec les mots-clés
    random walk, lattice non-intersecting ...

  11. #8
    morphdown

    Re : Calcul du nombre de chemins possibles dans une grille à 2Dimensions

    f(2) = 8 !
    tableau de 2 x 2

  12. #9
    Médiat

    Re : Calcul du nombre de chemins possibles dans une grille à 2Dimensions

    9
    Citation Envoyé par ambrosio Voir le message
    avec une approche empirique,
    je trouve f(1)=1, f(2)=2
    f(3)... en jouant un peu j'ai déjà dénombré 80 chemins différents
    partant d'un coin donc ...
    En partant d'un coin donné (en bas à gauche par exemple), je trouve 18 chemins (9 en partant vers le haut et en multipliant par 2 par symétrie).
    J'ai pris la règle : déplacement horizontaux et verticaux (la Tour), interdit de repasser sur une cas visitée, fin du chemin quand aucun mouvement n'est possible.

    Aurais-je oublié un cas ?
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  13. #10
    Ising

    Re : Calcul du nombre de chemins possibles dans une grille à 2Dimensions

    Citation Envoyé par morphdown Voir le message
    J'ai essaye de mettre ça sous forme mathématique mais c'est vite le cauchemar, à cause des chemins ou le serpent se mort la queue.
    En fait, c'est un cauchemar mathématique. Ce problème est connu sous le nom de celui de la marche aléatoire auto-évitante (self-avoiding random walk, ou SARW).

    Grosso modo, on sait que, sans compter les conditions aux frontières (çàd sur un réseau Z^2), le nombre de chemin de taille fixée diverge exponentiellement avec la taille des chemins, mais la formule pour trouver ce nombre n'est pas connue exactement.

    Si tu introduis des conditions aux frontières, il y a des chances pour que cela soit pire que mieux (sauf pour quelques réseaux exceptionnels).

    Pour plus d'infos, cfr:
    http://en.wikipedia.org/wiki/Self-avoiding_walk
    http://mathworld.wolfram.com/Self-AvoidingWalk.html

    A+

    Ising

  14. #11
    morphdown

    Re : Calcul du nombre de chemins possibles dans une grille à 2Dimensions

    Merci pour ta réponse.

    Donc pas de formule mathématique en vue.
    Reste a voir la doc sur randomWalk

    Tks very very mutchhh!


    Avec une méthode récursive on peut facilement calculer le nombre de chemins pour un nombre fixe, je pense que je vais faire un tableau avec les résultats de f(0) à f(n) et pouvoir ainsi analyser la complexité, qui semble être exponentielle.

    Bonne soirée.

Discussions similaires

  1. Nombre de rebonds possibles
    Par duddle dans le forum Science ludique : la science en s'amusant
    Réponses: 4
    Dernier message: 19/04/2008, 15h30
  2. Calcul des combinaisons possibles!
    Par Aero dans le forum Mathématiques du supérieur
    Réponses: 14
    Dernier message: 12/12/2007, 23h36
  3. Calcul du nombre de spires dans un generateur de courant
    Par romain91810 dans le forum Électronique
    Réponses: 1
    Dernier message: 22/04/2007, 19h03
  4. Nombres de chemins différents possibles ?
    Par shokin dans le forum Mathématiques du collège et du lycée
    Réponses: 4
    Dernier message: 04/12/2006, 00h55
  5. LHC : une grille de calcul scientifique équivalente à 6000 processeurs
    Par RSSBot dans le forum Commentez les actus, dossiers et définitions
    Réponses: 3
    Dernier message: 09/05/2005, 13h36