Avez-vous utilisé un algorithme de voyageur de commerce pour résoudre un problème?
https://stackoverflow.com/questions/264050
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J’ai étudié le TSP au collège dans le contexte de l’exhaustivité des NP. Je n'ai jamais eu de situation où cela s'appliquerait à un problème pratique. Un peu de recherche montre qu’il a été utilisé pour choisir le chemin le moins coûteux pour déplacer une perceuse, c’est-à-dire percer des trous dans les cartes de circuits imprimés. C'est à peu près tout ce que j'ai pu trouver.
L'utilisez-vous? Quelles sont les autres applications pratiques de la TSA?
La solution
Comme avec d’autres dans ce fil, j’ai construit une solution à un problème complet de NP au collège (c’était un projet parallèle pour un ami) - un programme de planification. Au moment où j'ai accepté de travailler sur son problème, je ne savais pas ce que NP Complete était. J'ai par la suite réalisé que j'avais mis au point des heuristiques assez bonnes pour résoudre le problème - mais le vrai truc, bien sûr, était de savoir quand dire à l'utilisateur qu'il n'y avait pas de solution et qu'il avait trop contraint le problème.
Ce fut un excellent moyen de réunir mes éventuels cours théoriques et le monde réel.
Encore une fois, l'heuristique et "suffisamment proches" conviennent généralement aux utilisations du monde réel où les solutions quasi optimales sont préférées en raison du coût de la recherche et de la mise en œuvre de la solution idéale.
Autres conseils
On m'a déjà demandé d'écrire un programme pour remplir une zone rectangulaire de manière assez uniforme avec un "gribouillis". - une ligne courbe qui ne se croise pas d'elle-même. Ma première tentative a été de générer des points aléatoires dans le rectangle et d'essayer de les parcourir (pas nécessairement le plus court absolu). Malheureusement, cette approche n'a tout simplement pas très bien fonctionné et je l'ai abandonnée.
J'ai finalement résolu le problème:
Ma méthode réussie n'était pas liée au TSP mais pour les curieux, je vais la résumer:
Commencez avec un seul segment de ligne. Boucle maintenant: si une ligne est "trop ??longue", divisez-la en deux. Déplacez chaque point un peu au hasard, mais faites en sorte que les points se repoussent. Terminez la boucle lorsque peu de progrès peuvent être réalisés. Il y a des détails mais j'espère que vous avez l'idée.
Bien sûr, cela crée une trajectoire angulaire (ce qui aurait été acceptable) mais il est facile de transformer les coins en arcs lisses.
Et oui j'ai gardé le code.
Je ne l'ai jamais utilisé personnellement, mais une autre application, en plus de percer les circuits imprimés, est si vous souhaitez vous rendre à différents endroits, par exemple pour vendre des aspirateurs. Vous pouvez utiliser une solution au problème pour choisir le moyen le moins cher de visiter une seule fois partout.
Savoir quand un problème est NP-difficile est utile pour exclure les solutions impliquant la résolution de ce problème. Chaque fois que vous voyez TSP (ou tout autre problème NP-difficile) remonter la tête pour des problèmes de taille non triviale, vous savez que vous vous dirigez dans la mauvaise voie. Non seulement vous le savez, mais vous savez pourquoi et pouvez en parler en toute confiance à votre patron / à votre coéquipier / à n’importe qui.
Cela étant dit, http://fr.wikipedia.org/wiki/CONCORDE révèle que :
Concorde a été appliqué à des problèmes de la cartographie des gènes, [1] fonction de la protéine prévision, [2] itinéraire du véhicule, [3] conversion d'images bitmap en dessins au trait continu, [4] planification des mouvements de navires pour la sismique enquêtes [5] et dans l'étude des propriétés d'échelle de la combinatoire problèmes d'optimisation. [6]
Oui, je l’utilise dans l’application de géocachette pour la planification d’itinéraire.
Il utilise actuellement une distance en ligne droite entre les points, mais devrait correctement (lorsque je me rapproche) utiliser les routes pour calculer les distances entre les points.
La plupart du temps, vous ne souhaitez pas utiliser un algorithme permettant de résoudre le problème NP-Complete / Hard. Vous voulez juste un algorithme qui soit "assez bon". Celles-ci sont généralement basées sur des heuristiques et donnent des approximations raisonnables.
J'ai eu un problème qui était une instance de Independent-Set (NP-Complete), mais j'ai trouvé un algorithme glouton qui donnait d'assez bons résultats dans la grande majorité des cas et dont le temps d'exécution était efficace.
De nombreux types de commande optimisée, tels que l’enlèvement du covoiturage, la livraison de colis UPS, etc., chaque fois que les exigences de traversée de nœud peuvent être exprimées en une seule dimension, comme le temps ou la distance.
TSP est le bonjour monde des problèmes complets NP. Dans sa forme purement canonique, vous ne le trouverez pas souvent à l’état sauvage ( démos comme celle-ci non incluse ), mais un grand sous-ensemble de problèmes complets NP sont liés ou même basés sur TSP, tels que:
- Acheminement des véhicules (inclut l'acheminement des camions de ravitaillement)
- Acheminement des compagnies aériennes / vols
- Itinéraire du train
- Itinéraire de la machine de déneigement
Chacune d’entre elles a des contraintes supplémentaires propres à un domaine, ce qui les rend plus difficiles à résoudre. TSP est donc une bonne introduction aux problèmes complets des NP, pour comprendre leur nature.
Peu de problèmes dans la vie réelle correspondent à ce que vous apprenez en classe de mathématiques. Les problèmes sont simplifiés et résumés afin que vous puissiez voir les calculs et ne pas être distrait par les détails. Comme vous l'avez dit, le meilleur exemple concret de gros PST, ne concerne aucun vendeur itinérant: il implique la planification de machines qui ont des tâches à exécuter avec cristallographie à rayons X . où vous devez orienter un échantillon de cristal selon plusieurs angles.
Cette société était basée sur un algorithme amélioré de TSP.
Ils dirigent les installateurs et les réparateurs de télévision par câble autour de New York, entre autres problèmes.
Etant donné que les humains peuvent généralement résoudre les problèmes de TSP au pair ou mieux que la plupart des algorithmes pour les cartes de 20 à 60 nœuds, il n’est pas très courant d’avoir un ordinateur qui résout le problème. Lorsque le coût est suffisamment élevé, il peut être rentable d'effectuer le calcul si l'ordinateur obtient une amélioration de 1 à 2% par rapport à un humain. Si la route ne change pas, on peut alors justifier de passer du temps à l’optimiser. C’est courant dans la conception de circuits intégrés.
Les sites Web de voyages aériens utilisent une version spécialisée du problème TSP lorsqu’ils affichent une liste des compagnies aériennes et les prix de chaque route. La différence est au lieu de la distance, ils optimisent pour le coût, et il n'est certainement pas nécessaire de visiter chaque ville une fois! Disons que vous voulez voler de LGA à LAX. Il y a environ une demi-douzaine de routes directes et un nombre infini d'autres routes. Cela peut suggérer LGA-> ORD-> LAX ou LGA-> DWF-> LAX. Les humains, qui peuvent tarifier les itinéraires manuellement, peuvent parfois trouver des tarifs plus bas que ceux recherchés par les sites de voyage. En règle générale, les personnes ne veulent pas plus de deux connexions, mais il n'y a pas de limite supérieure au nombre de connexions pour un vol donné.
Je l'ai utilisé pour résoudre des itinéraires pour mon jeu iPhone voyageur de vendeur . Ce qui est intéressant, c’est que les gens savent très bien résoudre le chemin le plus court, mais pas le plus long. Les itinéraires les plus longs et les plus courts ont la même complexité, mais les gens semblent formés pour pouvoir trouver les itinéraires les plus courts, souvent plus rapides et meilleurs que ce qu’un ordinateur peut faire.
Lors de mon premier emploi, nous avons créé une application de planification des soins à domicile.
Nous avons résolu le problème TSP avec des contraintes de temps non linéaires et avec une fonction de coût non linéaire supplémentaire.
Nous avons utilisé un solveur non optimal pour résoudre le problème.
Google Maps (et tous les autres logiciels de routage basés sur la carte) n’aurait-il pas recours à une sorte de voyageur voyageur pour résoudre les problèmes d'itinéraire?
Je n’ai pas utilisé TSP pour autant que je sache, mais j’ai travaillé sur plusieurs robots autonomes pour traverser un labyrinthe. Je me demande donc si le TSP pourrait être appliqué à la résolution de labyrinthe.
