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
Liens
du Projet
|
L'Alliance
Francophone
|
Statistiques
|
|
- 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