Haben Sie ein traveling salesman-Algorithmus, um ein problem zu lösen?
https://stackoverflow.com/questions/264050
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich studierte TSP in der Hochschule im Kontext der NP-Vollständigkeit.Ich habe eigentlich nie eine situation gehabt, wo es auf anwenden, um ein praktisches problem.Ein wenig recherche zeigt, dass es hat verwendet worden, um die billigsten Weg zu bewegen, einen Bohrer um, das ist die Herstellung von Bohrungen in Leiterplatten.Das ist so ziemlich alles, was ich finden konnte.
Verwenden Sie es?Welche anderen praktischen Anwendungen hat die TSA haben?
Lösung
Wie bei anderen in diesem Thread ich eine Lösung für ein NP vollständiges Problem in der Schule gebaut (es war ein Nebenprojekt für einen Freund) - ein Planungsprogramm. Zu der Zeit, die ich vereinbart sein Problem zu arbeiten, wusste ich nicht, was NP vollständig war. Ich erkennen später hatte ich mit einiger ziemlich guten Heuristik zur Lösung des Problems kommen - aber natürlich der eigentliche Trick zu wissen, war, wenn der Benutzer zu sagen, dass es keine Lösung war und sie das Problem über gezwungen hatte.
Es war eine gute Möglichkeit, meine eventuellen theoretischen Klassen zusammen zu bringen und die reale Welt.
Auch hier Heuristiken und „nahe genug“ sind in der Regel gut für reale Welt verwendet, wo nahezu optimale Lösungen wegen der Kosten des Findens und die Umsetzung der ideale Lösung bevorzugt.
Andere Tipps
Ich war einst die Aufgabe schreiben Sie ein Programm, um füllen Sie eine rechteckige Fläche ziemlich gleichmäßig mit einem "kringel" - eine gebogene Linie, die sich nicht selbst überschneidet.Mein Erster Versuch war zu generieren zufällige Punkte innerhalb des Rechtecks, und versuchen zu finden eine tour von Ihnen (nicht unbedingt die absolute kürzeste).Leider ist dieser Ansatz einfach nicht funktioniert sehr gut, und ich habe es aufgegeben.
Ich löste das problem in die Ende, obwohl:
Meine erfolgreiche Methode, die nicht im Zusammenhang mit der TDL aber für die neugierigen, werde ich es zusammenfassen:
Beginnen Sie mit einer einzelnen Liniensegment.Jetzt loop:wenn eine Linie "zu lange", teilen Sie in zwei.Bewegen Sie jeden Punkt ein bisschen zufällig, aber Punkte machen sich gegenseitig abstoßen.Ende der Schleife, wenn die kleinen Fortschritte erzielt werden können.Es sind details, aber hoffentlich bekommen Sie die Idee.
Natürlich, so ergibt sich ein Winkel Weg (das wäre zumutbar gewesen wäre), aber es ist leicht zu biegen die Ecken in glatten Bögen.
Und ja, ich habe, halten Sie den code.
Ich habe persönlich nie benutzt, aber eine andere Anwendung außer Bohren Leiterplatten ist, wenn Sie auf eine Reihe von verschiedenen Orten gehen wollen, sagen Sauger zu verkaufen. Sie könnten eine Lösung des Problems verwenden, um den billigsten Weg, um zu entscheiden, überall genau einmal zu besuchen.
Zu wissen, wann ein Problem ist NP-schwer ist, brauchbare Lösungen auszuschließen beteiligt, dieses Problem zu lösen. Jedes Mal, wenn Sie sehen, TSP (oder jede andere NP-hard Problem) ihr hässliches Gesicht für Probleme der nicht-triviale Größe Sie wissen Sie gehen den falschen Weg. Nicht nur wissen Sie es, aber Sie wissen, Warum , und sicher Ihr Chef / Mitspieler / jemand sagen kann.
Dass gesagt wird http://en.wikipedia.org/wiki/CONCORDE zeigt, dass :
Concorde wurde Probleme angewandt der Genkartierung, [1] Proteinfunktion Vorhersage, [2] Fahrzeug-Routing, [3] Umwandlung von Bitmap-Bildern Dauerstrichzeichnungen, [4] Planen Schiffsbewegungen für seismische Umfragen, [5] und in das Studium der Skalierungseigenschaften der kombinatorischen Optimierungsprobleme. [6]
Ja, ich benutze es in Geocaching-Anwendung für die Routenplanung.
Es nutzt derzeit eine gerade Linie Abstand zwischen den Punkten sollte aber richtig (wenn ich um um es zu bekommen) verwenden Straßen, die Abstände zwischen den Punkten ber.
Die meisten der Zeit, die Sie nicht wollen, einen Algorithmus verwenden, der die NP-Complete / Hard Problem löst. Sie wollen einfach nur einen Algorithmus, der „gut genug“ ist. Diese werden in der Regel auf Basis von Heuristiken und vernünftige Annäherungen geben.
Ich hatte ein Problem, das eine Instanz unabhängiger-Sets (NP-Complete) war, aber ich fand einen Greedy-Algorithmus, der ziemlich gute Ergebnisse in der überwiegenden Mehrzahl der Fälle gab, und hatte eine effiziente Laufzeit.
Viele Arten von optimierten Anordnung, wie Fahrgemeinschaft pickup, UPS Paketzustellung, usw. überall dort, wo die Knoten Traversal Anforderungen können in einer Dimension von Aufwand ausgedrückt werden, wie zum Beispiel Zeit oder Entfernung.
TSP ist die Hallo Welt von NP vollständigen Probleme. Darin rein kanonische Form ist, wird er nicht mehr in der freien Natur finden oft ( Demos wie diese nicht im Lieferumfang enthalten ), aber eine große Teilmenge von NP vollständigen Problemen sind im Zusammenhang oder sogar anhand von TSP, wie zum Beispiel:
- Vehicle Routing (einschließlich Versorgungs-LKW-Routing)
- Airline / Flug Routing
- Zug Routing
- Skipiste Pflug Maschine Routing
Jeder von ihnen hat zusätzliche, domänenspezifische Einschränkungen, die sie schwieriger zu lösen machen. So TSP ist eine gute Einführung in NP vollständigen Probleme, ihre Natur zu verstehen.
Ein paar Probleme im wirklichen Leben passen die Sachen, die man in Mathematik Klasse lernen. Die Probleme werden vereinfacht und abstrahiert, so dass Sie die Mathematik sehen und nicht von Details ablenken lassen. Das beste Beispiel aus der Praxis von großer TSPs, wie Sie bereits erwähnt, geht es nicht um tatsächlich jede Handlungsreisende: es Scheduling-Maschinen beinhaltet, die Jobs haben mit sequenzabhängige Rüstzeiten . Dazu gehören Maschinen, bei denen ein Arm, ein Werkzeug um verschiedene Stellen bewegt, und auch einige Gemälde Anwendungen (rot-> orange-> gelb ist einfacher als rot-> gelb-> orange). Es gibt auch einige Anwendungen in Röntgenkristallographie wo Sie einige Beispiel eines Kristalls an mehreren verschiedenen Winkeln zu orientieren.
Diese Firma auf einem verbesserten TSP-Algorithmus basiert.
Sie leiten Kabel-TV Installateure und Mechanikern um NYC unter anderem Probleme.
Weil Menschen können in der Regel TSP Probleme auf Par oder besser als die meisten Algorithmen für Karten mit 20-60 Knoten lösen, ist es nicht sehr häufig ein Computer das Problem zu lösen zu haben. Wenn die Kosten hoch genug ist, kann der Computer der Durchführung der Berechnung die Kosten wert sein, eine 1-2% Verbesserung gegenüber einem Menschen erhalten haben. Wenn die Route nicht ändert, dann kann man rechtfertigen verbringen einige Zeit es zu optimieren. Dies ist üblich, in dem Entwurf integrierter Schaltungen.
Airline Reise-Websites verwenden, um eine spezielle Version des TSP Problem, wenn die Show Sie eine Liste der Fluggesellschaften und die Preise für jede Strecke. Der Unterschied ist, statt Distanz optimieren sie für Kosten, und sicherlich gibt es keine Anforderung jede Stadt einmal zu besuchen! Sagen Sie bitte von LGA nach LAX fliegen wollen. Es gibt etwa 1/2 Dutzende direkte Routen und eine unendliche Anzahl von anderen Routen. Es könnte darauf hindeuten, LGA-> ORD-> LAX oder LGA-> DWF-> LAX. Menschen, die manuell Preis Routen manchmal niedrigere Preise als die, die durch die Reise-Websites durchsucht finden. Normalerweise wollen die Menschen nicht mehr als zwei Verbindungen, aber es gibt keine Obergrenze für die Anzahl der Verbindungen für einen bestimmten Flug.
Ich habe es verwendet Routen für meine Reisen Salesman iPhone Game . Was interessant ist, die Menschen sind sehr gut auf den kürzesten Weg zu lösen, aber nicht auf die längste Strecke zu lösen. Die längsten und kürzesten Routen haben die gleiche Komplexität, aber die Leute scheinen trainiert der Lage sein kürzesten Wege zu finden, oft schneller und besser als das, was ein Computer tun kann.
Bei meinem ersten Job wir eine häusliche Pflege Planungsanwendung gebaut.
Wir lösten das TSP Problem mit einigem nicht-linearen Zeitdruck und mit einer zusätzlichen nicht-linearer Kostenfunktion.
Wir verwendeten eine nicht optimale Solver das Problem zu lösen.
Wäre es nicht Google Maps (und jede andere Karte based Routing Software) werden mit einer Art Verkäufer von Reisen Wegbeschreibungen zu lösen?
Ich habe TSP nicht so weit verwendet, wie ich weiß, aber ich habe auf einer Reihe von autonomen Robotern gearbeitet, um ein Labyrinth zu durchqueren. So frage ich mich, wenn TSP angewendet werden könnte Lösung Labyrinth.
