| 3 KX, le 26 avr 2009 à 15:41:40En 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...
La confiance n'exclut pas le contrôle | 4 KX, le 26 avr 2009 à 15:51:23PS. c'est un peu le même algorithme que celui que j'avais décrit en détail ici
La confiance n'exclut pas le contrôle | 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 |
| 8 KX, le 8 mai 2009 à 18:35:07De 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
La confiance n'exclut pas le contrôle | 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 | 10 KX, le 8 mai 2009 à 23:26:25Comme tu le dis l'algo. est simple, et c'est d'ailleurs du copier-coller que de le faire en C !
Bien sûr aussi simple que ça, ça ne peut pas être performant... #include <stdio.h>
#include <stdlib.h>
const int XMAX=10;
const int YMAX=10;
int compteur=0;
typedef bool labyrinthe[XMAX][YMAX]; // 1 pour un mur, 0 sinon
struct point { int x; int y; };
void afficherPoint(point P)
{
printf("(%ld;%ld)\n",P.x,P.y);
}
point proche(point p,int dx,int dy)
{
point p2={p.x+dx,p.y+dy};
return p2;
}
bool afficherChemin(labyrinthe L, point A, point B)
{
compteur++;
// Si c'est les memes cases on a a reussi
if (A.x==B.x && A.y==B.y) { afficherPoint(A); return true; }
// Si c'est un mur on s est egare
if (L[A.x][A.y] || A.x<0 || A.x>=XMAX || A.y<0 || A.y>=YMAX) return false;
L[A.x][A.y]=1; // pour ne pas tourner en rond
// Sinon on essaye avec la case du haut
if (afficherChemin(L,proche(A,0,1),B)) { afficherPoint(A); return true; }
// Sinon on essaye avec la case de gauche
if (afficherChemin(L,proche(A,-1,0),B)) { afficherPoint(A); return true; }
// Sinon on essaye avec la case du bas
if (afficherChemin(L,proche(A,0,-1),B)) { afficherPoint(A); return true; }
// Sinon on essaye avec la case de droite
if (afficherChemin(L,proche(A,1,0),B)) { afficherPoint(A); return true; }
// Sinon la case d'arrivée ne peut pas être atteinte
return false;
}
int main(void)
{
labyrinthe Laby;
int x,y;
for (x=0; x<XMAX; x++)
for (y=0; y<YMAX; y++)
Laby[x][y]=0;
point Depart={4,5};
point Arrivee={5,1};
compteur=0;
if (!afficherChemin(Laby,Arrivee,Depart)) printf("Il n'y a pas de solution\n");
printf("\n%ld cases testees\n\n",compteur);
system("PAUSE");
return(EXIT_SUCCESS);
}À toi maintenant de trouver comment passer de cet algorithme simple à un algorithme plus efficace - voir optimal - comme celui que j'ai donné dans mon premier post...
Bonne continuation !
La confiance n'exclut pas le contrôle | Merci pour votre réponse rapide
je vais l'essayer, j'ai l'impression que ca marche mnt!!:)
Merci infiniment | 12 KX, le 9 mai 2009 à 00:03:23Bien sûr que ça marche !!! Je ne me serais pas amusé à faire quelque chose de faux ^^
La confiance n'exclut pas le contrôle | Au cous de la compilation, il m'affiche une erreur:
erreur: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘afficherChemin’
cette erreur correspond à la ligne : bool afficherChemin(int cas_d,int cas_a)
voici le pg que j'ai tapé, c'est pratiquemet le mm que vous m'avez présenté mais avec mais propres données:
NB:les fcts verifier_haut,bas,drte,gauche sont des fcts que j'ai defini pour verifier s'il ya un mur et retourne 1 s'ilya 0 sinon.
Merci autre fois de m'avoir aider!!:)
#include <stdio.h>
#include <stdlib.h>
int compteur=0;
void afficherPoint(int cas)
{
printf("%d\n",cas);
}
int succes(int cas,int dcas)
{
int suc=cas + dcas;
return suc;
}
bool afficherChemin(int cas_d,int cas_a)
{
compteur++;
// Si c'est les memes cases on a a reussi
if (cas_d==cas_a) { afficherPoint(cas_d); return true; }
// Si c'est un mur on s est egare
if (verifier_haut==1 || verifier_bas==1 || verifier_droite==1 || verifier_gauche==1) return false;
// Sinon on essaye avec la case du haut
if (afficherChemin(succes(cas_d,-8),cas_a)) { afficherPoint(cas_d); return true; }
// Sinon on essaye avec la case de gauche
if (afficherChemin(succes(cas_d,-1),cas_a)) { afficherPoint(cas_d); return true; }
// Sinon on essaye avec la case du bas
if (afficherChemin(succes(cas_d,8),cas_a)) { afficherPoint(cas_d); return true; }
// Sinon on essaye avec la case de droite
if (afficherChemin(succes(cas_d,1),B)) { afficherPoint(cas_d); return true; }
// Sinon la case d'arrivée ne peut pas être atteinte
return false;
}
int main(void)
{
int cas_d,cas_a;
printf("donner la case de depart : \t");
scanf("%d",&cas_d);
printf("donner la case d'arrivee : \t");
scanf("%d",&cas_a);
if (!afficherChemin(cas_d,cas_a)) printf("Il n'y a pas de solution\n");
return 0;
} | 14 KX, le 9 mai 2009 à 12:42:00Il faut que tu mette des paramètres à verifier_haut/bas/droite/gauche de plus tu as oublie le cas verifier_milieu
je ne comprend pas : int cas_d; scanf("%d",&cas_d); ça devrait être scanf'"%ld",cas_d); non ?
ensuite tu fais afficherChemin(succes(cas_d,1),B) sans avoir défini B
mais sinon ton problème viendrait peut-être de "bool" qui ne serait pas pris en charge par ton compilateur
et à mon avis il y a encore pas mal d'erreur de recopie, par exemple tu n'as plus de matrice de 0 ou 1...
La confiance n'exclut pas le contrôle | Si,,, j'ai commis pas mal de fautes!!!!
j'ai utulisé la mèthode des piles que tu m'a proposé (remplissage..),ca bien marcher, g maintnant un joli laby avec animation pour le chemin!!!^_^
Jte remercie infiniment KX, c'est grace a ton aide que j'ai pu trouver la solution!!!
Merci bien | Bonjour,
je suis étudiante en 1er année D.I et j'ai choisie aussi comme projet le jeu de labyrinthe ,j'ai fait jusqu'à maintenant le code qui permet de crée le laby mais je sais comment faire un code pour l'afficher ,
il doit être affiché avec une grille qui contient : ____ =mur et " " = couloir ,
alors comme vous avez fait le même programme j'espère que vous allez m'aidai a se point,
j'attends votre repense avec impatience ,
Merci a l'avance |
|
|
|
|
|
|
|
|
|
| Slt , mais on a pas encor fini le programme juste ici on ai dans les fichiers on a pas étudiers les piles |
|
Emission patrick sabatier avis de recherche