Le problème du voyageur de commerce (TSP)

INSCRIPTION Télécharger Boinc (tutorial) URL du projet : http://bob.myisland.as/tsp/

Trouver le chemin le plus court pour visiter les 48 capitales des Etats-Unis. Différents algorithmes seront utilisés. 

(algorithmes génétiques, force brute, méthode des plus proches voisins, recuit simulé et algorithme de colonies de fourmis).

Systèmes d'exploitation : FreeBSD, Linux, Linux 64 bits, Mac OS (PPC, Intel), Windows, Windows 64 bits

• Début du projet : 4 novembre 2007
• Statut : Alpha test
• Résultats : Le chemin le plus court (solution provisoire)
  

 Le responsable du projet, Markus Weltin, habite dans les Samoa américaines, un archipel situé dans l'Océan Pacifique à 4000 km au large de la côte Est de l'Australie.

Explication du projet

Le problème du voyageur de commerce (TSP) 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 à tord é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 conclus que le meilleur moyen était d'utiliser un algorithme avec des polynômes variant en rapport avec le nombre de villes. A 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(s) chemin(s) optimal sera /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 de colonies de fourmis).

Voir aussi l'article wikipédia : Le problème du voyageur de commerce