Résolution de labyrinthes

Bonjour tous le monde !

Voila je m'ennuyais un peu et j'ai eu l'idée de créer un petit algorithme qui me permette de trouver la sortie d'un labyrinthe... (très très original me dirais vous)

Alors du point de vue de l'algorithme, il est parfait, c'est à dire qu'il trouve la sortie :yaisse2:...

Seulement voila, en fait il prend souvent les mauvais embranchements (bé 2 fois sur 3 vu que j'ai remis le choix de la direction au hasard ^^) et je me demandais si personne ne connaissais un petit algorithme d'évaluation des chemins...

Je m'explique : je ne sais pas du tous où sont les noeuds, ni ce qu'il y a après le prochain tournant, mais comme je suis très fort, je peut parcourir mentalement le labyrinthe pendant que je le parcours (bé oui pas avant ce serai de la triche ^^). Ce que je veut rajouter, c'est une sorte d'algo "d'intuition" qui me dise : va pas par là ça craint... par exemple un algo qui évalue grosso modo la direction que l'on va prendre pour voir où l'on sera plusieures étapes après...

Le seul truc c'est que c'est que les algos que j'ai fait en ce sens sont tous presques aussi long (voir plus) que de parcourir tous les mauvias embranchements :mouarf:

Voila merci aux bonnes âmes qui voudront bien me répondre parceque la je sèche sur comment optimiser les choix...

Pour trouvé la sortie d'un labyrinthe il y 2 algo que tu dois connaitre ce sont: Dijkstra et A*. D'ailleurs je te conseil leur version génétique bien plus efficace;) par rapport a la version gloutons.

Merci de ta réponse snake, mais il me semble que tu doit connaître les noeuds intermédiaire pour le Djikstra comme pour le A*.

Pour le A*, il me semble aussi qu'il n'est pas forcemment efficace dans tous les labyrinthes (notamment ceux qui doivent s'éloigner de l'arrivée pour y aller).

Le Djikstra me pose également problème : comme je ne connais pas les noeuds à l'avance, il faut donc que je parcours tout mon labyrinthe pour les repèrer, puis ensuite définir des poids etc...
Ce qui m'interesse n'est pas ici forcemment de parcourir le chemin le plus court, mais bien d'arriver au bout le plus rapidement possible (en effet si je connnais à l'avance le chemin le plus court, c'est lui que j'ai intéret à prendre, mais ce n'est pas le cas)

Ma méthode de parcour aléatoire me permet alors de ne pas toujours parcourir le graphe en entier, ce qui me parrait alors mieux que le Djikstra ou le A*. A moins que je ne me trompe dans leur interprétation ?

Et aurait tu de la doc concernant les versions gloutons et génétique ? car j'ai cherché sur internet, mais je n'ais rien trouvé de "didactique".

Encore merci de ta réponse

Pour des cours il y a un très bon tuto sur le A* sur dvp;) pour Dijkstra je ne sais pas je n'ai jamais chercher:oops:

Ensuite c'est vrai tu n'as pas tord mais l'algo A* reprend les mêmes principes que Dijkstra mis à part que A* est de plus heuristique, c'est à dire que l'on se doute que dans la majorité des cas, la direction à prendre est en général la direction de la sortie, très très pratique notamment s'il n'y a aucun obstacle entre le point de départ et la sortie. Enfin une variante consiste à lancer l'algorithme du point de départ mais également, du point d'arrivé en alternant, mais cela n'a pas beaucoup d'intérêt pour ton problème, enfin c'est mon point de vue et en algo on a fait ce genre de petit exo et le résultat était bien au rendez-vous:mrgreen: Après il est sur que tu peut te créer ton propre algo à partir de ceux-là;)

Citation:

---

Envoyé par snake264

Pour trouvé la sortie d'un labyrinthe il y 2 algo que tu dois connaitre ce sont: Dijkstra et A*. D'ailleurs je te conseil leur version génétique bien plus efficace;) par rapport a la version gloutons.

---

Algo génétique ou simulant les colonies de fourmis ?

Génétique pour ce genre de chose car colonie de fourmi j'ai peur que le résultat ne soit pas optimal dans l'immédiat(faut dire aussi que je ne maitrise pas énormément ce genre d'algo qui est la coloni des fourmi, utiliser qu'une fois pour le PVC donc pas assé d'expérience dessus).

Tu pourrais alors peut-être me donner quelques idées pour ce problème. Je sèche car je n'arrive pas à trouver quelque chose de vraiment satisfaisant.
En fait je ne vois pas bien comment symboliser la population.
Au cours de la discussion, quelqu'un a dit qu'il vallait mieux utiliser les colonies de fourmis pour ce genre de problème, c'est pour celà que je posais la question.
As-tu des lectures à me conseiller ?

Voici déjà une petite solution toute simple qui marche dans tout les cas, quitte à ne pas prendre le chemin le plus court: c'est une exploration en profondeur qu'il faut faire d'abord.

Concrètement, tu te trouve sur un sommet donné. Tu choisis le premier voisin venu et tu recommence. Si à un moment donné il n'y a plus de voisin, cette branche de l'exploration a échoué et tu remonte essayer une autre branche.

Tu t'arrête bien sûr quand tu arrive sur la sortie. Cela se code simplement en utilisant la récursivité.

Le plus simple est d'utiliser une fonction booléenne qui répond si elle a déjà trouvé la sortie ou pas. Tu aura besoin d'un tableau de booléen indiquant si tu as déjà visité un sommet ou pas.

Voila j'espère que c'est assé clair :)

