Probleme du voyageur de commerce.

[Mike_51]

Bonjour je suis en prépa MP, et comme vous le savez peut-etre le theme des TIPE cette année porte sur la dualité. Et j'aimerais étudier le problème de voyageur mais je me demande si il y a bien de la dualité la dedans?
Merci si vous avez des réponses à m'apporter.

[Dominique Lefebvre]

Bonsoir,
Je ne vois pas trop quelle dualité on pourrait bien trouver! Un problème de graphe et d'algorithmique.... On le lie à la complexité calculatoire et on glisse vers les problèmes NP complets... Peut être quelque chose à chercher de ce coté là... Mais rien de bien probant!