Rechercher des chemins dans une grille
Yugo
-
Char Snipeur Messages postés 9813 Date d'inscription Statut Contributeur Dernière intervention -
Char Snipeur Messages postés 9813 Date d'inscription Statut Contributeur Dernière intervention -
Bonjour,
je débute l'algorithmique et j'ai un problème qui se pose:
j'ai une grille L*l avec L comme largeur et l comme hauteur (tous les deux sont des nb entier). Je cherche tous les chemins existants partant de (0,0) et arrivant en (L-1, l-1) en ne me déplaçant uniquement tout droit, à gauche ou à droite, pas en diagonale.
J'ai donc défini l'entête de ma fonction comme suit:
fonction nombre_chemins(l:entier, L:entier):entier
Je cherche désormais à écrire cette fonction. J'ai lu rapidemment des choses sur dijkstra et astar, peuvent-elles m'être utile ici?
Merci
je débute l'algorithmique et j'ai un problème qui se pose:
j'ai une grille L*l avec L comme largeur et l comme hauteur (tous les deux sont des nb entier). Je cherche tous les chemins existants partant de (0,0) et arrivant en (L-1, l-1) en ne me déplaçant uniquement tout droit, à gauche ou à droite, pas en diagonale.
J'ai donc défini l'entête de ma fonction comme suit:
fonction nombre_chemins(l:entier, L:entier):entier
Je cherche désormais à écrire cette fonction. J'ai lu rapidemment des choses sur dijkstra et astar, peuvent-elles m'être utile ici?
Merci
A voir également:
- Rechercher des chemins dans une grille
- Rechercher ou saisir une url - Guide
- Recherche automatique des chaînes ne fonctionne pas - Guide
- Rechercher une chanson - Guide
- Rechercher une image - Guide
- Rechercher remplacer word - Guide
1 réponse
Salut.
Pas simple comme problème.
Je suppose qu'il y a une condition supplémentaire qui est de ne pas repasser plusieurs fois par une même case, sinon le nombre de solution est infini.
On peut déjà remarqué que pour atteindre ta case finale, il faut avoir L mouvements vers le haut et l vers la droite (en cumulé). Tu as L*l cases, soit au max l*L mouvements maximum. Un mouvement peut être codé par un couple d'entier (v,h) compris entre -1 et 1 (soit 3 valeurs). Par contre, tout les couples ne sont pas valables, tu peux sortir de la grille ou repasser par un endroit déjà fait. Tu peux aussi faire un cul de sac qui ne mène nulle par.
Pour moi l'algorithme est le suivant, pour chaque case tu as 4 directions différentes. Au moins l'une d'elle est mauvaise (celle d'où tu viens).
Il faut donc contruire un arbre à chaque nouvelle case exploré, ou plutôt le dupliquer. Le plus chiant est alors la gestion des variables.
Pas simple comme problème.
Je suppose qu'il y a une condition supplémentaire qui est de ne pas repasser plusieurs fois par une même case, sinon le nombre de solution est infini.
On peut déjà remarqué que pour atteindre ta case finale, il faut avoir L mouvements vers le haut et l vers la droite (en cumulé). Tu as L*l cases, soit au max l*L mouvements maximum. Un mouvement peut être codé par un couple d'entier (v,h) compris entre -1 et 1 (soit 3 valeurs). Par contre, tout les couples ne sont pas valables, tu peux sortir de la grille ou repasser par un endroit déjà fait. Tu peux aussi faire un cul de sac qui ne mène nulle par.
Pour moi l'algorithme est le suivant, pour chaque case tu as 4 directions différentes. Au moins l'une d'elle est mauvaise (celle d'où tu viens).
Il faut donc contruire un arbre à chaque nouvelle case exploré, ou plutôt le dupliquer. Le plus chiant est alors la gestion des variables.
