Introduction

Pour se déplacer d'un point à un autre sur une carte, il est souvent utile de connaître le plus court chemin. Un réseau de sommets étant fixé, vient le problème de détermination de chemins optimaux dans le réseau. J'aborderai ici d'abord le problème de plus courts chemins d'un sommet à un autre avec les algorithmes de Bellmann-Ford, et A*. La complexité des réseaux nécessite parfois l'intervention de l'informatique, et donc la recherche d'algorithmes efficaces. L'algorithme de Bellmann-Ford résout le problème formellement, tandis que l'algorithme A* en est une résolution plus efficace, adaptée aux jeux vidéo. Enfin, on peut aussi avoir besoin de rechercher le plus court chemin passant par tous les sommets : c'est le problème du voyageur de commerce, résolu par les algorithmes 2-opt et de Lin-Kernighan.


Méthode de travail, expériences personnelles

Lors de l'étude de différents algorithmes de plus courts chemins, j'ai souhaité faire moi-même des tests sur ordinateur pour les expérimenter. J'ai ainsi réussi à programmer l'algorithme de Bellman-Ford en langage Caml, puis l'algorithme A* en ActionScript (Flash), qui m'a donné beaucoup de difficultés à cause de son implémentation complexe. Pour la suite, il se trouvait qu'un ami s'intéressait au même domaine que moi pour les TIPE. Nous nous sommes donc associés et nos recherches se sont orientées vers le problème du voyageur de commerce. L'algorithme le plus simple de résolution de ce problème s'appelait le 2-opt, dont nous avons trouvé un algorithme. Nous avons donc essayé de l'interpréter en Caml. Ce n'est qu'après de nombreux essais d'implémentations que nous somme parvenus à obtenir un programme opérationnel satisfaisant. Mais nous ne voulions pas nous arrêter là. Il existe un autre algorithme, dit de Lin-Kernighan, plus efficace mais plus subtil à comprendre et plus compliqué à implémenter, permettant de résoudre ce problème. Ayant trouvé une documentation complète de cet algorithme, j'ai décidé de le programmer lui aussi, malgré les difficultés supplémentaires qui s'annonçaient par rapport au 2-opt. Le document fournissait là encore l'algorithme, mais cette fois destiné à un langage impératif. Il m'a donc fallu réécrire l'ensemble du code pour adapter les structures impératives au langage Caml. Alors, j'ai pu aborder l'interprétation du code en Caml, bien que le programme que j'ai produit ne s'avère pas très satisfaisant pour la tâche qu'il devrait accomplir.
Commentaire : Après la rédaction de cette fiche synoptique, j'ai continué à travailler sur l'algorithme. Il suffisait de résoudre encore quelque bugs et celui-ci a fini par marcher correctement.


Plan

Parmi tous les algorithmes que j'ai étudiés, j'ai choisi d'en présenter trois, chacun représentant un problème différent et un principe de base différent, pour avoir une vision globale du sujet :
* L'algorithme de Bellmann-Ford
* L'algorithme A*
* L'algorithme de Lin-Kernighan


Contacts avec des professionnels

Pour la recherche de plus courts chemins :
* Sociétés de calculs d'itinéraire en ligne : Google Maps, ViaMichelin, Mappy
* Sociétés proposant des services de GPS : Mappy GPS et Tomtom
* Développeurs de jeux vidéo utilisant : Gas Powered Games
Les sociétés ayant répondu ont dit transférer mes demandes à leurs experts, mais sans suite.

Pour le problème du voyageur de commerce :
* Giga-Concept, Opti-Time : refus de dévoiler leurs algorithmes
* Keld Helsgaun, professeur associé en informatique : pas de réponse


Bibliographie

Livre :
* Introduction à l'algorithmique de Thomas H. Cormen, Charles E. Leiseron, éditions Dunod, partie "plus courts chemins à origine unique"

Sites Internet :
* http://www.policyalmanac.org/games/aStarTutorial.htm - Pathfinding A* pour les débutants
* http://fr.wikipedia.org/wiki/2-opt - présente l'algorithme 2-opt en pseudo-code
* http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.25.4908&rep=rep1&type=pdf - Une implémentation de l'algorithme de Lin-Kernighan