Discuter:Problème du voyageur de commerce

Un article de Wikipédia, l'encyclopédie libre.

	Problème du voyageur de commerce fait partie du projet Mathématiques, qui a pour but d'enrichir le contenu de Wikipédia sur les sujets liés aux mathématiques. Si vous voulez participer, vous pouvez modifier cet article ou visiter la page du projet, où vous pourrez vous joindre au projet et consulter la liste des tâches et des objectifs. Le portail Mathématiques pourrait aussi vous intéresser.
Ébauche	Cet article a été classé comme d'Avancement ébauche selon le Tableau d'évaluation du projet. (Voir les statistiques)
Moyenne	Cet article a été classé comme d'Importance moyenne selon le Tableau d'évaluation du projet.

Personne n'a encore entrepris de détailler les différentes méthodes (algorithmes génétiques, fourmis...) pour résoudre le problème? Dès que j'ai un peu de temps je m'y mettrais...

"On ne sait pour le moment s'y attaquer industriellement que de manière algorithmique, et l'on bute donc rapidement sur une explosion combinatoire." Cette phrase ne me parait pas très juste, je l'ai donc modifié. Yold 15 sep 2004 à 21:16 (CEST)

Je mentionnais juste que des approches non-algorithmiques existaient (en particulier utilisant des séquences d'ADN), mais qu'elles ne sont pour le moment qu'au stade de la recherche, sur de petits problèmes. Je replace en revanche explosion combinatoire, qui constitue bien le problème essentiel de cette approche algorithmique. Un simple clic renseignara ainsi les curieux ;o) François-Dominique 15 sep 2004 à 21:22 (CEST)

Ok, ça me plait bien tel que c'est là. C'est vrai que le mot clef est important.

J'ai un doute quant au "passant une et une seule fois par chaque sommet" dans la partie Problème détaillé. Dans le cas où le graphe contient une configuration avec 3 sommets reliés deux à deux et dont les poids des arètes de respectent pas l'inégalité triangulaire (ce qui arrive forcément dans un graphe non complet, si on considère que l'abscence d'arète est assimilable à l'existance d'une arète de poids infini), s'interdit-on tout de même de repasser par un sommet déjà visité ? Cela restreindrait le problème aux graphes contenant au moins un cycle hamiltonien, et il ne me semble pas que ce soit le cas... J'attends vos réponses avant de modifier...

D'autre part, je ne sais pas comment introduire cela dans l'article, mais j'aimerais préciser que bien que ce problème soit à priori exponentiel en temps (la version existentielle est un problème NP-complet), il existe des approximations calculables en temps polynomial (on peut, en se liberant de la contrainte de passer une seule fois par chaque sommet, calculet un chemin au pire deux fois plus long que l'optimum, en construisant l'arbre recouvrant de poids minimum, et en "faisant le tour" de cet arbre), pour peu que le graphe respecte l'inégalité triangulaire. On passe donc ainsi exactement deux fois par chaque sommet du graphe, et par chaque arète de l'arbre. Quelqu'un a une idée quant a une manière élégante d'insérer ça ? Jamian 7 janvier 2006 à 18:54 (CET)

La partie sur les colonies de fourmis de me paraît pas très pertinente par rapport à l'article. Il faudrait réduire cette partie, qui peut être transférée dans l'article "colonies de fourmis". Au niveau des citations, il y a un peu d'abus aussi, ça fait un peu dépliant publicitaire. Si personne ne râle d'ici quelque temps, je propose de supprimer purement et simplement les passages qui n'ont pas un lien direct avec le sujet. François Clautiaux (d) 21 février 2008 à 20:32 (CET)