recherche chemin labyrinthe

Question

bonjour,je sui débutante en C 
svp!! si qqun pourra m'aider sur ce sujet
g un labyrinthe défini a partir d'un fichier texte avec des 1 pour les murs et 0 sinon
je veux bien chercher un chemin entre deux cases mé jarrive pas à trouver une solution
Merci de me présenter un algo si c possible
Crdt

cptpingu · Answer

Renseigne toi sur un algo de backtracking. La récursivité devrait aussi résoudre le problème très rapidement. Plus bourrin, tu peux aussi regarder des algos tel que Manhattan, Astar, ou Dijkstra.

Pistol_Pete · Answer

Salut
>>Cptpingus : Je ne suis pas d'accord avec toi quand tu dis "plus bourrin". Pour Dijkstra c'est vrai mais pas pour l'Astar. Un algo Astar bien codé est très loin de visiter toute la carte. Pour moi c'est le meilleur moyen pour résoudre ce problème.
A+
____________________________________________________________________________
Mon site internet :   
http://ImAnalyse.free.fr

cptpingu · Answer

Je dit plus bourrin au niveau de la difficulté d'implémentation. Il est plus simple de faire un truc en récursif qui visite tout, qu'un des algos précités.

Pistol_Pete · Answer

Dans ce sens, alors là ok.
A+
____________________________________________________________________________
Mon site internet :   
http://ImAnalyse.free.fr

amenienis · Answer

Salut;
jarrive pa à comprendre ces algorithmes, 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

cptpingu · Answer

Fais le en récursif alors. Exemple théorique: Récupère tout les 1 et les 0, et tu les mets dans une matrice. fonction est_valide(Matrice m, Entier x, Entier y) : qui renvoie un boolean début // On vérifie si la coordonnés définit par x et y est valide // Vérifions que ça ne soit pas hors borne Si x >= largeur Ou x < 0 Ou y >= hauteur Ou y < 0 alors retourner faux; retourner Matrice[x][y] == 1; // Si tu es débutante, cette ligne veut dire, retourner vrai si c'est égale à 1, faux sinon. fin fonction recherche(Matrice m, Entier x, Entier y) : qui renvoie un tableau de coordonnés début variable locale: Tableau de coordonnés : tab = [(x,y)] // Regarder si les coordonnées d'à côté sont valides Si est_valide(Matrice, x - 1, y) alors tab = tab + recherche(Matrice, x - 1, y); Sinon Si est_valide(Matrice, x, y - 1) alors tab = tab + recherche(Matrice, x, y - 1); ... // Ici tu le fait pour les 8 directions. retourner tab; fin fonction Main() début variable locale: Matrice d'entier: m; Tableau de coordonnés : tab = [] (vide); m = récuperer tout ce qu'il y a dans le fichier et le mettre dans la matrice. // Ici je suppose que tu commence tout en haut à gauche, et que la case est libre. tab = rechercher(m, 0, 0); Afficher (tab); fin Attention, ce n'est pas du C, c'est vraiment une méthode théorique pour te présenter la manière de faire, à toi ensuite de coder cela, si tu as compris la méthode.

cptpingu · Answer

Il manque quelque chose dans mon algo... La coordonnée d'arrêt !
Il faut bien entendu s'ârrêter quand on arrive à la bonne destination, ou si la destination n'est pas atteignable (mais c'est un poil plus dur, considère que la cible est toujours atteignable et existante, dans un premier temps).

amenienis · Answer

Merci de m'avoir rèpondu!!

j'ai dèja une matrice qui récupère les 1 et les 0!!!!!
mais comme même je vais l'essayer

Recherche chemin labyrinthe

8 réponses

Votre réponse

Discussions similaires