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).
Cet article a été publié le 04-12-2007 22:06. Vous pouvez suivre les commentaires suscités par cet article grâce au fil RSS 2.0. Vous pouvez laisser un commentaire.
Dernière mise à jour 21-03-2008 21:55
Vos commentaires (0)
Seul les utilisateurs enregistrés peuvent commenter un article.
