Mona Lisa en "TSP art". Cliquez dessus pour l'admirer dans mon applet Processing
Cette image me donne enfin l’occasion de consacrer un article marrant au célèbre mais barbant "problème du voyageur de commerce" . Si vous cliquez sur Mona Lisa, vous verrez qu’elle est produite par une seule ligne brisée zig-zaguant entre 100’000 points sans jamais s’entrecouper. De plus, la ligne n’a ni début ni fin, elle forme un cycle. Autrement dit, on peut dessiner la Joconde comme un cercle déformé, sans lever le crayon… Je viens de publier une petite applet en processing qui montre ça.
Le dessin a initialement été produit par Robert Bosch, un prof de maths allemand qui étudie l’"Opt Art", l’utilisation de techniques d’optimisation dans l’art. La méthode est assez simple :
- on prend une image en « niveaux de gris »
- on dispose un grand nombre N de points sur l’image, resserrés dans les zones sombres, plus espacés dans les zones claires. Craig S. Kaplan a eu l’idée d’utiliser l’algorithme « Voronoï Stippler » [2] qui fait ça de manière remarquable.
- Ensuite, il suffit de résoudre le problème du voyageur de commerce à N villes pour obtenir le circuit le plus court entre les N points, donc sans intersection.
Quand vous lisez « il suffit de.. » , il faut vous méfier. C’est souvent sous cette formule lapidaire qu’on cache l’os. En réalité, le problème du voyageur de commerce (« Travelling Salesman Problem » en anglais, TSP dans la suite) est un problème « NP-complet », un de ceux qui nécessite un nombre « non polynomial » d’opérations pour sa résolution, « non polynomial » étant un euphémisme. En l’occurence, il faut en principe mesurer la longueur des N ! (N factorielle…) cycles hamiltoniens possibles passant par les N points pour déterminer lequel est le plus court. Au delà de N=20, on oublie.
Mais le TSP a un intérêt certain pour beaucoup d’applications pratiques dans lesquelles N est bien plus grand, ce qui justifie la recherche d’algorithmes efficaces même s’ils ne fournissent pas la solution absolument optimale. Le site TSP de Georgia Tech est une mine d’exemples et d’infos sur les progrès de la résolution du TSP. On y trouve également Concorde, un solveur de TSP open source très performant basé sur la programmation linéaire. Il détient le record du plus gros TSP résolu, pour N=85’500 calculé en 135 années de CPU, mais résout des problèmes raisonnables en un temps qui l’est aussi. J’ai eu l’occasion de m’en servir pour optimiser le parcours d’une perceuse de circuits imprimés où N valait autour de 1000 : quelques minutes de calcul permettent d’économiser des secondes de travail par circuit. Il existe d’ailleurs un Concorde en ligne pour résoudre vos (pas trop gros) problèmes de TSP.
Pour revenir à la Joconde, elle fait l’objet d’un petit concours car il n’est pas sûr que le chemin affiché dans l’image soit le plus court possible entre les 100’000 points définis par R. Bosch. Ce chemin, calculé par Yuichi Nagata avec Concorde a une longueur de 5’757’191 unités, alors qu’on a pu déterminer que le chemin ne peut pas être plus court que 5’757’044 unités. Il est donc possible qu’il existe un chemin encore plus court de 0.0026% ! Tout ce qu’il vous faut pour le trouver, c’est le fichier mona-lisa100K.tsp, et touiller un peu le code de Concorde ou de son concurrent TSPLib. Ah, et un superordinateur peut être utile aussi. Si vous trouvez le chemin le plus court, vous gagnerez la somme mirobolante de $100 !
Références:
- Robert Bosch, « Opt Art« , Math Horizons, February 2006, pages 6–9.
- Adrian Secord, « Weighted Voronoi Stippling« , 2002, Proceedings of 2nd NPAR, Annecy, p 37-43