Labo Algo
Labo Algo
Le défi des 250 villes est un concours ouvert à tous et . Il s'agit de créer un logiciel permettant de trouver, le plus vite possible, le chemin le plus court entre 250 villes (voir un exemple à droite).
Voici comment le défi a commencé :
Après avoir découvert le problème du voyageur de commerce (PVC) et les algorithmes génetiques, j'écris en 1996 une première version de mon algorithme permettant de résoudre des petits problèmes (de l'ordre de 25 villes). Cet algorithme est présenté dans ma page sur les algorithmes génétiques en C (1997). En 1998-99, j'en fait une version Delphi sous Windows (GraphGen), en ajoutant la possibilité de changer le nombre de villes et d'afficher graphiquement la solution.
Le 30 Septembre 2000, je reçois un e-mail d'un étudiant en informatique.
Il me dit qu'il travaille depuis un an sur un algorithme permettant de résoudre le problème du voyageur du commerce,
qu'il pense être très performant.
Intrigué, je lui demande plus de détails et je lui envoie une version de mon algorithme écrit en Delphi.
Il me répond que mon programme est intéressant, mais que le sien est bien mieux que le mien ... et il me le prouve en me l'envoyant !
Effectivement, mon algorithme fonctionne bien pour un nombre de villes assez réduit, mais commence à peiner à partir de 75 villes.
Le sien est plus efficace et surtout beaucoup plus rapide !
Sachant que mon programme date un peu, et que j'ai des idées d'amélioration et d'optimisations, je lui propose
de nous mesurer grâce à un défi : trouver le meilleur parcours pour un problème de 250 villes.
(le défi n'a pas de date de fin car il est impossible à ma connaissance de prouver que l'on a trouvé le meilleur chemin)
Quelques temps plus tard, d'autres personnes me contactent pour participer au concours...
Le but est simple : trouver le chemin le plus court entre les 250 villes dont les coordonnées (x, y) sont définies dans le fichier suivant : defi250.csv
Les 250 villes se trouvent dans un carré de 1 x 1, c'est à dire entre les points de coordonnées (0, 0) et (1, 1).
Le format du fichier est le suivant :
nombre de villes total position X de la première ville;position Y de la première ville position X de la deuxième ville;position Y de la deuxième ville position X de la troisième ville;position Y de la troisième ville ...
Extrait du fichier defi250.csv :
250 0.223118073306978;0.216796220745891 0.447559242602438;0.492616587784141 0.569365015253425;0.473787421826273 0.474918519612402;0.033659254200757 ...
Les villes sont numérotées de 0 à 249. Les trajets doivent commencer par la ville 0.
Le logiciel devra fournir le résultat (meilleur trajet trouvé) sous la forme :
n° de la 1ère ville visitée (toujours 0)-n° de la 2ème ville visitée-n° de la 3ème ville visitée...
(si possible dans un fichier, c'est plus pratique...)
Par exemple, voici le début du meilleur parcours :
0-85-24-202-51-05-61-92-37-06-153-32-242-58-155-227-113-126-110-...
Pas besoin d'afficheur dans votre programme, il suffit d'utiliser la petite applet que j'ai créé, à intégrer dans une page html très simple (on en voit un exemple en haut de cette page) :
<html>
<applet code="DisplayTsp.class" width=400 height=400>
<param name="Problem" value="default">
<param name="Parcours" value="0-85-24-202-51-05-61-92-37-06-153-32-242-suite du parcours...">
</applet>
</html>
Dans le même répertoire, placez le fichier DisplayTsp.class (l'applet Java).
Cette applet de visualisation - dont vous voyez une démo un peu plus haut - est un logiciel libre (GPL) dont code source est disponible ici : DisplayTsp
Elle permet calculer la longueur du trajet et de zoomer. Elle peut aussi fonctionner avec d'autres problèmes (nombre de villes différents...)
Bien sûr, vous pouvez utiliser votre propre afficheur pendant le calcul (quelqu'un l'a même implémenté en OpenGL !) mais je vous préviens que cela rique de ralentir fortement le calcul...
Très prochainement je réaliserai une page PHP permettant de s'inscrire et d'envoyer ses résultats facilement. En attendant voici comment faire :
Informations à réunir pour participer :
(Tant que les pages php ne sont pas en place) il se peut que je ne vous réponde pas immédiatement, car mon boulot me prend beaucoup de temps, mais sachez que je me passionne toujours autant pour ce problème, et que le défi est ouvert tant que le site est ouvert !
Labo Algo
Alexandre Aupetit, Avril 2004