L’esprit humain est un assistant de planification de chemin. Souvenez-vous des jours de pré-verrouillage où nous avons tous fait plusieurs courses consécutives à travers la ville. Il y avait toujours une danse mentale derrière votre tête pour donner un sens à la façon dont vous aviez planifié la journée. Cela pourrait aller quelque chose comme «d’abord à la banque, puis pour déposer le nettoyage à sec. Puisque le bureau de poste est sur le chemin de l’épicerie, je vais passer et envoyer cette boîte qui est restée dans le coffre depuis une semaine.

Ce genre de gymnastique mentale ne vient pas naturellement aux machines – c’est en fait un problème célèbre en informatique connu sous le nom de problème du voyageur de commerce. Bien qu’il soit classé dans l’industrie comme un problème NP-difficile dans l’optimisation combinatoire, une définition plus succincte et compréhensible serait: étant donné une liste de destinations, quel est le meilleur itinéraire aller-retour qui visite chaque emplacement?

Cet été a apporté la nouvelle que le record de 44 ans pour résoudre le problème a été battu. Voyons pourquoi il s’agit d’un problème difficile et comment l’équipe de recherche de l’Université de Washington a adopté une approche différente pour accélérer le processus.

La science pour aller d’ici à là

Le problème du voyageur de commerce (ou TSP en abrégé) a été l’un des problèmes les plus étudiés en informatique. Il a été envisagé pour la première fois dans les années 1800 par les mathématiciens WR Hamilton et Thomas Kirkman. Malgré ce que vous pourriez penser, il a en fait des applications en dehors du système de navigation GPS sur votre smartphone. Ce qui peut être modélisé comme un TSP comprend tout, de la disposition des ASIC, les plans des itinéraires des bus scolaires, l’ordre des trous de forage pour les PCB, jusqu’au séquençage de l’ADN. La «distance» entre les points pourrait signifier la distance physique ou la similitude entre les gènes.

Dans les années 1930, Karl Menger, mathématicien d’origine autrichienne qui était professeur à Harvard et Rice à peu près au même moment, envisageait la solution de la force brute qui considère simplement toutes les voies possibles. Cette approche devient rapidement extrêmement difficile car seulement 15 emplacements différents donnent 1 307 674 368 000 itinéraires différents à calculer (soit 15 factorielles). Comme vous pouvez l’imaginer, la mise à l’échelle vers des centaines ou des milliers de destinations différentes devient rapidement impossible à calculer. Une soixantaine de destinations différentes donne à peu près le même nombre d’itinéraires possibles que le nombre de particules estimées dans l’univers. C’est ainsi qu’est né un défi informatique classique.

Il existe plusieurs versions différentes du TSP, telles que des contraintes métriques, euclidiennes, asymétriques et plus spécifiques au domaine, telles que l’ajout d’un coût pour parcourir différents itinéraires en plus des distances elles-mêmes. Cela conduit à une distinction entre le TSP générique et non générique.

Nos talents uniques

Curieusement, les humains sont en fait assez bons pour résoudre la version euclidienne du problème. Les humains peuvent arriver à une solution presque parfaite en un temps presque linéaire, même dans les cas avec plus de 120 destinations. La facilité avec laquelle nous pouvons accomplir cet exploit a fasciné plusieurs psychologues cognitifs et suscité des dizaines d’études et d’articles sur le sujet. En fait, cette même capacité a été démontrée chez les pigeons et les bactéries qui changent de forme.

L’hypothèse actuelle est que les humains ont plusieurs heuristiques ou raccourcis qui les rendent très bons pour satisfaire – un terme inventé par Herbert A. Simon qui signifie simplement arriver à une décision qui est «assez bonne». La plupart des ordinateurs calculent une réponse spécifique et vérifiable. Il est correct ou incorrect sans espace entre les deux. Il est beaucoup plus facile d’arriver à la solution de perfection que de définir ce qui est assez bon dans le contexte actuel.

Les solutions approximatives

Dans cette veine, les informaticiens au cours du dernier demi-siècle ont affiné et appliqué de nouvelles techniques et approximations que les ordinateurs peuvent utiliser pour deviner leur chemin vers une meilleure solution. Des techniques telles que la programmation dynamique ont permis d’obtenir le nombre d’itinéraires à calculer jusqu’à n22n soit 7 372 800 itinéraires possibles pour 15 destinations, loin de moins d’un billion. Les algorithmes de branche et de borne sont capables d’obtenir cela encore plus bas, mais jusqu’à présent, il n’a pas été prouvé qu’il existe un algorithme parfait qui évalue moins de 2n itinéraires.

La modélisation des colonies de fourmis, qui utilisent des pistes de phéromones pour construire un consensus sur le chemin le plus court, a été proposée dans cet article publié en 1997.

Ceci est encore largement déraisonnable pour des ensembles de données plus volumineux et il fallait donc trouver des solutions approximatives plutôt que parfaites. Les heuristiques telles que le voisin le plus proche, qui va simplement à la destination la plus proche qui n’a pas été visitée, la recherche aléatoire à l’aide de chaînes de Markov et même la simulation de colonies de fourmis sont toutes des solutions utilisées pour produire des solutions approximatives. Cependant, même les meilleurs de ces algorithmes ne peuvent garantir que leur solution sera au plus 50% plus longue que la solution parfaite.

Une amélioration fine de rasoir vaut plus que sa valeur nominale

Bien que nous ayons vu du matériel lancé sur le TSP dans les deux accélérateurs personnalisés ainsi que le grand nombre de cœurs travaillant sur le problème, aucun algorithme n’a été capable de briser ce nombre de 50%. Jusqu’au récent article de pré-impression publié par Anna Karlin, Nathan Klein et Shayan Gharan sur une nouvelle technique qui offre une légère amélioration pour la version métrique du TSP. L’amélioration rase juste 10-34 sur ce nombre de 50%. Cela peut ne pas sembler beaucoup et vous pouvez affirmer qu’il est si petit que cela n’a pas d’importance sur tous les ensembles de données sauf les plus grands.

Cependant, la clé est qu’il a été mathématiquement démontré qu’une amélioration était et est possible. Le record des 44 dernières années a été battu et les auteurs de l’article espèrent qu’il en inspirera d’autres. Une percée similaire s’est produite en 2011 lorsque le cas graphique du TSP a connu une légère amélioration. Ce petit raffinement a inspiré d’autres chercheurs qui ont développé des algorithmes repensés. Ce qui a commencé comme une simple augmentation a finalement conduit à briser la barrière de 50% jusqu’à 40% pour le cas graphique.

Ce qu’il faut retenir ici, c’est que les problèmes peuvent être résolus. Même les problèmes qui semblent avoir atteint une limite qui ne peuvent pas être résolus. C’est bien de constater que les problèmes vieux de 44 ans retiennent encore l’attention, entraînant avec eux l’état de l’art alors que de nouveaux yeux trouvent des approches inattendues.

LAISSER UN COMMENTAIRE

Rédigez votre commentaire !
Entrez votre nom ici