50 clés pour comprendre les maths
184
chronologie
Vers 1810
Charles Babbage cite ce problème
qu’il juge intéressant.
1831
Le problème du voyageur
de commerce est traité de
façon non théorique.
1926
Boru ° vka introduit
l’algorithme glouton.
46
James a tracé un graphique des distances qui séparent les villes. Bismarck est par
exemple à 1 641 km de Dallas, comme l’indique la cellule grisée à l’intersection de
la colonne de Bismarck et de la ligne de Dallas.
La méthode gloutonne Pragmatique, James Cook fait un croquis de son secteur de vente qui ne fait pas apparaître les détails mais qui lui donne une représentation globale de la position des villes et de la distance qui les sépare.
L’un de ses trajets de prédilection part de Bismarck, passe
par Chicago, Albuquerque, Dallas et El Paso avant de
revenir à Bismarck. C’est le trajet BCADEB.
Mais il se rend compte maintenant
que ce trajet de 6 618 km au total a
un coût élevé en termes de distance
parcourue. Peut-il mieux faire ?
James a certes tracé un plan de son secteur de vente mais il n’a pas envie d’entrer
dans le détail : il veut simplement se rendre dans ces villes pour vendre son produit.
Il regarde une carte dans son bureau de Bismarck et constate que la ville la plus
proche est Chicago. C’est à 1 136 km de Bismarck, alors qu’Albuquerque se trouve
à 1 421 km, Dallas à 1 641, et El Paso à 1 770 km. Il se met en route pour Chicago
Albuquerque
1 421
Bismarck
1 831
1 136
Chicago
933
1 641
1 263
Dallas
380
1 770
2 031
948
El Paso
Le voyageur
de commerce
James Cook, qui travaille dans une agence de Bismarck (Dakota-du-Nord, ÉtatsUnis), est un excellent voyageur de commerce qui vend un nettoyant spécial
moquettes pour l’entreprise Electra. Le fait qu’il ait été désigné vendeur de
l’année trois fois de suite atteste de son savoir-faire. Son secteur de vente
comprend Albuquerque, Chicago, Dallas et El paso, et il se rend dans chacune
de ces villes une fois par mois lors d’un déplacement unique. Son problème est de
savoir comment effectuer ce déplacement tout en minimisant la distance totale
parcourue. C’est le problème classique du voyageur de commerce.
184
chronologie
Vers 1810
Charles Babbage cite ce problème
qu’il juge intéressant.
1831
Le problème du voyageur
de commerce est traité de
façon non théorique.
1926
Boru ° vka introduit
l’algorithme glouton.
46
James a tracé un graphique des distances qui séparent les villes. Bismarck est par
exemple à 1 641 km de Dallas, comme l’indique la cellule grisée à l’intersection de
la colonne de Bismarck et de la ligne de Dallas.
La méthode gloutonne Pragmatique, James Cook fait un croquis de son secteur de vente qui ne fait pas apparaître les détails mais qui lui donne une représentation globale de la position des villes et de la distance qui les sépare.
L’un de ses trajets de prédilection part de Bismarck, passe
par Chicago, Albuquerque, Dallas et El Paso avant de
revenir à Bismarck. C’est le trajet BCADEB.
Mais il se rend compte maintenant
que ce trajet de 6 618 km au total a
un coût élevé en termes de distance
parcourue. Peut-il mieux faire ?
James a certes tracé un plan de son secteur de vente mais il n’a pas envie d’entrer
dans le détail : il veut simplement se rendre dans ces villes pour vendre son produit.
Il regarde une carte dans son bureau de Bismarck et constate que la ville la plus
proche est Chicago. C’est à 1 136 km de Bismarck, alors qu’Albuquerque se trouve
à 1 421 km, Dallas à 1 641, et El Paso à 1 770 km. Il se met en route pour Chicago
Albuquerque
1 421
Bismarck
1 831
1 136
Chicago
933
1 641
1 263
Dallas
380
1 770
2 031
948
El Paso
Le voyageur
de commerce
James Cook, qui travaille dans une agence de Bismarck (Dakota-du-Nord, ÉtatsUnis), est un excellent voyageur de commerce qui vend un nettoyant spécial
moquettes pour l’entreprise Electra. Le fait qu’il ait été désigné vendeur de
l’année trois fois de suite atteste de son savoir-faire. Son secteur de vente
comprend Albuquerque, Chicago, Dallas et El paso, et il se rend dans chacune
de ces villes une fois par mois lors d’un déplacement unique. Son problème est de
savoir comment effectuer ce déplacement tout en minimisant la distance totale
parcourue. C’est le problème classique du voyageur de commerce.