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
Bonjour,
Svp si qqun peut m'aider à résoudre ce problème
j'ai un labyrinthe défini à partir d'une matrice avec 1 pour les murs et 0 sinon
je veux trouver un chemin entre deux points
comment je procéde pour le programmer en C
Merci d'avance

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
je propose d'utiliser une liste chainee peut etre ??
0
ameni.enis Messages postés 22 Date d'inscription mardi 3 février 2009 Statut Membre Dernière intervention 26 mai 2010
26 avril 2009 à 15:27
jne sais pa bien manipulé les listes chainées!!!!!!!!
0
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
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...
0
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
PS. c'est un peu le même algorithme que celui que j'avais décrit en détail ici
0
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
merci KX pr l'algo
jvé lessayé
0
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
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
0
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
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
0
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
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
0
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
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.
0