Discussion :

[cs_ntd]

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

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

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

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

[cs_ntd]

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

[snake264]

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

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 Après il est sur que tu peut te créer ton propre algo à partir de ceux-là

[Trap D]

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 ?

[snake264]

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

[Trap D]

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 ?

[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