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

[invitea54a6f54]

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!
-----

[invite986312212]

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.

[invitea54a6f54]

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

[invitea54a6f54]

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.

[A voir en vidéo sur Futura]

[}{uman]

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

Cordialement,

[}{uman]

Dsl ya déja le réponse

[invite986312212]

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 ...

[invitea54a6f54]

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

[Médiat]

9

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 ?

[invite0fb72cf8]

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

[invitea54a6f54]

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.