AccueilEcologie Le voyageur de commerce rencontre le calcul distribué.
Le voyageur de commerce rencontre le calcul distribué.
TSP
Le
problème du voyageur de commerce (TSP) est résolu
lorsque le "commercial" visite chacune des n villes en couvrant la
distance la plus faible. Le chemin le plus court est ce que
l'on appelle un circuit hamiltonien. Il
n'existe aucune méthode
généralisée permettant de trouver les
solutions TSP.
Image : Wolfram Mathworld
En mathématique, le problème du voyageur de
commerce (Traveling Salesman Problem, TSP)
est ce que l'on appelle un classique : quel chemin permet de
visiter une seule et unique
fois un nombre de villes donné tout en minimisant la
distance parcourue. Lorsque l'on réfléchit au
problème pour un
petit nombre de villes,
la solution parait simpliste. Cependant, au fur et à mesure
que le nombre de villes s'élève, la
résolution
du problème surpasse rapidement la
capacité de la plupart des micro-ordinateurs. Il
faudrait par exemple 1047 années
pour vérifier de manière exhaustive toutes les
possibilités permettant de relier 48 villes, et ce
en considérant que vous puissiez passer en revue un million
de possibilités par seconde.
Malgré de nombreuses recherches, aucune solution
générale n'a encore pu être
apportée pour résoudre le problème TSP.
Mais qui se soucie
réellement du voyageur de commerce ?
Avons nous
vraiment besoin de savoir quel est
l'itinéraire le plus court pour qu'un
voyageur de commerce vienne sonner à votre porte ? Non, mais
la forme générique du
problème est utilisé
dans la conception
des circuits imprimés, le partitionnement des
données, l'analyse des structures cristallines,
l'ordonnancement, pour découper les matériaux et
bien plus encore.
Représentant
distribué
Le premier objectif du
projet TSP est de
réaliser une recherche exhaustive pour un
problème TSP
à 48 villes. Une fois que le chemin optimal sera connu, nous
testerons différents algorithmes de recherche pour mesurer
leur aptitude à trouver le chemin optimal.
L'étape suivante consistera à observer si la
combinaison
d'algorithmes de recherche et de tactiques par force brute peuvent
aboutir à un résultat optimal. Ensuite, viendra
le temps
du banc d'essai de toutes théories en
s'intéressant à de très grands
problèmes TSP.
Les débuts
Le projet TSP a
débuté comme une
sorte
d'étude de faisabilité. Je (Markus Weltin)
voulais juste prouver que je pouvais être capable de lancer
ce
genre de projet. Quelques-uns de mes amis se sont joint au projet.
Le
premier objectif du projet TSP consiste à calculer la
solution optimale d'un problème contenant 48 villes des
Etats-Unis (les 48 capitales). De nouvelles solutions sont constamment
calculées par l'utilisation de la grille de calcul
partagé volontaire fonctionnant sous BOINC.
Image : TSP
Mais les mots circulent extrêmement vite, et avant que j'ai
eu le temps
de m'en apercevoir, un groupe d'alpha testeurs était
dejà présent sur
le forum pour encourager le projet. Selon allprojectstats.com,
3000 ordinateurs et 1200 utilisateurs participent au projet, un grand
merci à la communauté BOINC.
Pourquoi TSP fonctionne :
un grand merci
Il existe
très peu de logiciels incontournables (Killer
application) dans ce monde, mais BOINC en fait
très certainement partie.
Certaines des personnes les plus intelligentes, aimables, modestes et
patientes à travers le
monde sont toujours prêtent à aider. La
communauté BOINC fournit une aide dans tous les aspect qui
font qu'un projet puisse fonctionner : le développement du
code, la configuration
du serveur, les conseils à l'utilisateur final, le
système d'attribution des points, l'installation du client,
le développement de l'application, ...
Ainsi, j'ai écrit le logiciel, mais c'est la
communauté BOINC qui maintient le projet. Les gens ont pris
volontairement de leur temps pour écrire des applications
pour différentes plateformes (y compris récement
une application pour les PS3), ou pour mettre au point des
applications optimisées. Tous les graphismes du site
internet ont été gracieusement donnés
par des membres de la communauté BOINC.
