 |
The Traveling Salesman Problem (TSP), en français : le problème du voyageur de commerce, est un nouveau projet de mathématiques lancé il y a tout juste un mois par Markus Weltin (un habitant des Samoa Américaines). Quelques précisions techniques : Une unité dure environ 1h sur un processeur Q6600, et utilise seulement 900 Ko de mémoire vive. C'est donc encore un projet parfaitement adapté pour les plus petites configurations. |
Explication du problème : Le problème du voyageur de commerce n'est pas très difficile à expliquer. En partant d'un groupe de villes données, il consiste à visiter une fois chacune des villes (une seule et unique fois) tout en minimisant la distance de vos déplacements. Ce problème qui paraît à tort élémentaire est effectivement anodin pour un petit nombre de villes, mais, lorsque vous ajoutez d'autres villes, le nombre de chemins possibles crève le plafond. Il ne faut donc pas s'étonner si le problème du voyageur de commerce est classé dans la catégorie des problèmes NP-complets. Dans ce problème, le nombre de chemins hamiltoniens est égal à n!/2 où n correspond au nombre de villes qui composent le problème.
Une
solution générale efficiente n'a pas encore
été découverte. Les
mathématiciens ont conclu
que le meilleur moyen était d'utiliser un algorithme avec
des polynômes
variant en rapport avec le nombre de villes. À l'heure
actuelle, la
meilleure solution varie de façon exponentielle en fonction
du nombre
de villes.
C'est là
qu'intervient le projet BOINC-TSP. Le projet TSP se voit confier la
lourde tâche qui consiste à
trouver une solution optimale pour un TSP de 48 villes en utilisant la
méthode par force brute. Une fois que le ou les
chemins optimaux seront connus, nous pourrons débuter
la résolution du problème à l'aide
d'autres algorithmes
(algorithmes
génétiques, méthode
des plus proches voisins, recuit
simulé
et algorithme
par colonies de fourmis).
Le projet utilise 48 villes des États-Unis, un point de départ à Washington et un point d'arrivé à Montgomey dans l'Alabama. Voici une représentation du chemin le plus court trouvé par les premiers calculs (solution provisoire).