RÉSOLUTION D'UN LABYRINTHE (MÉTHODE RÉCURSIVE) - SOLVEUR RÉCURSIF GÉNÉRAL

cs_Willi Messages postés 2375 Date d'inscription jeudi 12 juillet 2001 Statut Modérateur Dernière intervention 15 décembre 2018 - 4 mars 2006 à 12:49
poldere Messages postés 69 Date d'inscription samedi 14 mai 2005 Statut Membre Dernière intervention 12 août 2007 - 25 juin 2006 à 17:17

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/36373-resolution-d-un-labyrinthe-methode-recursive-solveur-recursif-general

poldere Messages postés 69 Date d'inscription samedi 14 mai 2005 Statut Membre Dernière intervention 12 août 2007
25 juin 2006 à 17:17

Ok merci. Je voulais partir de 3 cas différents :
1 : On connait le périmètre et les obstacles d'avance > on cherche juste le chemin le plus court
2 : Obstacles aléatoires dans un périmètre connu > calcul de contournement d'obstacle et re chemin le plus court.
3 : territoire inconnu > découverte et mémorisation du périmètre et des obstacles fixes.
4,5 : territoire inconnu et obstacles mouvants ( comme du sable par exemple lol ).
voilà en gros ce que je cherche à réaliser doucement avec le peu de connaissance que j'ai. Alors je cherche et merci à ceux qui ont mis des codes qui m'ont et m'auront aidé à progresser.
Merci à tous

pekch Messages postés 51 Date d'inscription vendredi 20 février 2004 Statut Membre Dernière intervention 7 juillet 2006
25 juin 2006 à 15:46

mais ce n'est pas un algo de trajectoire, poldere!? c'est de la résolution de lab. c pas pareil... enfin je tuche pas des masses sur le sujet mais je crois que ca n'a rien a voir, dans la mesur ou dans un algo de trajectoire on connait déjà les chemins possibles, et on teste le plus court...

poldere Messages postés 69 Date d'inscription samedi 14 mai 2005 Statut Membre Dernière intervention 12 août 2007
31 mars 2006 à 22:22

Merci pour la réponse et du peu que je connaisse en VB et le peu que j'ai pu voir du programme ; il est vrai que lorsqu'on enlève les obstacles on se rend compte que la recherche de chemin fait un genre " serpent ". Il serait stupide que le robot fasse le même chemin avant d'arrivé au but lol. Je vais fair une recherche avec " djisktra " pour trouver quelque chose en visuak basic à mon niveau basique.
Merci

jean_marc_n2 Messages postés 170 Date d'inscription jeudi 11 décembre 2003 Statut Membre Dernière intervention 24 janvier 2009
31 mars 2006 à 19:37

Hello, ça dépend de ce que tu veux faire. Si le robot doit pouvoir trouver un ou plusieurs objets dans la maison, alors on peut l'utiliser. Si le robot doit passer par tous les endroits de la maison, on peut aussi l'utiliser. Si le robot doit pouvoir trouver le chemin le plus court pour se rendre à un endroit donné, alors cet algorithme peut être utilisé, au prix de quelques modifications, mais il n'est pas fait pour ça. Il existe des algorithmes plus efficaces pour la détermination des chemins les plus courts, avec des contraintes.

Pour la majorité des cas, oui cet algorithme est tout à fait adéquat pour déplacer un robot dans une maison.

poldere Messages postés 69 Date d'inscription samedi 14 mai 2005 Statut Membre Dernière intervention 12 août 2007
31 mars 2006 à 10:32

Bonjour, je voudrais savoir si on peut utiliser ta source en l'adaptant pour le déplacemet d'un robot ? Création automatique ou manuel d'un labyrinthe correspondant à des pièces d'une maison puis déplacement à partir de cette base. Merci

cs_guyvdv Messages postés 101 Date d'inscription samedi 16 mars 2002 Statut Membre Dernière intervention 19 mai 2011 1
26 mars 2006 à 12:07

merci jean-marc,
J'ai deja beaucoup cherche sur google, et beaucoup trouve
Mais le mot recursivite et dijkstra pas encore essayer
Merci et je te tiens au courant

A+
Guy van der Velden

jean_marc_n2 Messages postés 170 Date d'inscription jeudi 11 décembre 2003 Statut Membre Dernière intervention 24 janvier 2009
26 mars 2006 à 12:03

