Qu'est-ce que le problème du voyageur de commerce ?

C'est le problème de trouver l'itinéraire le plus court possible qui visite un ensemble donné de villes exactement une fois chacune et revient à la ville de départ — un problème d'optimisation NP-difficile classique.

Qu'est-ce que l'algorithme de Held-Karp ?

C'est un algorithme de programmation dynamique qui résout exactement le problème du voyageur de commerce en temps O(n² · 2ⁿ) en suivant le coût minimal pour atteindre chaque combinaison de (sous-ensemble de villes visitées, ville actuelle), nettement mieux que le O(n!) de la force brute.

Cela trouve-t-il le circuit optimal ou juste un bon circuit ?

Le circuit optimal exact — Held-Karp n'est pas une heuristique ou une approximation ; il est garanti de trouver le véritable circuit de coût minimal, contrairement aux heuristiques plus rapides comme le plus proche voisin ou 2-opt.

Pourquoi ce solveur est-il limité à 12 villes ?

Le temps et l'espace O(n² · 2ⁿ) de Held-Karp croissent toujours de manière exponentielle — 12 villes gardent le calcul confortablement instantané dans un navigateur, tout en couvrant la grande majorité des exemples saisis manuellement que les gens veulent résoudre exactement.

La matrice de distances doit-elle être symétrique ?

Non — ce solveur fonctionne avec des distances asymétriques (où le coût de A à B diffère de celui de B à A), ce qui couvre à la fois des exemples simples de distance routière symétrique et des cas directionnels comme les rues à sens unique ou les coûts de vol.

Quel algorithme devrais-je utiliser pour plus de 12 villes ?

Au-delà de la plage où une solution exacte est réalisable, les approches pratiques passent à des heuristiques (construction du plus proche voisin, recherche locale 2-opt ou 3-opt, ou algorithmes génétiques), qui échangent la garantie d'optimalité contre la vitesse sur des instances beaucoup plus grandes.

En quoi cela diffère-t-il du Calculateur d'Arbre Couvrant Minimal ?

Un arbre couvrant minimal connecte chaque ville avec le poids total d'arêtes le plus faible mais autorise la ramification et n'a pas besoin de former un itinéraire unique ; un circuit du voyageur de commerce doit être une boucle fermée unique visitant chaque ville exactement une fois, une exigence beaucoup plus restrictive.

Où le problème du voyageur de commerce est-il utilisé dans la vie réelle ?

Il est utilisé dans la planification d'itinéraires de livraison et de logistique, le perçage de circuits imprimés et la fabrication de cartes de circuits, le séquençage de l'ADN, et comme problème de référence pour les algorithmes d'optimisation en recherche opérationnelle.

Solveur du Voyageur de Commerce — Trouvez l'Itinéraire le Plus Court à Travers Chaque Ville

Notre Solveur du Voyageur de Commerce trouve le circuit de coût minimal exact qui visite chaque ville exactement une fois et retourne à la ville de départ, étant donné une matrice de distances entre les villes, à l'aide de l'algorithme de programmation dynamique par masque de bits de Held-Karp — une méthode exacte délibérément limitée à au plus 12 villes puisque le problème est NP-difficile en général.

Réponse rapide

Saisissez une matrice de distances entre villes pour trouver instantanément le circuit aller-retour le plus court exact via la programmation dynamique de Held-Karp.

Matrice de distances

Saisissez une ligne par ville, distances séparées par des virgules, par ex. 0,10,15,20 puis 10,0,35,25. Jusqu'à 12 villes.

Comment utiliser Solveur du Voyageur de Commerce — DP Exacte de Held-Karp en Ligne

1
Saisissez une matrice de distances, une ligne par ville, avec des distances séparées par des virgules, ex. 0,10,15,20 puis 10,0,35,25 et ainsi de suite.
2
La matrice doit être carrée, chaque entrée donnant la distance entre deux villes (les entrées diagonales sont généralement 0).
3
Cliquez sur 'Calculer' pour trouver le circuit optimal exact via la programmation dynamique de Held-Karp.

Pourquoi utiliser Solveur du Voyageur de Commerce — DP Exacte de Held-Karp en Ligne ?

Le problème du voyageur de commerce demande l'itinéraire le plus court possible qui visite chaque ville exactement une fois et revient au départ — un problème NP-difficile classique où vérifier par force brute les (n−1)!/2 circuits possibles devient impossible au-delà d'une poignée de villes. L'algorithme de Held-Karp améliore considérablement la force brute en utilisant la programmation dynamique sur des sous-ensembles : il suit, pour chaque sous-ensemble de villes visitées et chaque ville de fin possible, le moyen le moins coûteux d'atteindre cet état, en construisant à partir de petits sous-ensembles jusqu'à l'ensemble complet en temps O(n² · 2ⁿ) au lieu de O(n!). C'est toujours exponentiel, donc ce calculateur limite le problème à 12 villes, où Held-Karp reste confortablement rapide tout en trouvant le circuit exact, prouvablement optimal (pas seulement une bonne approximation).

Questions fréquentes

Outils similaires

Vérificateur de Chemin Hamiltonien — Visitez Chaque Nœud Une Fois en Ligne

Vérifiez si un graphe a un chemin hamiltonien — un chemin visitant chaque nœud exactement une fois — via une recherche par retour sur trace. Calculatrice gratuite, limitée aux graphes de jusqu'à 10 nœuds.

Calculatrice d'Arbre Couvrant Minimal — Algorithme de Kruskal en Ligne

Trouvez l'arbre couvrant minimal d'un graphe pondéré à l'aide de l'algorithme de Kruskal. Calculatrice gratuite avec une simple saisie de liste d'arêtes et détection de cycles par union-find.

Solveur de Programmation Linéaire — Méthode des Points d'Angle à 2 Variables en Ligne

Résolvez un programme linéaire à 2 variables en trouvant et en évaluant chaque point d'angle de la région réalisable. Calculateur gratuit, maximisez ou minimisez avec des contraintes linéaires.