Boinc - Equipe de la Science

Site de la miniteam Equipe de la Science composante de L’Alliance Francophone sur la grille de calcul partagé et bénévole BOINC.
Accueil du site > 7.3-Projets Sciences physiques, Chimie et Mathématiques > Le voyageur de commerce rencontre le calcul distribué.
  • Brève

  Le voyageur de commerce rencontre le calcul distribué.

jeudi 14 février 2008

Traduction d’un article publié par International Science Grid this Week

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.

capitales etats-unis 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.

Markus Weltin, responsable du projet TSP