Page d'accueil
encyclopedie-enligne.com en page d'accueil| Page d'accueil |
encyclopedie-enligne.com en page d'accueil |
|||||
| Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées | ||||||
L'énoncé du problème du voyageur de commerce est le suivant : étant donné n points (des « villes ») et les distances séparant chaque point, trouver un chemin de longueur totale minimale qui passe exactement une fois par chaque point (et revienne au point de départ).
Ce problème est plus compliqué qu'il n'y paraît; on ne connaît pas de méthode de résolution permettant d'obtenir des solutions exactes en un temps raisonnable pour de grandes instances (grand nombre de villes) du problème. Pour ces grandes instances, on devra donc souvent se contenter de solutions approchées, car on se retrouve face à une explosion combinatoire : Le nombre de chemins possibles passant par 69 villes est déjà un nombre de 100 chiffres. Pour comparaison, un nombre de 80 chiffres permettrait déjà de représenter le nombre d'atomes dans tout l'univers connu!).
Ce problème peut servir tel quel à l'optimisation de trajectoires de machines-outils par exemple, pour minimiser le temps total que met une fraiseuse à commande numérique pour percer n points dans une plaque de tôle. Il se posait également pour optimiser la vitesse de tracé d'une structure (en BTP, par exemple) par une table traçante à l'époque où ces périphériques étaient mécaniques, et non électroniques comme aujourd'hui.
Plus généralement, divers problèmes de recherche opérationnelle se ramènent au voyageur de commerce. Un voyageur de commerce peu scrupuleux serait intéressé par le double problème du chemin le plus court (pour son trajet réel) et du chemin le plus long (pour sa note de frais).
Voici un énoncé plus formel du problème du voyageur de commerce sous forme de problème de décision.
Données :
une fonction de coût sur les
arcs ;
Question : Existe-t-il un circuit hamiltonien (c'est-à-dire ne passant qu'une et une seule fois par chaque sommet) dont le coût (la somme du coût des arcs qui le composent) est inférieur ou égal à ?
Ce problème est NP-complet. On ne connaît donc pas d'algorithme capable de déterminer en temps polynomial (en fonction de la taille de ) si la réponse à la question est oui ou non.
Le problème de minimisation équivalent consiste à trouver le circuit hamiltonien de coût minimum. Ce problème est inapproximable, c'est-à-dire qu'il n'existe pas d'algorithme en temps polynomial capable de fournir une solution approchée dont le coût est toujours inférieur ou égal à fois le coût d'une solution optimale où est une constante. Lorsque le graphe vérifie l'inégalité triangulaire, alors le problème devient approximable. Le meilleur algorithme connu garantit que toute solution sera au pire fois plus coûteuse qu'une solution optimale. Cet algorithme a été imaginé en 1976 par Nicos Christofides.
