Il n’y a pas si longtemps, une équipe de chercheurs des universités Stanford et McGill a battu un record de 35 ans en informatique par une marge presque imperceptible-quatre centièmes de trillionième de trillionième de trillionième de pour cent, pour être exact., L’avance-faite à cet enfant d’affiche pour les dilemmes informatiques difficiles à résoudre, le problème du « vendeur itinérant”-était trop minuscule pour avoir une signification pratique immédiate, mais elle a insufflé une nouvelle vie à la recherche de solutions approximatives améliorées.
*article original réimprimé avec la permission de Simons Science News, une division éditorialement indépendante de SimonsFoundation.org dont la mission est d’améliorer la compréhension du public de la science en couvrant les développements et les tendances de la recherche en mathématiques et en sciences computationnelles, physiques et de la vie.,* Le problème du vendeur itinérant demande: étant donné un ensemble de villes reliées par des autoroutes, Quel est l’itinéraire le plus court qui visite chaque ville et retourne au lieu de départ? La réponse a des applications pratiques à des processus tels que le perçage de trous dans des cartes de circuits imprimés, la planification de tâches sur un ordinateur et la commande de fonctionnalités d’un génome.
le problème du vendeur itinérant est facile à énoncer, et — en théorie du moins — il peut être facilement résolu en vérifiant chaque itinéraire aller-retour pour trouver le plus court., Le problème avec cette approche par force brute est que le nombre de villes augmente, le nombre d’allers-retours pour vérifier rapidement dépasse les capacités des ordinateurs les plus rapides. Avec 10 villes, il y a plus de 300 000 allers-retours différents__.__ Avec 15 villes, le nombre de ballons possibilités à plus de 87 milliards.,
algorithme de Christofides
Au début des ordinateurs, les mathématiciens espéraient que quelqu’un trouverait une bien meilleure approche des grands problèmes de vendeurs itinérants — un algorithme qui permettrait aux ordinateurs de les résoudre dans un délai raisonnable. Mais alors que les informaticiens ont fait des progrès avec des scénarios spécifiques-identifier l’itinéraire aller-retour le plus court pour__ une carte de 49 villes dans les années 1950, une carte de 2 392 villes dans les années 1980 et une carte de 85 900 villes en 2006-personne n’a conçu un algorithme capable de résoudre efficacement tous les problèmes, Selon un document historique publié en 1972, une telle solution pourrait même ne pas être possible. L’informaticien Richard Karp, de L’Université de Californie à Berkeley, __a montré que le problème du vendeur itinérant est « NP-dur », ce qui signifie qu’il n’a pas d’algorithme efficace (à moins qu’une conjecture célèbre appelée P=NP ne soit vraie — mais la majorité des informaticiens soupçonnent maintenant qu’elle est fausse).
Illustration: avec L’aimable autorisation de David Applegate, Robert Bixby, Vasek Chvatal et William Cook
Après la publication de L’article de Karp, de nombreux informaticiens ont cherché à créer un algorithme efficace pour trouver des solutions approximatives au problème du vendeur itinérant — des itinéraires aller-retour dont la longueur est proche de celle du meilleur itinéraire possible., Ici, ils ont eu plus de chance: en 1976, Nicos Christofides, professeur à L’Imperial College de Londres, a développé un algorithmequi produit des itinéraires garantis d’être au plus 50% plus longs que l’itinéraire le plus court.
lors de sa création, de nombreux informaticiens ont supposé que L’algorithme de Christofides, qui est assez simple pour enseigner aux étudiants de premier cycle en informatique en une heure, était un espace réservé qui finirait par céder la place à un algorithme plus sophistiqué capable de mieux approximer la vraie solution. Pourtant, pendant des décennies, cet algorithme n’a pas réussi à se matérialiser.,
« presque tous les étudiants diplômés en informatique théorique ont à un moment donné passé quelques semaines ou mois futiles à essayer d’améliorer L’algorithme de Christofides”, a déclaré Sanjeev Arora, informaticien à L’Université de Princeton.
enfin, en 2011, L’équipe Stanford-McGill a dépassé la garantie de 50% de Christofides pour certains types de problèmes de vendeurs itinérants, montrant que les solutions de son algorithme seraient au plus 49.9999999999999999999999999999999999999999999999999996 pour cent plus long que la vraie réponse.,
Une série d’algorithmes d’approximation améliorés ont depuis émergé, après que les informaticiens ont commencé à examiner le problème avec de nouveaux yeux. Bien que ces approximations ne s’appliquent qu’à certains types de problèmes de vendeurs itinérants, L’approche qu’elles incarnent est très prometteuse, a déclaré Michel Goemans, informaticien au Massachusetts Institute of Technology.
” Nous avons à peine rayé la surface », a-t-il déclaré. « Je suis un grand croyant que, peut-être cinq ans plus tard, il y aura un résultat beaucoup plus puissant., »
L’arbre le plus court
L’algorithme de Christofides commence par rechercher non pas l’itinéraire aller-retour le plus court, mais le” spanning tree » le plus court — un ensemble de branches reliant les villes, sans boucles fermées. Contrairement à l’itinéraire aller-retour le plus court, le spanning tree le plus court est facile à construire efficacement: commencez par trouver l’autoroute la plus courte reliant deux villes; c’est la première branche. Pour ajouter la branche suivante, trouvez l’autoroute la plus courte reliant une nouvelle ville à l’une de ces deux — et ainsi de suite jusqu’à ce que toutes les villes aient été atteintes.,
l’arbre résultant n’est pas une solution possible au problème du vendeur itinérant car il ne crée pas d’itinéraire aller-retour. Mais il peut être converti en un aller-retour en visualisant les branches comme des murs, puis en imaginant marcher le long de l’arbre, avec votre doigt touchant le mur, jusqu’à ce que vous reveniez à l’endroit où vous avez commencé. Le voyage qui en résulte visite chaque ville et revient au point de départ, mais il est généralement loin d’être le chemin le plus court pour le faire, car il implique généralement de retracer les étapes plusieurs fois — chaque mur de l’arbre est traversé deux fois, une fois de chaque côté.,
cependant, cet itinéraire aller-retour est, au pire, deux fois plus long que la meilleure solution au problème du vendeur itinérant. En ajoutant des autoroutes soigneusement choisies à cet arbre et en prenant des raccourcis intelligents, Christofides a montré comment réduire cet aller-retour à un itinéraire au plus 50% plus long que le plus court.
Le spanning tree le plus court était un point de départ naturel pour les efforts visant à construire un court circuit aller-retour., Mais cette approche a également offert une ouverture pour les chercheurs qui tentent de réduire la garantie de 50% de Christofides. Car bien que l’arbre couvrant le plus court semble efficace au début, d’autres arbres peuvent être meilleurs en ce qui concerne le processus de coupe courte qui convertit l’arbre en un aller-retour-par exemple, un arbre qui ne se branche jamais n’a besoin que d’une seule autoroute ajoutée pour devenir un aller — retour.
L’objectif était donc de trouver un arbre couvrant qui trouve l’équilibre parfait entre la longueur et la conversion facile en un aller-retour., Aucun algorithme efficace ne peut découvrir cet arbre parfait (à moins que P=NP), mais un algorithme d’approximation réussi n’a besoin que d’en trouver un assez bon.
(Illustration: Robert Bosch)
un voyage fractionnaire
le chemin vers ce « très bon” arbre couvrant a impliqué la technique largement utilisée mais contre-intuitive de permettre solutions fractionnaires à certains types de problèmes. Un aller-retour fractionné, par exemple, pourrait impliquer d’aller sur la moitié de L’autoroute de Minneapolis à Detroit et la moitié de L’autoroute de Cleveland à Detroit. Une telle voie est, bien sûr, un non-sens d’un point de vue pratique., Mais il peut être formulé en termes mathématiques précis, et, contrairement au problème standard du vendeur itinérant, cette version fractionnée peut être résolue efficacement.
de nombreux problèmes d’approximation en informatique peuvent être résolus en calculant la solution à la version fractionnaire du problème, puis en trouvant un moyen intelligent d’arrondir les fractions pour produire une solution approximative au problème d’origine. Mais jusqu’à récemment, personne n’avait trouvé un bon moyen de le faire pour le problème du vendeur itinérant.,
en 2009, Amin Saberi de L’Université de Stanford et Arash Asadpour, alors étudiant diplômé, ont développé une technique d’arrondi général qui utilise le hasard pour essayer de choisir une solution en nombre entier qui conserve autant de propriétés de la solution fractionnaire que possible. Saberi a vu cette nouvelle technique d’arrondi comme « un marteau fort à la recherche d’un clou. »Le bon clou, soupçonnait-il, pourrait être le problème du vendeur itinérant.,
quelques mois plus tard, Saberi, Asadpour, Goemans, Shayan Gharan, étudiant diplômé de Stanford, et Aleksander Madry, aujourd’hui de L’École Polytechnique Fédérale de Lausanne en Suisse, ont montré que la nouvelle technique d’arrondi pouvait produire un bon algorithme d’approximation pour une variation du problème du affaire. L’année suivante, Saberi, Gharan et Mohit Singh de L’Université McGill ont utilisé la même approche pour développer un nouvel algorithme d’approximation pour le problème du vendeur itinérant ordinaire.,
étant donné une carte des villes et des autoroutes, le nouvel algorithme commence par calculer la solution fractionnaire exacte au problème du vendeur itinérant. Ensuite, il complète Cette solution fractionnaire en un arbre couvrant qui, espérons-le, sera proche de l’équilibre recherché entre la longueur et la conversion facile en un aller-retour. Enfin, l’algorithme branche cet arbre couvrant — plutôt que l’arbre couvrant le plus court-dans le cadre de Christofides.
le nouvel algorithme était « une idée que nous pourrions décrire en une heure ou deux, mais prouver qu’il fonctionnait réellement a pris plus d’un an”, a déclaré Saberi.,
Après une longue analyse, L’équipe Stanford-McGill a finalement réussi à battre L’algorithme de Christofides par une marge infime pour les problèmes de vendeurs itinérants « Graphiques”, une large sous-classe. En quelques mois, d’autres groupes, stimulés par le succès de L’équipe Stanford-McGill, ont utilisé d’autres techniques d’arrondi pour produire des algorithmes pour le cas graphique avec de meilleures approximations; le record actuel s’élève à 40%, une amélioration substantielle par rapport aux 50% de Christofides.,
le cas graphique « encapsule beaucoup des mêmes difficultés que vous rencontrez dans le problème général”, a déclaré Arora, ajoutant que les mêmes techniques qui fonctionnent pour le cas graphique pourraient bien être appliquées au problème général du vendeur itinérant.
néanmoins, a déclaré Saberi, résoudre le problème d’approximation du vendeur itinérant dans toute sa généralité nécessitera probablement une infusion de nouvelles idées.,
« la découverte mathématique est comme sentir votre chemin dans une pièce sombre: mettre votre main ici et trouver une chaise, mettre votre main là et trouver une table”, a-t-il dit, paraphrasant le mathématicien Andrew Wiles. « À un moment donné, votre main frappe l’interrupteur et tout à coup, tout a un sens. Pour le problème du vendeur itinérant, même après tant de papiers qui ont poussé l’enveloppe dans tant de directions, Je ne pense pas que nous ayons encore frappé ce commutateur. »
histoire originale réimprimée avec la permission de Simons Science News, une division éditorialement indépendante de SimonsFoundation.,org dont la mission est d’améliorer la compréhension du public de la science en couvrant les développements et les tendances de la recherche en mathématiques et en sciences computationnelles, physiques et de la vie.