# Problème du voyageur de commerce

**Thème :** Maths · Maths appliquées  
**Page :** https://curium.ctopass.com/c/probleme-du-voyageur-de-commerce  
**Mise à jour :** 2026-09-30

## Les trois niveaux

### Débutant — Combien d'itinéraires différents un livreur peut-il suivre pour visiter 20 villes ?

Plus de soixante millions de milliards. Chaque ville ajoutée multiplie le nombre de tournées possibles, au lieu de simplement l'augmenter. Un ordinateur qui en testerait un million par seconde y passerait près de deux mille ans.

### Intermédiaire — Comment trouve-t-on une bonne tournée de livraison sans essayer toutes les possibilités ?

On se contente d'une tournée presque parfaite, trouvée par des heuristiques. La plus simple file toujours vers la ville la plus proche pas encore visitée ; sur des villes placées au hasard, elle donne un trajet environ 25 % plus long que le meilleur. Les méthodes modernes descendent à 2 ou 3 % de l'optimum, même avec des millions de points.

### Expert — Pourquoi un algorithme rapide pour le voyageur de commerce vaudrait-il un million de dollars ?

Parce que la question « existe-t-il une tournée plus courte que tant de kilomètres ? » est NP-complète. Un algorithme exact et rapide pour elle en donnerait un pour tout problème de la classe NP, et trancherait la question P = NP, l'un des sept problèmes du millénaire mis à prix par l'institut Clay.

## À explorer ensuite

- [Problème P égale NP](https://curium.ctopass.com/c/probleme-p-egale-np.md)
- [Programmation linéaire](https://curium.ctopass.com/c/programmation-lineaire.md)
- [L'algorithme](https://curium.ctopass.com/c/l-algorithme.md)
- [Théorie des graphes](https://curium.ctopass.com/c/theorie-des-graphes.md)
- [Dilemme du prisonnier](https://curium.ctopass.com/c/dilemme-du-prisonnier.md)
- [Méthode de Monte-Carlo](https://curium.ctopass.com/c/methode-de-monte-carlo.md)
- [Pourcentage](https://curium.ctopass.com/c/pourcentage.md)
- [Proportionnalité](https://curium.ctopass.com/c/proportionnalite.md)
- [Trigonométrie](https://curium.ctopass.com/c/trigonometrie.md)
- [Valeur absolue](https://curium.ctopass.com/c/valeur-absolue.md)

---

Curium — La connaissance, une question à la fois.

App Store : https://apps.apple.com/fr/app/curium/id6793886587
Google Play : https://play.google.com/store/apps/details?id=com.ctopass.curium