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

Votre navigateur ne prend pas en charge Canvas.
DépartVillesTrajet gloutonTrajet optimal (optionnel)

Cliquez sur une ville pour la choisir comme point de départ. Le circuit se recalcule sans changer les positions.

📊 Comparaison des méthodes

Plus proche voisin—
Optimum exact—
Écart relatif—

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

ÉtapeDéplacementDistanceCumul

🧠 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.

💡 Exercice : générez huit villes, changez le départ et observez l'écart à l'optimum. Pourquoi le meilleur choix local ne garantit-il pas le meilleur circuit global ?