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

Commentaire de Marsu le 05/03/2006 13:31:34

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.

Commentaire de jean_marc_n2 le 05/03/2006 14:04:01

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').

Commentaire de jean_marc_n2 le 05/03/2006 14:23:48

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 :-)

Commentaire de jean_marc_n2 le 26/03/2006 12:03:18

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).

Commentaire de poldere le 31/03/2006 10:32:10

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

Commentaire de poldere le 31/03/2006 22:22:03

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