Méta-heuristiques chéries

[morice]

Bonjour à tous.

Bon comme vous le savez peut-être, je suis un accro de la prog, et ça fait près d'un an que je me déchaine pour connaitre de nouvelles méta-heuristiques.

Explications:
:fleche: méta-heuristiques : ce sont des algorithmes spéciaux permettant la simulation et l'expérimentation sur des choses que l'on n'arrive pas à faire par des moyens classiques

Par wikipedia: http://fr.wikipedia.org/wiki/Méta-heuristique

Donc malgré mes recherches, je ne trouvepas les explications algorithmiques de toutes ces méta-heuristiques.

Pour le moment, je me concentre surtout sur la recherche du plus court chemin.
A ma connaissance il n'existe que trois algorithmes pour cette méta-heuristique là:
:fleche: Dijkstra (méthode des graphes, en principe)
:fleche: A* ou méthode de l'étoile (étoile de valeurs croissantes)
:fleche: Ford-Bellmann (ou quelque chose comme ça)

J'ai compris le principe des deux premières que je détaillerai plus tard, bien que je n'arrive pas encore à les mettre en place, mais la troisième je ne trouve aucune info intéressante.

 

[IUPGSI]

Iopla

Tu te poses de ces question :wacko: :laugh:. Voici notre cours sur les algos à fonction heuristique de licence GSI (l'année dernière :wink2. Est-ce que ton algo démontre une théorie calculable ? Il existe des problèmes dont les algos seraient incapables de les calculer : exemple jeux d'échec. En effet, aux échecs, vous avez 10 puissance 19 coups possibles de jouer le meilleur coup ce qui revient en gros à 10 puissance 19 millisecondes (300 millions d'années pour trouver le meilleur coup d'échec à jouer).

Ecrire une heuristique, c'est écrire une méthode (un algo) qui produit la plupart du temps un résultat acceptable mais pas nécessairement optimal en un temps raisonnable.Un algo peut être heuristique de plusieurs façons : algo intraitable dès que la puissance est trop importante et des comportements polynomiaux ou exponentiels.
Voilà pour une petite intro :wink2:.

Idem Momo, je ne connais que les deux premiers mais le troisième :blink: ascompris;.

 

[morice]

Et là je ne parlais que du problème du plus court chemin, par contre je connais d'autres méta-heuristiques, mais j'en connais aucune solution.

:fleche: le recuit simulé
:fleche: recherches avec tabous
:fleche: colonnies de fourmis (je sais qu'il peut servir à résoudre le problème du plus court chemin par la simulation de déposition de phéromones par période constante et recherche par le maximum)
:fleche: essaims particulaires
:fleche: ...

Enfin voilà, si quelqu'un a des explications, voir mêmes des algorithmes à proposer, je suis preneur.
Je vais consacrer un autre post à la suite de celui-ci pour expliquer A* puis un autre pour Dijkstra.
Je les intègrerai ensuite au Blog Info

 

[morice]

Alors voilà l'explication pour A*, mais j'ai un problème dans la mise en oeuvre, je détaille après.

Tout d'abord, le problème général du plus court chemin.

Vous avez un tableau présenté ci-dessous. Sachant que nous partons de A vers F, pas de mouvements en diagonale, les cases B sont des obstacles infranchissables.

A0000
B0000
00BB0
0B000
00F00

Ici de façon visuelle, nous devinons facilement que la solution est de 8 mouvements. Par contre pour un ordinateur, ce n'est pas aussi simple.
Solution ici avec les croix:

A*000
B*000
**BB0
*B000
**F00

Voyons ce que nous propose les différents algorithmes.

A*
L'idée est de définir un nouveau tableau contenant une étoile de valeurs croissantes partant du point d'arrivée et s'étendant dans toutes les directions.
Voici ce que donne le tableau une fois modifié:
A5456
B4345
43BB4
3B123
21F12
Pour préciser, ici, A=6 et F=0.
Nous partons de la fin (tout à fait logique :wink2: ) et par recherche de valeur supérieure, nous progressons dans le tableau jusqu'à A. Forcément, il existe plusieurs directions possibles dès le début. Il suffit d'établir un processus de circulation standard.
Ici nous choisirons haut, gauche, bas et enfin droite (hgbd). Bien évidemment, nous éliminerons systématiquement la direction nous contraignant à revenir sur nos pas.

Si l'on suite la procédure proposée, nous obtenons donc le trajet suivant (*):
A545*
B434*
43BB*
3B***
21F12
Et là nous sommes bloqués.
Nous en concluons que ce n'est pas le bon trajet. On change donc la procédure en la faisant tourner d'un quart de tour, nous obtenons: gauche, bas, droite, haut (gbdh). Nous obtenons ainsi:
A5456
B4345
*3BB4
*B123
**F12
Encore une fois nous sommes bloqués, et pourtant ce bout de trajet appartient clairement au bout de trajet repéré visuellement auparavant...
La technique est dond d'inverser la lecture. Nous conservons un historique des trajets effectués bien évidemment. Maintenant l'étoile croissante part de A:
A1234
B2345
23BB6
3B567
45F78
Nous utilisons la première procédure de lecture (hgbd). Et nous obtenons:
A*234
B*345
2*BB6
3B567
45F78
Nous sommes encore bloqués, mais cette fois-ci, nous contrôlons si il y a un lien avec les possibilités de la première lecture.
Nous concluons qu'il n'y a pas de liaison entre la première hypothèse et celle-ci, par contre il y en a une avec la seconde (qui est également la bonne solution).

Bien évidemment, ce tutoriel est simplifié, pour être sur de trouver le bon chemin, nous devrions essayer les 4 procédures possibles (hgbd, gbdh, bdhg et dhgb) au point de départ comme au point d'arrivée. Et voir même rajouter des repères sur des points utilisés par chacune des quatre procédures afin de déterminer si il existe un chemin le plus court possible depuis ces points vers l'arrivée, en venant du point de départ et entre eux.

Mais moi j'ai un problème dès le début. Cela marche à peu près bien quand je simule avec le départ au dessus et sur la gauche de l'arrivée, sinon systématiquement, il recule ou fait n'importe quoi...

Dijkstra:
J'expliquerai demain, là je suis naze... :chessy:

 

[morice]

Voilà les explications des trois algorithmes du plus court chemin par Wikipedia, du coup j'ai plus envie de les décrire moi-même:

A* - Dijkstra - Ford-Bellman

Je les lis, j'apprends et si j'ai le temps, je vous les propose en C, en PHP et en Pascal :chessy: