fonction recursive / DFS/ shortest path finding

Bonjour
Je suis en train de resoudre un exercice en C et je suis face a un probleme.


J'ai defini une grille (carte topologique simplifiee) dont chaque case comporte 2 caracteristiques: sa traversabilite et son degre d inclinaison. Si la case a un degre d inclinaison eleve, cela siginifie que le cout demande pr la traverser sera eleve...

J ai donc prepare ma grille, suivant toutes les recommendations de l exercice et je dois a present ecrire une fonction de recherche du chemin le plus court entre 2 points. Cette fonction prend en compte ma grille, un cout maximal qu on ne peut pas depasser et les coordonnees de mon point de depart et de mon point d arrivee...

Le prof nous dit que l on peut utiliser l agorithme DFS et /ou ecrire une fonction recursive qui permet de calculer ce chemin le plus court...

J ai regarde sur internet ce qu est un DFS mais je n ai pas bien saisi et surtout je ne vois pas comment l appliquer a mon probleme...

Comment ecrire cette fonction recursive interne a ma fonction de calcul du chemin le plus court (si existe) qui prend en argument ma grille, le point ou l on se trouve, la cible et un nombre entier qui definit combien de "pas" l on peut encore realiser ???

Merci pour votre aide!

Bonjour,

Ton problème est avant tout un problème d'algorithmique et aurait plus sa place dans le forum consacré.

DFS, c'est Deep First Search, soit « Recherche en profondeur d'abord ». Ça s'applique à des arbres. Quand tu pars de la racine d'un arbre ou d'un nœud quelquonque, tu as le choix d'explorer d'abord tous ses fils puis, une fois fait, de poursuivre l'exploration vers ses petits fils, et ainsi de suite, ou alors tu peux choisir de traiter le premier fils que tu trouves et le considérer comme la racine du sous-arbre qu'il y a en dessous. À ce moment, il te suffit de rappeler la même fonction pour la traiter et c'est en ce sens que l'algo est récursif.

Maintenant, ça ne s'applique pas directement à une grille.

Citation:

---

J'ai defini une grille (carte topologique simplifiee) dont chaque case comporte 2 caracteristiques: sa traversabilite et son degre d inclinaison. Si la case a un degre d inclinaison eleve, cela siginifie que le cout demande pr la traverser sera eleve...

---

Qu'appelles-tu « traversabilité » ?

Si ta case présente un angle d'inclinaison, elle a forcément une orientation (de quel côté on monte, de quel côté on descend). Si, en revanche, chaque case est distinguée par son altitude, alors tu peux considérer ta grille comme un graphe orienté et pondéré, et tu peux lui appliquer l'algorithme de Dijkstra.