De la théorie des graphes à l'optimisation
Chapitre 5 — Cycles, approximations et synthèse globale
Explorez le problème du voyageur de commerce (TSP) : construisez un circuit par plus proche voisin, puis comparez-le à un optimum exact lorsque le nombre de villes le permet.
🧭 Laboratoire interactif du voyageur de commerce
Chaque ville doit être visitée exactement une fois, avant de revenir au départ. Les distances sont euclidiennes et le graphe est complet.
Prêt à commencer.
🗺️ Visualisation du circuit
Cliquez sur une ville pour la choisir comme point de départ. Le circuit se recalcule sans changer les positions.
📊 Comparaison des méthodes
Progression du parcours
Aucune étape effectuée.
Tour glouton : —
Pour n ≤ 10, un algorithme exact de Held–Karp permet une comparaison pédagogique.
📋 Déroulement pas à pas
| Étape | Déplacement | Distance | Cumul |
|---|
🧠 Comprendre les algorithmes
Plus proche voisin : à chaque étape, sélectionner la ville non visitée la plus proche, puis revenir au point de départ. Sa complexité temporelle est O(n²). C'est une heuristique, pas un algorithme d'approximation à facteur constant garanti pour le TSP métrique général.
Held–Karp : une programmation dynamique exacte sur des sous-ensembles de villes. Sa complexité temporelle est O(n² · 2ⁿ), et sa mémoire O(n · 2ⁿ). Ici, elle est limitée à 10 villes pour garder l'interface fluide.
À retenir : une solution gloutonne est toujours un tour réalisable dans ce graphe complet, mais peut être plus longue que l'optimum. Changer la ville de départ peut changer le résultat.