Personnellement, c'est quasiment l'algo que vient de décrire snake que j'utilise dans mon solveur. Et je peut confirmer qu'il résout TOUS les labyrinthes, pas forcemment le plus rapidement (c'était même la raison de mon post), mais il les résoult...

Oui ce que je viens de donner c'est l'algo de base après il y en a qui sont beaucoup mieux mais aussi plus compliqué:mouarf:

Citation:

---

Envoyé par snake264

Voici déjà une petite solution toute simple qui marche dans tout les cas, quitte à ne pas prendre le chemin le plus court: c'est une exploration en profondeur qu'il faut faire d'abord.

Concrètement, tu te trouve sur un sommet donné. Tu choisis le premier voisin venu et tu recommence. Si à un moment donné il n'y a plus de voisin, cette branche de l'exploration a échoué et tu remonte essayer une autre branche.

Tu t'arrête bien sûr quand tu arrive sur la sortie. Cela se code simplement en utilisant la récursivité.

Le plus simple est d'utiliser une fonction booléenne qui répond si elle a déjà trouvé la sortie ou pas. Tu aura besoin d'un tableau de booléen indiquant si tu as déjà visité un sommet ou pas.

Voila j'espère que c'est assé clair :)

---

Oui, ça d'accord, mais mon problème est plus dans l'algo génétique, je recherche une fonction d'évaluation de la population indépendante du type de labyrinthe, et pour celà j'ai besoin de coder correctement ma population, et c'est la que je sèche :cry: :cry:

Ok d'accord je vois, j'ai il y a quelques mois fais cet algo génétique pour sortir d'un labyrinthe je vais donc te donner le lien qui m'a beaucoup aider à le faire :)
http://www.mines.inpl-nancy.fr/~tiss...genetique.html

Tu t'apercevra ensuite qu'il y a pas mal de petites améliorations possibles;)

Merci, je connais ce lien et c'est à partir de celui-ci que j'ai commencé à travailler sur ces algos.
Peut-être devrais-je le relire de façon plus approfondie, car tel que je suis parti j'arrive à une impasse, ma fonction d'évaluation dépendant absolument du labyrinthe donné.

Pour arrivé à ce résultat oui tu as du peut-être te concentré sur quelque chose de trop précis (en l'occurrence ici un labyrinthe particulier).

Bien après avoir réfléchi, voici mon humble avis sur le problème de Trap D :

Tout d'abord : y aura-t-il plusieurs solutions ? si oui un algo génétique me parait mal adapté :

En effet quel sera ton (tes) objectifs ?

1) Trouver toutes les solutions du labyrinthe ?
Dans ce cas il te faut faire une recherche systématique de tous les chemins et ce n'est pas le but de l'algo génétique

2) Trouver une solution ?
Mais a) La meilleur solution (voir 4) ) ? ou b) N'importe quelle solution ?

Selon moi le choix de l'algo génétique ne peut s'appliquer qu'à l'objectif 2)b).

Ensuite, (mais je ne crois pas que ce soit ce que tu recherche) a tu également pour objectif des contraintes autres :

3) Trouver le plus rapidement une solution ?

4) Trouver la solution la plus courte ou qui rempli le mieux certains critères (ce qui rejoint le 2)a) )
Dans ce cas, il te faudra envisager tous les autres chemins possibles, et les classer, ce qui n'est pas non plus le but de l'algo génétique.


Et dans le cas d'une seule solution (mais ce n'est alors plus un cas général), toutes ces questions ne se posent bien évidement plus puisque tu n'a qu'un seul chemin possible.

Evaluer une population indépendamment du type de labyrinthe me parait très très délicat : en effet, les solutions peuvent être totalement farfelues, partir en arrière, pour revenit, etc... Cela n'obéit à aucune logique déterminée.

Dans ton labyrinthe, a un moment donné, tu ne peut connaître que les éléments suivants : ta postion, les choix qui s'offrent à toi, le parcour effectué pour venir à cette position, et eventuellement les parcours précédents pour essayer de sortir du labyrinthe, et eventuellement aussi la (les) position de l'arrivée.

Dans ces conditions, comment évaluer un individu ? La distance a vol d'oiseau du point atteint au point d'arrivée peut ou peut ne pas etre efficace, tout dépend du labyrinthe (mais ce n'est pas le cas général).

Après faut voir si tu connais les positions d'arrivée... Si tu ne les a pas... rien à faire je pense (dans le cas ou tu génererais un labyrinthe aléatoirement).

Mais dans tous les cas, comment dire si un individu est meilleur qu'un autre ? Sur quel critère objectif et indépendant du labyrinthe se baser pour répondre à cela ? A mon avis tu doit te baser sur la direction : plus tu sera loin de l'arrivée, plus tu devra avoir tendance à t'en rapprocher...
Donc plus tu sera à droite, plus ton algo devra sélectionner des chemins qui tourne à gauche... cad revenir a la dernière intersection et tourner à gauche...

Le problème selon moi vient plus de la fonction d'évaluation que de la manière de coder les individus : car de n'importe quelle manière qu'ils soient codés, cela reprèsente toujours la même chose : un chemin donné. Les codages sont interchangeables.

J'ai vu également que tu n'interdisais pas les retours en arrière : pourquoi ? Selon moi retourner en arrière est dans tous les cas inutile.
Il est inutile de repasser par ou tu es passé.

Voila beaucoup de texte pour tenter de faire avancer le problème, mais j'espère que tout n'est pas inutile :mrgreen:

Tout dépend de comment tu code ton algo génétique, il peut très bien être fait pour trouver le chemin le plus court ou être multi objectif ;)

Mais sinon la méthode est assé bien résumé oui :)

cs_ntd >> tes remarques sont tout à fait judicieuses, mais je persiste à penser que la solution dépend d'un codage correct du problème au départ.
Je n'ai pas encore eu assezde temps pour y réfléchir de manière approfondie, il va falloir que je lise un peu plus de doc autour de ça.