Le problème du voyageur de commerce
La tournée la plus courte passant une fois par chaque ville : explosion du nombre de tournées, construction par le plus proche voisin, amélioration par échange de deux arêtes et borne par l'arbre couvrant minimal.
- 23 cartes
- 5 thèmes
- Gratuit
Le programme, thème par thème
Le poids de chaque thème suit celui que lui donne l'examen.
- Notions
- Questions
- Ranger et relier
- Les chiffres
- Mises en situation
Quelques cartes du deck
Problème du voyageur de commerce : de quoi s'agit-il ?
Voir la réponse
Étant données des villes et les distances entre elles, trouver la tournée la plus courte qui passe une fois par chaque ville et revient à son point de départ.
Il modélise des tournées de livraison, le perçage de circuits imprimés, l'ordre des tâches d'une machine. Il est NP-difficile : aucun algorithme polynomial n'est connu.
Voici les distances entre cinq villes. Le plus proche voisin, depuis A, donne une tournée de quelle longueur (retour à A compris) ?
```text
A B C D E
A . 5 11 10 4
B 5 . 7 11 9
C 11 7 . 12 11
D 10 11 12 . 3
E 4 9 11 3 .`- 36
- 31
- 25
- 40
Voir la réponse
36
A → E (4), E → D (3), D → B (11, contre 12 pour C), B → C (7), C → A (11) : 36. 31 est la tournée optimale A-B-C-D-E-A ; 25 oublie le retour vers A ; 40 est la longueur d'une autre tournée, A-B-E-D-C-A.
Avec n villes et des distances symétriques, il existe … tournées distinctes : on fixe la ville de départ et on ne distingue pas un sens de parcours de l'autre.
Voir la réponse
Avec n villes et des distances symétriques, il existe (n − 1)! / 2 tournées distinctes : on fixe la ville de départ et on ne distingue pas un sens de parcours de l'autre.
(n − 1)! ordres pour les autres villes, divisés par 2 parce qu'une tournée et son inverse ont la même longueur. Pour 5 villes : 4! / 2 = 12.
Cycle hamiltonien : de quoi s'agit-il ?
Voir la réponse
Cycle d'un graphe qui passe exactement une fois par chaque sommet.
Une tournée est un cycle hamiltonien du graphe complet des villes ; sa longueur est la somme des distances de ses arêtes.