Intéressant

Algorithmes, optimisation et problème du voyageur de commerce

Algorithmes, optimisation et problème du voyageur de commerce

Il s'agit du cinquième article d'une série en sept parties sur les algorithmes et le calcul, qui explore comment nous utilisons des nombres binaires simples pour alimenter notre monde. Le premier article, Comment les algorithmes gèrent le monde dans lequel nous vivons, peut être trouvé ici.

Le travail essentiel d'un informaticien théorique est de trouver des algorithmes efficaces pour les problèmes et le plus difficile de ces problèmes n'est pas seulement académique; ils sont au cœur même de certains des scénarios du monde réel les plus difficiles qui se déroulent chaque jour. Le plus critique d'entre eux est le problème de l'optimisation: comment trouver le meilleur solution à un problème lorsque nous avons un nombre apparemment infini de solutions possibles?

CONNEXES: UN NOUVEL ALGORITHME PERMET AUX VOITURES AUTONOMES DE CHANGER DE VOIE PLUS COMME DES HUMAINS

Pour l'instant, le mieux que nous puissions faire est d'adopter une approche heuristique et de trouver unassez bien solution, mais nous créons un niveau incalculable d'inefficacités qui s'additionnent avec le temps et épuisent nos ressources limitées qui pourraient être mieux utilisées ailleurs. Nous appelons cela le problème du voyageur de commerce et ce n'est pas un euphémisme de dire que la solution à ce problème pourrait sauver notre économie de milliers de milliards de dollars.

Le problème du voyageur de commerce, la complexité exponentielle du temps et bien plus encore

Le problème des vendeurs itinérants est décrit comme suit: une entreprise exige que l'un de ses vendeurs itinérants visite chaque ville sur une liste de n villes, où les distances entre une ville et toutes les autres villes de la liste sont connues. Chaque ville ne peut être visitée qu'une seule fois et le vendeur termine dans la ville d'où il est parti. Quel est le chemin le plus court qu'il puisse emprunter pour y parvenir?

L'algorithme le plus efficace que nous connaissons pour ce problème fonctionne dans temps exponentiel, ce qui est assez brutal comme nous l'avons vu. Contrairement au cryptage RSA cependant, dans le cas du problème du voyageur de commerce, il n'y a pas d'arithmétique modulaire ou de transformation de la factorisation en recherche de période, comme le fait l'algorithme de Shor. Le problème du voyageur de commerce est un problème de décision, et nous ne connaissons aucun raccourci qui nous met sous complexité temporelle exponentielle.

Juste pour expliquer pourquoi c'est une situation horrible, utilisons un exemple très courant de la folie complexité temporelle exponentielle peut obtenir. Disons que vous pouvez plier un morceau de papier encore et encore autant de fois que vous le souhaitez et qui aura toujours autant de longueur que nécessaire pour faire le pli. En prenant une mesure de la largeur de la pile de "feuilles" dans le produit final où le papier plié se développe en longueur loin de nous, voici ce à quoi vous pouvez vous attendre:

* 0 plis: 1 / 250e de pouce d'épaisseur.
* 10 plis: ~ 2,05 pouces d'épaisseur.
* 25 plis: ~ 1 mile d'épaisseur.
* 43 plis: La surface de la lune.
* 52 plis: À l'intérieur du soleil.
* 57 plis: Dépasser Ultima Thule
* 67 plis: Prend 1,5 an de lumière pour voyager d'un bout à l'autre.
* 82 plis: Aussi large que la Voie lactée.
* 93 plis: À une distance de projection astronomique du trou noir supermassif au centre de Messier 87.
* 101 plis: Je ne sais pas ce qu'il y a parce que c'est au-delà de l'univers observable.

Et c'est avec le meilleur algorithme que nous avons en ce moment. Chacune de ces «feuilles» de cette pile est une route que le vendeur pourrait emprunter dont la longueur à la fin nous aurions besoin de vérifier et de mesurer par rapport à toutes les autres longueurs d'itinéraire et chaque pli équivaut à ajouter une ville supplémentaire à la liste des villes qu'il doit visiter. Si nous nous sommes trompés en essayant de résoudre le problème du voyageur de commerce en vérifiant toutes les solutions possibles pour trouver la meilleure, nous examinons complexité temporelle factorielle. En utilisant notre 128 bits numéro de notre exemple de chiffrement RSA, qui était de 2128, alors que 101 plis n'est que 2101, 35! souffle passé 2128 par au moins un facteur de 100. Cela ne fait qu'empirer avec chaque incrément supplémentaire dans votre entrée, et c'est ce qui rend le problème du voyageur de commerce si important et aussi si exaspérant.

Le problème des algorithmes d'optimisation

Nous ne savons pas comment trouver la bonne réponse au problème du voyageur de commerce car pour trouver la meilleure réponse, vous avez besoin d'un moyen d'exclure toutes les autres réponses et nous n'avons aucune idée de comment le faire sans vérifier toutes les possibilités ou garder un enregistrement de l'itinéraire le plus court trouvé jusqu'à présent et recommencer une fois que notre itinéraire actuel dépasse ce nombre. C'est le meilleur que nous ayons, et cela ne fait que réduire les choses complexité temporelle exponentielle, donc en tant que solution, ce n'est pas du tout une solution.

Le problème du voyageur de commerce est spécial pour de nombreuses raisons, mais le plus important est qu'il s'agit d'un problème d'optimisation et que des problèmes d'optimisation surgissent partout dans la vie de tous les jours. En ce qui concerne les tailles d'entrée, 101 n'est pas du tout très grande. Dans le monde réel, il y a autant de petites villes dans un seul État américain qui pourraient théoriquement faire partie de la zone de livraison d'un grand distributeur commercial. Déterminer le trajet le plus court entre tous les arrêts que leurs camions doivent faire quotidiennement à divers clients permettrait d'économiser une somme incalculable en main-d'œuvre et en carburant.

Si vous achetez des pièces d'outre-mer pour votre usine, quel itinéraire et quelle combinaison de méthodes de livraison vous coûtera le moins cher? Quelle configuration de plis protéiques est celle qui peut vaincre le cancer? Trouver un algorithme qui peut résoudre le problème du voyageur de commerce dans quelque chose proche de Temps polynomial changerait tout et le ferait du jour au lendemain.

Une partie du problème est cependant qu'en raison de la nature du problème lui-même, nous ne savons même pas si une solution Temps polynomial est mathématiquement possible. C'est à cause de la façon dont nous classons les problèmes et le problème du voyageur de commerce appartient à une classification très spéciale de ce système, qui pose l'un des plus grands défis en mathématiques et en informatique, avec des implications de grande portée pour le monde réel.

Le sixième article de notre série sur les algorithmes et le calcul, P contre. NP, NP-Complete et l'algorithme pour tout, peut être trouvé ici.


Voir la vidéo: Résolution du Problème du Voyageur de Commerce Temps Réel (Mai 2021).