Hello Guy, tu trouveras de très nombreuses références à Dijkstra sur le net, tu peux tout simplement entrer "Dijkstra" dans Google, tu auras déjà beaucoup de liens.
Pour la récursivité, il existe des centaines de références sur le net, tu peux commencer par la par exemple: http://www.chambily.com/recursivite/

Sur ce coup la, Google est ton ami, tu trouveras tout ce qu'il te faut. Ensuite, ayant compris les principes sous-jacents, utiliser et adapter mon programme devrait être assez simple pour résoudre tes cas particuliers (sudoku, etc).

cs_guyvdv Messages postés 101 Date d'inscription samedi 16 mars 2002 Statut Membre Dernière intervention 19 mai 2011 1
25 mars 2006 à 17:50

Bonjour Tout lemonde
Je debut dans la recursion, j'avai trouvé sur e a http://personal.vsnl.com/erwin/connect4.htm
un tut de recursion, mais le connect (4 sur une ligne? ) de fonctionne pas chez moi.(Commenté en hollandais alors illisible pour vous).
Il y a qq qui peu me donner un tuyo pour comprendre un peut la recursion.

le script de jean-marc est claire mais comment l'emploier pour 4/1 ligne et plus tard sudoku hihihi

Le nom Dijkstr ( hollandais) , ou je trouve ce qu'il a ecris??
Merci de m'aider un peut
A+
Guy van der Velden

jean_marc_n2 Messages postés 170 Date d'inscription jeudi 11 décembre 2003 Statut Membre Dernière intervention 24 janvier 2009
5 mars 2006 à 14:23

Merci willi pour tes commentaires :-) C'est vrai que ce programme n'est pas en soi destiné à trouver le chemin le plus court. Il est destiné à trouver une solution par recherche récursive. Mais c'est vrai aussi qu'on peut le modifier (assez) aisément pour trouver des minima (donc en queque sorte trouver les chemins les plus courts). Bien sur, un tel algorithme modifé sera TRES inefficace dans le cas présent puisque comme je le disais, il y a d'autres algorithmes qui sont fait pour ça (par exemple l'algorithme A* de Dijkstra). Salut et encore merci pour tes sympathiques commentaires :-)

cs_Willi Messages postés 2375 Date d'inscription jeudi 12 juillet 2001 Statut Modérateur Dernière intervention 15 décembre 2018 22
5 mars 2006 à 14:12

Et moi qui croyais avoir tout compris je me suis trompé également :)

jean_marc_n2 Messages postés 170 Date d'inscription jeudi 11 décembre 2003 Statut Membre Dernière intervention 24 janvier 2009
5 mars 2006 à 14:04

Hello,

tu n'as visiblement pas lu ou pas compris l'algorithme. Je penche pour la seconde solution. Ce programme permet bien évidemment de trouver le chemin le plus court (il suffit de regarder l'indice de pile à chauqe fois qu'on atteint un "B" et de stocker ce nouveau chemin si il est plus court que celui déjà sauvé).

Relis le au calme, essaie de bien comprendre comment cela fonctionne. Ca demande une petite gymnastique cérébrale ;-)

Qui plus est, il existe d'autres méthodes de résolution de labyrinthes: c'est un problème général de parcours de graphes. Tout a été dit et écrit par Dijkstra sur le sujet. On trouve aussi de très bonnes implémentations dans Knuth (TAOCP, Volume 3, 'Sorting and Searching').

cs_Willi Messages postés 2375 Date d'inscription jeudi 12 juillet 2001 Statut Modérateur Dernière intervention 15 décembre 2018 22
5 mars 2006 à 13:53

Bonne remarque Marsu, mais le but n'est pas de trouver le chemin le plus court ici.

cs_Marsu Messages postés 21 Date d'inscription jeudi 27 décembre 2001 Statut Membre Dernière intervention 22 décembre 2008
5 mars 2006 à 13:31

Moyen, je ne comprends pas pourquoi ne pas chercher le chemin le plus court, ce qui est a mon avis pas vraiment plus long, et permet aussi de traiter d'autres problèmes.

cs_Willi Messages postés 2375 Date d'inscription jeudi 12 juillet 2001 Statut Modérateur Dernière intervention 15 décembre 2018 22
4 mars 2006 à 12:49

Source instructive :)
Bonne continuation 8/10

Discussions similaires

Parcourir des repertoires (fonction recursive)

Masquer une méthode héritée

Utilitaire de résolution de problèmes

fonction récursive et count mysql a additionner

Résoudre une équation (un système d'équation ???) avec le solveur Excel 2007

Votre réponse

Discussions similaires