TSP #1

« TSP » vaut pour « Travelling Salesman Problem » (ou « Travelling Salesperson Problem » si on veut être « genderly » correct) qui peut se traduire en « problème du voyageur de commerce », et désigne le problème suivant : étant donné un certain nombre de points, quel est le plus court chemin qui relie tous ces points ?

« TSP » stands for « Travelling Salesman Problem » (or « Travelling Salesperson Problem » to be « genderly » correct) and refers to the following problem: given a set of points, what is the shortest route that links all those points?

Une condition supplémentaire est que le chemin revient à son point de départ : il s’agit d’un circuit, et donc d’un polygone. Une conséquence de la minimisation de la longueur du circuit est que ce polygone est non croisé : on peut en effet montrer que si deux segments se croisent, alors le polygone obtenu en « décroisant » est plus court (la somme de deux côtés opposés d’un quadrilatère est toujours inférieure à celle des diagonales).

A further condition is that the route must return to the starting point: it is a tour, or circuit, and as such a polygon. A consequence of the minimization of the length of the route is that the polygon is not self-intersecting (simple) : it can be demonstrated that if two segments intersects, the polygon obtained by suppressing this intersection is shorter (the sum of two opposed edges of a quadrilateral is always less than the sum of the diagonals).

Même si l’on n’insiste pas sur la condition de minimisation, résoudre ce problème est intéressant, ne serait-ce que pour obtenir un polygone non croisé à partir d’un ensemble de sommets.

Even without stressing on the condition of minimization, solving this problem is interesting in order to obtain a simple polygon from a given set of vertices.

J’ai été sensibilisée à ce problème et au côté esthétique de ses résultats par la conférence de Philip Galanter à GA 2004 intitulée « What is Emergence ?» (voir article ici). J’avais étudié ce problème à l’époque, mais je m’y suis remise récemment à l'occasion de discussions avec un ancien étudiant sur la génération de polygones dont l’aire doit respecter certaines contraintes, la première étape consistant de toutes façons à générer un polygone non croisé.

I was made sensitive to this problem and its aesthetic side by Philip Galanter’s lecture at GA 2004 : «What is Emergence ?» (see paper here). I had looked at the problem at that time, but I was reminded of it recently when discussing with a former student the generation of polygons the area of which must obey constraints, the first step consisting of generating a simple polygon anyway.

Le problème TSP, qui s’énonce très simplement, est plus compliqué qu’il n’y paraît, surtout si l’on veut optimiser le temps de résolution. L’algorithme que j’avais mis en œuvre se décrit ainsi : on commence par faire un circuit convexe qui circonscrit l’ensemble des points, puis on ajoute les points restants un à un en choisissant à chaque fois le point dont l’insertion entre deux points du circuit génère la plus petite augmentation de la longueur totale.

The TSP problem, though simple in its formulation, is more complicated than it seems, more over if one wants to optimize the solving time. The algorithm I had used consists in this : one begins with a convex circuit that circumscribes the set of points, then one adds the other points one by one by choosing the points that yields the least augmentation of the total length when inserted between two points of the circuit.

On peut même le mettre en œuvre manuellement : on plante des clous dans une planche ou une plaque de carton, on les entoure avec un élastique, puis on fait passer l’élastique par le clou qui nous semble l’allonger le moins, et on recommence jusqu’au dernier clou.

One can even do this «by hand» : hammer a few nails in a wood or cardboard plate, put a rubber band around them, then shift the rubber band around the nail that seems to elongate it the least, and do it again till the last nail.

La version calculée de ce processus inverse les difficultés : s’il est évident de mettre l’élastique autour des clous, calculer le circuit convexe circonscrit est plus laborieux. Je commence par trouver le point le plus à droite (par exemple) puis par une comparaison des angles que font les autres points avec celui-ci, je trouve le deuxième, etc.

The computed version of this process reverses the difficulties : while it is straightforward to put the rubber band around the nails, it is more laborious to calculate the convex circuit that circumscribes the set of points. I start with the point which is the farthest on the right (for instance) then I compare angles for the other points in order to find the second point, and so on.

Par contre, si choisir le clou qui génère la plus petite élongation de l’élastique est un peu hasardeuse, calculer et comparer la différence entre la somme des distances entre tel point et deux sommets successifs du circuit d’une part et la distance entre ces deux sommets d’autre part, est simple à mettre en œuvre.

On the contrary, while the choice of the nail that generates the least elongation of the rubber band is somewhat uncertain, the computation of the difference between the sum of the distances between one point and two successive vertices of the circuit, on one hand, and the distance between those two vertices, on the other, is very easy.

Je ne suis pas sûre que cet algorithme donne vraiment le plus court circuit, ni qu’il soit optimal en temps de calcul, mais son résultat me satisfait tout de même, en ce qu’il est bien un polygone non croisé joignant un ensemble donné de points.

I am not sure that this algorithm yields the shortest circuit, nor that it optimizes the computing time, but its result is satisfying enough anyway, as it is a simple polygon linking a given set of points.