3. Le voyageur de commerce (solution)

Q1 :

Le bouteille de départ n’est pas importante puisqu’il s’agit de faire le tour. On peut donc démarrer de n’importe quelle bouteille, ce sera toujours le même tour.

../_images/tsp_tour.png

Le premier réflexe est de relier les bouteilles en allant d’une bouteille à l’autre en prenant la plus proche. Mais c’est un peu trop compter sur la chance et la méthode est un peu trop aléatoire. Une meilleure méthode est d’entourer les points à visiter par une corde :

../_images/tsp_fil_tour1.png

Puis on se rapproche le plus possible en tirant sur le fil :

../_images/tsp_fil_tour2.png

On obtient l”enveloppe convexe. Ensuite, pour chaque point à l’intérieur, on tire un peu plus le fil là où cela paraît le plus court de façon à inclure le point dans ce chemin :

../_images/tsp_fil_tour3.png

Ca ne change pas grand chose ici mais j’aurais dû commencer par le point en vert car c’était le plus proche du chemin initial. On fait pareil avec les autres points intérieurs :

../_images/tsp_fil_tour4.png

Comment écrire l’algorithme ?

  1. Constuire l’enveloppe convexe de l’ensemble des points. Ce sera le chemin initial.
  2. Pour chaque point à l’intérieur, considérer le point le plus proche d’un des segments.
  3. Ajouter ce point à ce segment.
  4. Retourner à l’étape 2.

Le problème est que construire l’enveloppe convexe d’un ensemble de points n’est pas aussi simple que ça en a l’air. Ce fera l’objet d’un algorithme séparée. C’est d’ailleurs pourquoi on regarde les d’autres algorithmes permettant de construire le chemin le plus court passant par toutes les villes. Pour le savoir, il vous suffit de lire ce qui suit.

3.1. Autres options à programmer

Q2 :

Regardons sur la figure suivante :

../_images/tsp_croix.png

Avec le chemin rouge qui se croise, on parcourt : Lyon, Paris, Strasbourg, Nantes. Avec le chemin bleu qui ne se croise pas, on parcourt : Lyon, Strasbourg, Paris, Nantes. Les points de départ et d’arrivée sont les mêmes. On a juste permuter Strasbourg et Paris.

Pourquoi c’est plus court de ne pas croiser ?

Le parcours rouge est de même longueur que : Lyon, C, Strasbourg, Paris, C, Nantes qui parcourt les villes dans le même ordre que le parcours bleu. Sauf que aller de Lyon à Strasbourg en passant C est plus long que d’y aller directement : c’est un détour. Donc, il suffit de ne pas passer par C. C’est plus court.

../_images/tsp_tour1.png

Q3 :

Quel est le chemin de plus court, le rouge ou le bleu ? Vaut-il mieux faire ABC ou BAC ?

../_images/tsp_croix2.png

La différence entre les deux parcours ? On a permuté les villes A et B. Peut-on faire pareil avec les points IJK ? La réponse est oui. Par extension, si on a déjà tracé un chemin qui passe par toutes les villes, on peut permuter deux villes consécutives et voir si cela raccourcit le chemin. Par exemple, on peut essayer de permuter n’importe quelle ville avec n’importe quelle autre. On peut imaginer à peu près n’importe quelle transformation à partir de là.

../_images/tsp_tour2.png ../_images/tsp_tour3.png

Le notebook Voyageur de commerce permet d’avoir un cadre dans lequel on peut essayer ses propres algorithmes.

3.2. Pour aller plus loin

On rappelle le problème…

On considère un problème un petit peu différent. Pour recevoir des amis, il faut faire les courses en ville et à pied. Il faut du pain (500 grammes), des pommes de terre (3 kg), du fromage (2 kg), du vin (2 kg) et de la viande (1 kg). Il faut donc aller à la boulangerie, chez le marchant de légumes, le fromager, le marchand de vin et le boucher. On suppose que ce sont les commerçants de votre ville. Dans quel sens faut-il faire les courses pour porter le moins possible ?

La solution complète attendra un peu. Mais en attendant voici deux indices sous forme de questions :

  1. Au début du chemin, combien de kilos porte celui qui fait les courses ? Et à la fin ?
  2. Comment comparer deux chemins ?

3.3. Liens