Le voyageur de commerce 185
1954
Dantzig et Dijkstra
proposent des méthodes
pour résoudre le problème
du voyageur de commerce.
1971
Cook formule le concept
P versus NP pour les
algorithmes.
2004
David Applegate résout le
problème pour les 24 978
villes de Suède.
sans projet préconçu. Arrivé à Chicago, il fait son travail et il cherche la ville la plus
proche où il pourra se rendre ensuite. Il choisit Dallas de préférence à Albuquerque
et El Paso, parce que c’est à 1 263 km de Chicago, et c’est donc la ville la plus proche
de toutes.
Arrivé à Dallas, il a parcouru 1 136 + 1 263 km. Il doit
ensuite choisir entre Albuquerque et El Paso. Il opte
pour Albuquerque qui est plus proche. D’Albuquerque,
il doit se rendre à El Paso, et après quoi, il a vu toutes
les villes ; son travail terminé, il revient à Bismarck.
Son parcours total est égal à 1 136 +1 263 + 933 + 380
+ 1 770 = 5 482 km. Ce trajet BCDAEB est beaucoup
plus court que le précédent et a donc aussi produit
moins d’émissions carboniques.
Cette façon de faire est souvent appelée la méthode
gloutonne de recherche d’un trajet court. Elle est gloutonne parce que la décision de James Cook est toujours
locale : il se trouve dans une ville particulière et cherche
le meilleur trajet pour quitter cette ville. Avec cette
méthode, il n’essaie jamais d’anticiper plus d’une étape à la fois. Cette méthode
n’a rien de stratégique parce qu’elle ne tient aucun compte du meilleur trajet. Sa
dernière étape étant El Paso, il s’est trouvé obligé de couvrir une longue distance
pour revenir à Bismarck. Un trajet plus court a donc été trouvé, mais est-ce le plus
court ? James est intrigué.
James voit comment il peut tirer profit du fait que seules cinq villes sont concernées. Le petit nombre de villes permet de dresser la liste de tous les trajets possibles
et de choisir ensuite le plus court. Avec cinq villes, il n’y a que 24 trajets à examiner
ou seulement 12 si l’on considère qu’un trajet et son inverse sont équivalents. C’est
autorisé car tous deux sont de même distance. Cette méthode est bien utile à James
Cook car il apprend que le trajet BAEDCB (ou son inverse BCDEAB) est en réalité la
solution optimale puisque la distance à parcourir est de 5 147 km seulement.
De retour à Bismarck, James se rend compte que son voyage lui a pris trop de temps.
Ce n’est pas la distance qu’il veut
réduire, mais le temps. Il trace
un nouveau tableau qui donne le
temps qui sépare les différentes
villes du secteur à parcourir.
James sait que la somme des distances des deux côtés d’un triangle
1831
1421
1136
1641
1263
380
948
933
2021
1770
A
E
C
D
B
Albuquerque
12 (route)
Bismarck
6 (avion)
2 (avion) Chicago
2 (avion)
4 (avion) 3 (avion)
Dallas
4 (route)
3 (avion) 5 (avion) 1 (avion) El Paso
1954
Dantzig et Dijkstra
proposent des méthodes
pour résoudre le problème
du voyageur de commerce.
1971
Cook formule le concept
P versus NP pour les
algorithmes.
2004
David Applegate résout le
problème pour les 24 978
villes de Suède.
sans projet préconçu. Arrivé à Chicago, il fait son travail et il cherche la ville la plus
proche où il pourra se rendre ensuite. Il choisit Dallas de préférence à Albuquerque
et El Paso, parce que c’est à 1 263 km de Chicago, et c’est donc la ville la plus proche
de toutes.
Arrivé à Dallas, il a parcouru 1 136 + 1 263 km. Il doit
ensuite choisir entre Albuquerque et El Paso. Il opte
pour Albuquerque qui est plus proche. D’Albuquerque,
il doit se rendre à El Paso, et après quoi, il a vu toutes
les villes ; son travail terminé, il revient à Bismarck.
Son parcours total est égal à 1 136 +1 263 + 933 + 380
+ 1 770 = 5 482 km. Ce trajet BCDAEB est beaucoup
plus court que le précédent et a donc aussi produit
moins d’émissions carboniques.
Cette façon de faire est souvent appelée la méthode
gloutonne de recherche d’un trajet court. Elle est gloutonne parce que la décision de James Cook est toujours
locale : il se trouve dans une ville particulière et cherche
le meilleur trajet pour quitter cette ville. Avec cette
méthode, il n’essaie jamais d’anticiper plus d’une étape à la fois. Cette méthode
n’a rien de stratégique parce qu’elle ne tient aucun compte du meilleur trajet. Sa
dernière étape étant El Paso, il s’est trouvé obligé de couvrir une longue distance
pour revenir à Bismarck. Un trajet plus court a donc été trouvé, mais est-ce le plus
court ? James est intrigué.
James voit comment il peut tirer profit du fait que seules cinq villes sont concernées. Le petit nombre de villes permet de dresser la liste de tous les trajets possibles
et de choisir ensuite le plus court. Avec cinq villes, il n’y a que 24 trajets à examiner
ou seulement 12 si l’on considère qu’un trajet et son inverse sont équivalents. C’est
autorisé car tous deux sont de même distance. Cette méthode est bien utile à James
Cook car il apprend que le trajet BAEDCB (ou son inverse BCDEAB) est en réalité la
solution optimale puisque la distance à parcourir est de 5 147 km seulement.
De retour à Bismarck, James se rend compte que son voyage lui a pris trop de temps.
Ce n’est pas la distance qu’il veut
réduire, mais le temps. Il trace
un nouveau tableau qui donne le
temps qui sépare les différentes
villes du secteur à parcourir.
James sait que la somme des distances des deux côtés d’un triangle
1831
1421
1136
1641
1263
380
948
933
2021
1770
A
E
C
D
B
Albuquerque
12 (route)
Bismarck
6 (avion)
2 (avion) Chicago
2 (avion)
4 (avion) 3 (avion)
Dallas
4 (route)
3 (avion) 5 (avion) 1 (avion) El Paso