RECHERCHE DE CHEMIN (RECURSIVITÉ ET BACKTRACKING)
cs_Joky
Messages postés
1787
Date d'inscription
lundi 22 novembre 2004
Statut
Membre
Dernière intervention
31 janvier 2009
-
20 avril 2006 à 17:28
rrk275 Messages postés 540 Date d'inscription vendredi 25 juin 2004 Statut Membre Dernière intervention 1 octobre 2007 - 9 mai 2006 à 22:46
rrk275 Messages postés 540 Date d'inscription vendredi 25 juin 2004 Statut Membre Dernière intervention 1 octobre 2007 - 9 mai 2006 à 22:46
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/37160-recherche-de-chemin-recursivite-et-backtracking
https://codes-sources.commentcamarche.net/source/37160-recherche-de-chemin-recursivite-et-backtracking
9 mai 2006 à 22:46
21 avril 2006 à 18:13
Soit fait pas attention à ma question lol
21 avril 2006 à 16:21
_
| ____
|___| |
| _
|___| |
|
Ton algorithme pourrait il suivre ce chemin ? c'est à dire remonter pour trouver le chemin. Tu as peut etre répondu à ma question ici plus haut mais comme faut toujours tout me répeter 2 fois, je serai fixé ainsi lol
21 avril 2006 à 07:51
20 avril 2006 à 21:43
Tu as réussi à développer quelque chose d'une manière que je n'ai pas su réaliser. J'ai été confronté à ce problème un moment et j'ai pensé à le faire avec de la récursivité et... comme je trouve que cette approche est un peu floue et bien j'ai rennoncé à cette manière qui semblait la plus logique et j'ai pensé à un autre algorithme. Il vaut ce qu'il vaut, il n'est sans doute pas meilleur que le tiens, mais je vais en donner l'idée pour ceux qui aurait comme moi, du mal avec la recursivité.
En fait, mon algorithme recopie le tableau initial dans un autre tableau (ca ce n'est pas obligatoire si dans le premier tableau il n'y a que deux choix différent : chemin libre, chemin non libre). Si ce n'est pas le cas il recopie le tableau en simplifiant de cette manière, autrement dit si l'élément est un arbre une pierre ou autre chose qui bloque le passage il met 0 sinon il met 1. On se retrouve avec un tableau binaire. Ensuite je considère que les chemins possibles partent d'un point et ne peux que descendre vers 3 des points situés en dessous (celui directement en dessous, et ceux à gauche et à droite de celui directement en dessous).
Il parcourt alors tout le tableau et pour chaque élément il regarde si au moins un des 3 éléments de passage est libre, si c'est le cas il ne fait rien, si ce n'est pas le cas il transforme l'élement en 0 car cela voudra dire que le passage est impossible par ce point. On vérifie tout les lignes sauf la dernière, ce n'est pas utile. Le parcours se fait de bas en haut.
Une fois ce passage terminé, alors il suffit de prendre un point de départ et à chaque fois on choisit un de ces points en dessous, il est alors sur et certain que si un chemin existe ce point en fera partie.
Maintenant, je n'ai pas regardé à fond ton code, donc je ne sais pas si ton algorithme est capable de remonter dans le tableau pour faire un détour à fin d'arriver au sommet. Le mien ne l'est pas ;)
20 avril 2006 à 17:28
J'suis entrain de faire ce genre de truc ;)
Enfin vous verrez quand j'aurais fini ;)