Recherche chemin labyrinthe en C
Fermé
ameni.enis
Messages postés
22
Date d'inscription
mardi 3 février 2009
Statut
Membre
Dernière intervention
26 mai 2010
-
25 avril 2009 à 23:12
parcours Messages postés 13 Date d'inscription mercredi 3 juin 2009 Statut Membre Dernière intervention 28 juin 2009 - 28 juin 2009 à 17:35
parcours Messages postés 13 Date d'inscription mercredi 3 juin 2009 Statut Membre Dernière intervention 28 juin 2009 - 28 juin 2009 à 17:35
A voir également:
- Recherche chemin labyrinthe en C
- Recherche automatique des chaînes ne fonctionne pas - Guide
- Recherche adresse - Guide
- Recherche musique - Guide
- Recherche par image - Guide
- Recherche privée - Guide
3 réponses
the F
Messages postés
150
Date d'inscription
dimanche 22 mars 2009
Statut
Membre
Dernière intervention
22 mars 2011
13
25 avril 2009 à 23:30
25 avril 2009 à 23:30
je propose d'utiliser une liste chainee peut etre ??
KX
Messages postés
16752
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
31 août 2024
3 019
26 avril 2009 à 15:41
26 avril 2009 à 15:41
En fait je pense qu'une pile (ou deux) serait plus adapté, et si tu ne connais pas les piles, c'est le moment de t'y mettre ;)
Tu pars de ton point de départ, tu places les cases adjacentes (celles à 0) dans la pile puis tu vides la pile en faisant la même recherche sur les cases que tu viens de dépiler (en s'assurant de ne pas tourner en rond) jusqu'à ce que tu tombes sur ta case d'arrivée...
Il te faudra cependant pouvoir "remonter" le chemin parcouru (associe chaque case empilée à sa case adjacente "père") et alors tu auras un chemin pour aller de ta case de départ à ta case d'arrivée, et si c'est bien fait normalement cette méthode doit te donner le plus court chemin...
Tu pars de ton point de départ, tu places les cases adjacentes (celles à 0) dans la pile puis tu vides la pile en faisant la même recherche sur les cases que tu viens de dépiler (en s'assurant de ne pas tourner en rond) jusqu'à ce que tu tombes sur ta case d'arrivée...
Il te faudra cependant pouvoir "remonter" le chemin parcouru (associe chaque case empilée à sa case adjacente "père") et alors tu auras un chemin pour aller de ta case de départ à ta case d'arrivée, et si c'est bien fait normalement cette méthode doit te donner le plus court chemin...
KX
Messages postés
16752
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
31 août 2024
3 019
26 avril 2009 à 15:51
26 avril 2009 à 15:51
PS. c'est un peu le même algorithme que celui que j'avais décrit en détail ici
ameni.enis
Messages postés
22
Date d'inscription
mardi 3 février 2009
Statut
Membre
Dernière intervention
26 mai 2010
>
KX
Messages postés
16752
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
31 août 2024
26 avril 2009 à 22:23
26 avril 2009 à 22:23
merci KX pr l'algo
jvé lessayé
jvé lessayé
ameni.enis
Messages postés
22
Date d'inscription
mardi 3 février 2009
Statut
Membre
Dernière intervention
26 mai 2010
>
KX
Messages postés
16752
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
31 août 2024
7 mai 2009 à 07:29
7 mai 2009 à 07:29
Salut;
jarrive pa à comprendre cet algorithme,mm celui de Djiskra!! jsuis encore débutante!!
Svp si qqun peut me donner un algo plus simple(ni pile ni listes chainèes) qui traite ce problème de recherche en C.
Merci bien d'avance
Cdlt
jarrive pa à comprendre cet algorithme,mm celui de Djiskra!! jsuis encore débutante!!
Svp si qqun peut me donner un algo plus simple(ni pile ni listes chainèes) qui traite ce problème de recherche en C.
Merci bien d'avance
Cdlt
KX
Messages postés
16752
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
31 août 2024
3 019
>
KX
Messages postés
16752
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
31 août 2024
8 mai 2009 à 18:35
8 mai 2009 à 18:35
De toute façon l'algorithme de Dijkstra n'est pas fait pour ce genre de problème, à moins que tu ne veuilles connaitre tous les chemins de tous les possibilités (départ-arrivée)
Ce que tu essayes de faire demande des connaissances un peu plus poussées, et c'était l'occasion de voir le fonctionnement des piles...
Pour une autre solution j'espère que tu comprends au moins la récursivité, parce que sinon il va falloir qu'on te l'explique...
La solution que je proposais était optimale (on pouvait pas trouver de chemin plus court) mais si tu veux juste trouver un chemin quelconque du moment qu'il rejoint l'arrivée, alors tu peux décider de suivre l'algorithme suivant :
Tu pars d'une case (la première fois c'est ta case d'arrivée)
Si c'est ta case d'arrivée t'as gagné
Si c'est un mur t'as perdu
Sinon tu essaye avec la case du haut (qui essayera elle même en haut/gauche/bas/droite)
Sinon tu essaye avec la case de gauche (qui essayera elle même en haut/gauche/bas/droite)
Sinon tu essaye avec la case du bas (qui essayera elle même en haut/gauche/bas/droite)
Sinon tu essaye avec la case de droite (qui essayera elle même en haut/gauche/bas/droite)
Sinon ta case d'arrivée ne peut pas être atteinte
(en fait l'ordre haut/gauche/bas/droite importe peu)
C'est l'algo le plus simple que je connaisse pour ton problème (pas le plus efficace) et en plus quand la récursivité se terminera avec tous tes cas positifs tu pourras faire l'affichage (en ordre inverse) de tes cases intermédiaires
Ce que tu essayes de faire demande des connaissances un peu plus poussées, et c'était l'occasion de voir le fonctionnement des piles...
Pour une autre solution j'espère que tu comprends au moins la récursivité, parce que sinon il va falloir qu'on te l'explique...
La solution que je proposais était optimale (on pouvait pas trouver de chemin plus court) mais si tu veux juste trouver un chemin quelconque du moment qu'il rejoint l'arrivée, alors tu peux décider de suivre l'algorithme suivant :
Tu pars d'une case (la première fois c'est ta case d'arrivée)
Si c'est ta case d'arrivée t'as gagné
Si c'est un mur t'as perdu
Sinon tu essaye avec la case du haut (qui essayera elle même en haut/gauche/bas/droite)
Sinon tu essaye avec la case de gauche (qui essayera elle même en haut/gauche/bas/droite)
Sinon tu essaye avec la case du bas (qui essayera elle même en haut/gauche/bas/droite)
Sinon tu essaye avec la case de droite (qui essayera elle même en haut/gauche/bas/droite)
Sinon ta case d'arrivée ne peut pas être atteinte
(en fait l'ordre haut/gauche/bas/droite importe peu)
C'est l'algo le plus simple que je connaisse pour ton problème (pas le plus efficace) et en plus quand la récursivité se terminera avec tous tes cas positifs tu pourras faire l'affichage (en ordre inverse) de tes cases intermédiaires
ameni.enis
Messages postés
22
Date d'inscription
mardi 3 février 2009
Statut
Membre
Dernière intervention
26 mai 2010
>
KX
Messages postés
16752
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
31 août 2024
8 mai 2009 à 22:29
8 mai 2009 à 22:29
Merci de me répondre KX!!
l'algo est simple et compréhensif,je l'ai bien compris mais mon problème mnt c'est comment le programmer en C
svp si vous pouver m'aider à le programmer
mon mini projet sera ce lundi et j'ai rien fait encore,,j'essaie mais en vain!!!!!!
SVP
j'attend votre réponse
MERCI
l'algo est simple et compréhensif,je l'ai bien compris mais mon problème mnt c'est comment le programmer en C
svp si vous pouver m'aider à le programmer
mon mini projet sera ce lundi et j'ai rien fait encore,,j'essaie mais en vain!!!!!!
SVP
j'attend votre réponse
MERCI
Char Snipeur
Messages postés
9813
Date d'inscription
vendredi 23 avril 2004
Statut
Contributeur
Dernière intervention
3 octobre 2023
1 298
7 mai 2009 à 08:24
7 mai 2009 à 08:24
Tu peux faire un chemin aléatoire.
Tu met les murs à -1 plutôt que 1.
Ensuite, quand tu es dans une case, tu incrémente sa valeur de 1. Tu as alors 4 directions possible au plus (haut bas gauche droite), parmis ces 4 cases possibles, supposons qu'il y ait 3 zéros (des cases encore non visités) et 1 case à 1 (déjà visité) tu prends alors le groupe de plus petite valeur (les 0) et tu en choisi une au hasard.
Tu peux repasser plusieurs fois au même endroit, mais il faut incrémenté alors à chaque fois la case.
En retenant chaque mouvement, tu pourra alors reconstitué le chemin.
Tu met les murs à -1 plutôt que 1.
Ensuite, quand tu es dans une case, tu incrémente sa valeur de 1. Tu as alors 4 directions possible au plus (haut bas gauche droite), parmis ces 4 cases possibles, supposons qu'il y ait 3 zéros (des cases encore non visités) et 1 case à 1 (déjà visité) tu prends alors le groupe de plus petite valeur (les 0) et tu en choisi une au hasard.
Tu peux repasser plusieurs fois au même endroit, mais il faut incrémenté alors à chaque fois la case.
En retenant chaque mouvement, tu pourra alors reconstitué le chemin.
26 avril 2009 à 15:27