Das Handlungsreisender-Problem (TSP) ist ein NP-hard Problem in der kombinatorischen Optimierung, die in der Operationsforschung und theoretischen Informatik studiert ist. In Anbetracht einer Liste von Städten und ihren pairwise Entfernungen ist die Aufgabe, den kürzestmöglichen Weg zu finden, der jede Stadt genau einmal besucht und zur Ursprung-Stadt zurückkehrt. Es ist ein spezieller Fall des Reisen-Käufer-Problems.

Das Problem wurde zuerst als ein mathematisches Problem 1930 formuliert und ist eines der am intensivsten studierten Probleme in der Optimierung. Es wird als ein Abrisspunkt für viele Optimierungsmethoden verwendet. Wenn auch das Problem rechenbetont schwierig ist, ist eine Vielzahl der Heuristik und genauen Methoden bekannt, so dass einige Beispiele mit Zehntausenden von Städten gelöst werden können.

Der TSP hat mehrere Anwendungen sogar in seiner reinsten Formulierung, wie Planung, Logistik und die Fertigung von Mikrochips. Ein bisschen modifiziert erscheint es als ein Teilproblem in vielen Gebieten, wie DNA sequencing. In diesen Anwendungen vertritt die Konzeptstadt, zum Beispiel, Kunden, Lötstellen oder DNA-Bruchstücke, und die Konzeptentfernung vertritt Reisen-Zeiten oder Kosten oder ein Ähnlichkeitsmaß zwischen DNA-Bruchstücken. In vielen Anwendungen machen zusätzliche Einschränkungen wie beschränkte Mittel oder Zeitfenster das Problem beträchtlich härter.

In der Theorie der rechenbetonten Kompliziertheit gehört die Entscheidungsversion des TSP (wo, in Anbetracht einer Länge L, die Aufgabe ist zu entscheiden, ob eine Tour kürzer ist als L) der Klasse von NP-complete Problemen. So ist es wahrscheinlich, dass die Grenzfall-Laufzeit für jeden Algorithmus für den TSP exponential mit der Zahl von Städten zunimmt.

Geschichte

Die Ursprünge des Handlungsreisender-Problems sind unklar. Ein Handbuch für Handlungsreisender von 1832 erwähnt das Problem und schließt Beispiel-Touren durch Deutschland und die Schweiz ein, aber enthält keine mathematische Behandlung.

Das Handlungsreisender-Problem wurde in den 1800er Jahren vom irischen Mathematiker W. R. Hamilton und vom britischen Mathematiker Thomas Kirkman definiert. Das Icosian Spiel von Hamilton war ein auf der Entdeckung eines Zyklus von Hamiltonian gestütztes Erholungsrätsel. Die allgemeine Form des TSP scheint, zuerst von Mathematikern während der 1930er Jahre in Wien und an Harvard namentlich von Karl Menger studiert worden zu sein, der das Problem definiert, den offensichtlichen Algorithmus der rohen Gewalt denkt, und den non-optimality des nächsten heuristischen Nachbars beobachtet:

Hassler Whitney an der Universität von Princeton hat das Namenhandlungsreisender-Problem bald danach eingeführt.

In den 1950er Jahren und 1960er Jahren ist das Problem immer populärer in wissenschaftlichen Kreisen in Europa und den USA geworden. Bemerkenswerte Beiträge wurden von George Dantzig, Delbert Ray Fulkerson und Selmer M. Johnson an RAND Corporation in Santa Monica geleistet, der das Problem als eine ganze Zahl geradliniges Programm ausgedrückt hat und die Schneidflugzeug-Methode für seine Lösung entwickelt hat. Mit diesen neuen Methoden haben sie ein Beispiel mit 49 Städten zu optimality gelöst, indem sie eine Tour gebaut haben und bewiesen haben, dass keine andere Tour kürzer sein konnte. In den folgenden Jahrzehnten wurde das Problem von vielen Forschern von Mathematik, Informatik, Chemie, Physik und anderen Wissenschaften studiert.

Richard M. Karp hat 1972 gezeigt, dass das Zyklus-Problem von Hamiltonian NP-complete war, der die NP-Härte von TSP einbezieht. Das hat eine mathematische Erklärung für die offenbare rechenbetonte Schwierigkeit geliefert, optimale Touren zu finden.

Große Fortschritte wurden gegen Ende der 1970er Jahre und 1980 gemacht, als Grötschel, Padberg, Rinaldi und andere geschafft haben, Beispiele mit bis zu 2392 Städten, mit dem Ausschnitt von Flugzeugen und branch-bound genau zu lösen.

In den 1990er Jahren haben Applegate, Bixby, Chvátal und Koch das Programm Concorde entwickelt, der in vielen neuen Rekordlösungen verwendet worden ist. Gerhard Reinelt hat den TSPLIB 1991, eine Sammlung von Abrisspunkt-Beispielen der unterschiedlichen Schwierigkeit veröffentlicht, die von vielen Forschungsgruppen verwendet worden ist, um Ergebnisse zu vergleichen. 2005 haben Koch und andere eine optimale Tour durch ein durch ein Mikrochip-Lay-Out-Problem gegebenes 33,810-Städte-Beispiel geschätzt, zurzeit hat das größte TSPLIB Beispiel gelöst. Für viele andere Beispiele mit Millionen von Städten können Lösungen gefunden werden, dass versichert werden, innerhalb von 1 % einer optimalen Tour zu sein.

Beschreibung

Als ein Graph-Problem

TSP kann als ein ungeleiteter belasteter Graph, solch modelliert werden, dass Städte die Scheitelpunkte des Graphen sind, sind Pfade die Ränder des Graphen, und eine Entfernung eines Pfads ist die Länge des Randes. Es ist ein Minimierungsproblem-Starten und das Vollenden an einem angegebenen Scheitelpunkt, einander Scheitelpunkt genau einmal besucht. Häufig ist das Modell ein ganzer Graph (d. h. jedes Paar von Scheitelpunkten wird durch einen Rand verbunden). Wenn kein Pfad zwischen zwei Städten besteht, hinzufügend, dass ein willkürlich langer Rand den Graphen vollenden wird, ohne die optimale Tour zu betreffen.

Asymmetrisch und symmetrisch

Im symmetrischen TSP ist die Entfernung zwischen zwei Städten dasselbe in jeder entgegengesetzten Richtung, einen ungeleiteten Graphen bildend. Diese Symmetrie Hälften der Zahl von möglichen Lösungen. Im asymmetrischen TSP können Pfade nicht in beiden Richtungen bestehen, oder die Entfernungen könnten verschieden sein, einen geleiteten Graphen bildend. Verkehrskollisionen, Einbahnstraßen und Flugkosten für Städte mit verschiedenen Abfahrts- und Ankunftgebühren sind Beispiele dessen, wie diese Symmetrie zusammenbrechen konnte.

Zusammenhängende Probleme

• Eine gleichwertige Formulierung in Bezug auf die Graph-Theorie ist: In Anbetracht eines ganzen belasteten Graphen (wo die Scheitelpunkte die Städte vertreten würden, würden die Ränder die Straßen und die Gewichte vertreten, würde die Kosten oder Entfernung dieser Straße sein), finden Sie einen Zyklus von Hamiltonian mit kleinstem Gewicht.
• Die Voraussetzung des Zurückbringens in die Startstadt ändert die rechenbetonte Kompliziertheit des Problems nicht, sieht Pfad-Problem von Hamiltonian.
• Ein anderes zusammenhängendes Problem ist das Engpass-Handlungsreisender-Problem (Engpass TSP): Finden Sie einen Zyklus von Hamiltonian in einem belasteten Graphen mit dem minimalen Gewicht des gewichtigsten Randes. Das Problem ist von beträchtlicher praktischer Wichtigkeit, abgesondert vom offensichtlichen Transport und den Logistik-Gebieten. Ein klassisches Beispiel ist in der gedruckten Stromkreis-Herstellung: Terminplanung eines Wegs der Bohrmaschine-Maschine, Löcher in einem PCB zu bohren. In robotic maschinell herstellende oder Bohranwendungen sind die "Städte" Teile zur Maschine oder den Löchern (verschiedener Größen), um zu bohren, und die "Kosten des Reisens" schließen Zeit ein, für den Roboter (einzelner Maschinenjob sequencing Problem) neu auszurüsten.
• Das verallgemeinerte Handlungsreisender-Problem befasst sich mit "Staaten", die haben (ein oder mehr), müssen "Städte" und der Verkäufer genau eine "Stadt" von jedem "Staat" besuchen. Auch bekannt als das "Reisen-Politiker-Problem". Auf eine Anwendung wird in der Einrichtung einer Lösung des Schneidaktienproblems gestoßen, um Messer-Änderungen zu minimieren. Ein anderer ist mit dem Bohren in der Halbleiter-Herstellung beschäftigt, sieh z.B. Überraschend haben Behzad und Modarres demonstriert, dass das verallgemeinerte Handlungsreisender-Problem in ein Standardhandlungsreisender-Problem mit derselben Zahl von Städten, aber eine modifizierte Entfernungsmatrix umgestaltet werden kann.
• Das folgende Einrichtungsproblem befasst sich mit dem Problem, eine Reihe von Städten zu besuchen, wo Prioritätsbeziehungen zwischen den Städten bestehen.
• Das Reisen-Käufer-Problem befasst sich mit einem Käufer, der wegen des Kaufens einer Reihe von Produkten angeklagt wird. Er kann diese Produkte in mehreren Städten kaufen, aber zu verschiedenen Preisen und nicht allen Städten bieten dieselben Produkte an. Das Ziel ist, einen Weg zwischen einer Teilmenge der Städte zu finden, die Gesamtkosten (Reisekosten + das Kaufen von Kosten) minimiert, und die den Kauf aller erforderlichen Produkte ermöglicht.

Computerwissenschaft einer Lösung

Die traditionellen Linien des Angriffs für die NP-hard Probleme sind der folgende:

• Das Planen von Algorithmen, um genaue Lösungen zu finden (werden sie vernünftig schnell nur für kleine Problem-Größen arbeiten).
• "Suboptimale" oder heuristische Algorithmen, d. h., Algorithmen ausdenkend, die entweder anscheinend oder wahrscheinlich gute Lösungen liefern, aber die, wie man beweisen konnte, nicht optimal waren.
• Die Entdeckung von speziellen Fällen für das Problem ("Teilprobleme"), für die entweder besser oder genaue Heuristik möglich sind.

Rechenbetonte Kompliziertheit

Wie man

gezeigt hat, ist das Problem NP-hard gewesen (genauer, es ist für die Kompliziertheitsklasse FP abgeschlossen; sieh, dass Funktionsproblem), und die Entscheidungsproblem-Version ("gegeben die Kosten und eine Nummer x, entscheiden, ob es einen Rückfahrweg gibt, der preiswerter ist als x"), ist NP-complete. Das Engpass-Handlungsreisender-Problem ist auch NP-hard. Das Problem bleibt NP-hard sogar für den Fall, wenn die Städte im Flugzeug mit Euklidischen Entfernungen, sowie in mehreren anderen einschränkenden Fällen sind. Das Entfernen der Bedingung, jede Stadt "nur einmal" zu besuchen, entfernt die NP-Härte nicht, da es leicht gesehen wird, dass im planaren Fall es eine optimale Tour gibt, die jede Stadt nur einmal besucht (sonst, durch die Dreieck-Ungleichheit würde eine Abkürzung, die einen wiederholten Besuch auslässt, die Tour-Länge nicht vergrößern).

Kompliziertheit der Annäherung

Im allgemeinen Fall, eine kürzeste Handlungsreisender-Tour findend, ist NPO-abgeschlossen. Wenn das Entfernungsmaß ein metrischer und symmetrisches ist, wird das Problem APX-abgeschlossen, und der Algorithmus von Christofides kommt ihm innerhalb 1.5 näher.

Wenn die Entfernungen auf 1 und 2 eingeschränkt werden (aber sind noch ein metrischer), wird das Annäherungsverhältnis 7/6. Im asymmetrischen, metrischen Fall sind nur logarithmische Leistungsgarantien bekannt, der beste aktuelle Algorithmus erreicht Leistungsverhältnis 0.814 Klotz n; es ist eine geöffnete Frage, wenn eine unveränderliche Faktor-Annäherung besteht.

Das entsprechende Maximierungsproblem, die längste Handlungsreisender-Tour zu finden, ist approximable innerhalb von 63/38. Wenn die Entfernungsfunktion symmetrisch ist, kann der längsten Tour innerhalb von 4/3 durch einen deterministischen Algorithmus und innerhalb durch einen randomised Algorithmus näher gekommen werden.

Genaue Algorithmen

Die direkteste Lösung würde sein, alle Versetzungen (bestellte Kombinationen) zu versuchen und zu sehen, welcher (das Verwenden der Suche der rohen Gewalt) am preiswertesten ist. Die Laufzeit für diese Annäherung liegt innerhalb eines polynomischen Faktors von O (n!), der factorial der Zahl von Städten, so wird diese Lösung unpraktisch sogar für nur 20 Städte. Eine der frühsten Anwendungen der dynamischen Programmierung ist der Gehaltene-Karp Algorithmus, der das Problem rechtzeitig O (n2) behebt.

Die dynamische Programmierlösung verlangt Exponentialraum. Mit dem Einschließungsausschluss kann das Problem rechtzeitig innerhalb eines polynomischen Faktors und polynomischen Raums behoben werden.

Besserung dieser Zeitgrenzen scheint, schwierig zu sein. Zum Beispiel ist es nicht bestimmt worden, ob ein genauer Algorithmus für TSP, der rechtzeitig läuft, besteht.

Andere Annäherungen schließen ein:

• Verschiedene branch-bound Algorithmen, die verwendet werden können, um TSPs zu bearbeiten, der 40-60 Städte enthält.
• Progressive Verbesserungsalgorithmen, die an die geradlinige Programmierung erinnernde Techniken verwenden. Arbeiten gut für bis zu 200 Städte.
• Durchführungen von branch-bound und mit dem Problem spezifische Kürzungsgeneration; das ist die Methode der Wahl, um große Beispiele zu lösen. Diese Annäherung meint, dass die aktuelle Aufzeichnung, ein Beispiel mit 85,900 Städten lösend, sieht.

Eine genaue Lösung für 15,112 deutsche Städte von TSPLIB wurde 2001 mit der schneidstufigen von George Dantzig vorgeschlagenen Methode gefunden, Ray Fulkerson und Selmer M. Johnson 1954, haben auf der geradlinigen Programmierung gestützt. Die Berechnung wurde in einem Netz von 110 an der Reisuniversität von Universität und Princeton gelegenen Verarbeitern durchgeführt (sieh den Princeton Außenverbindung). Die Gesamtberechnungszeit war zu 22.6 Jahren auf einzelnen 500 MHz Verarbeiter von Alpha gleichwertig. Im Mai 2004 wurde das Handlungsreisender-Problem, alle 24,978 Städte in Schweden zu besuchen, behoben: Eine Tour der Länge, die etwa 72,500 Kilometer gefunden wurden und wurde es bewiesen, dass keine kürzere Tour besteht.

Im März 2005 wurde das Handlungsreisender-Problem, alle 33,810 Punkte in einer Leiterplatte zu besuchen, mit Concorde TSP Solver behoben: Eine Tour der Länge, die 66,048,945 Einheiten gefunden wurden und wurde es bewiesen, dass keine kürzere Tour besteht. Die Berechnung hat etwa 15.7 Zentraleinheitsjahre genommen (Koch u. a. 2006). Im April 2006 wurde ein Beispiel mit 85,900 Punkten mit Concorde TSP Solver gelöst, 136 Zentraleinheitsjahre übernehmend, sieh.

Heuristisch und Annäherungsalgorithmen

Verschiedene Heuristik und Annäherungsalgorithmen, die schnell gute Lösungen nachgeben, sind ausgedacht worden. Moderne Methoden können Lösungen für äußerst große Probleme (Millionen von Städten) innerhalb einer angemessenen Frist finden, die mit einer hohen Wahrscheinlichkeit gerade 2-3 % weg von der optimalen Lösung sind.

Mehrere Kategorien der Heuristik werden anerkannt.

Konstruktive Heuristik

Der Algorithmus des nächsten Nachbars (NN) (oder so genannte gierige Algorithmus) lassen den Verkäufer die nächste verlassene Stadt als seine folgende Bewegung wählen. Dieser Algorithmus gibt schnell einen effektiv kurzen Weg nach. Für N auf einem Flugzeug zufällig verteilte Städte gibt der Algorithmus auf dem Durchschnitt einen Pfad nach, der um 25 % länger ist als der kürzestmögliche Pfad. Jedoch dort bestehen Sie vieler besonders eingeordneter Stadtvertrieb, der den NN Algorithmus den schlechtesten Weg (Gutin, Yeo und Zverovich, 2002) geben lässt. Das ist sowohl für asymmetrischen als auch für symmetrischen TSPs (Gutin und Yeo, 2007) wahr. Rosenkrantz u. a. [1977] hat gezeigt, dass der NN Algorithmus den Annäherungsfaktor für Beispiele hat, die die Dreieck-Ungleichheit befriedigen.

Auf einem minimalen Überspannen-Baum gestützte Aufbauten haben ein Annäherungsverhältnis 2. Der Christofides Algorithmus erreicht ein Verhältnis 1.5.

Die bitonic Tour von einer Reihe von Punkten ist das Eintönigkeitsvieleck des minimalen Umfangs, das die Punkte als seine Scheitelpunkte hat; es kann effizient durch die dynamische Programmierung geschätzt werden.

Ein anderer konstruktiv heuristisch, Match Zweimal und Stich (MTS) (Kahng, Reda 2004), führt zwei folgende matchings durch, wo das zweite Zusammenbringen nach dem Löschen aller Ränder des ersten Zusammenbringens durchgeführt wird, um eine Reihe von Zyklen nachzugeben. Die Zyklen werden dann genäht, um die Endtour zu erzeugen.

Wiederholende Verbesserung

Austausch von Pairwise oder Heuristik von Lin-Kernighan: Der Pairwise-Austausch oder 2 - wählt Technik ist mit wiederholend dem Entfernen von zwei Rändern und Ersetzen von diesen mit zwei verschiedenen Rändern verbunden, die die Bruchstücke wiederverbinden, die durch die Rand-Eliminierung in eine neue und kürzere Tour geschaffen sind. Das ist ein spezieller Fall der k-opt Methode. Bemerken Sie, dass das Etikett Lin-Kernighan ist eine häufig gehörte falsche Bezeichnung für 2 - wählt. Lin-Kernighan ist wirklich eine allgemeinere Methode.

heuristischer k-opt: Nehmen Sie eine gegebene Tour und löschen Sie k gegenseitig nehmen Ränder auseinander. Versammeln Sie die restlichen Bruchstücke in eine Tour wieder, keine zusammenhanglosen Subtouren verlassend (d. h. verbinden Sie Endpunkte eines Bruchstücks zusammen nicht). Das vereinfacht tatsächlich den TSP unter der Rücksicht in ein viel einfacheres Problem. Jeder Bruchstück-Endpunkt kann mit 2k &minus verbunden werden; 2 andere Möglichkeiten: 2k verfügbarer Gesamtbruchstück-Endpunkte werden die zwei Endpunkte des Bruchstücks unter der Rücksicht zurückgewiesen. Solch eine gezwungene 2k-Stadt TSP kann dann mit Methoden der rohen Gewalt gelöst werden, die am wenigsten gekostete Wiederkombination der ursprünglichen Bruchstücke zu finden. Die k-opt Technik ist ein spezieller Fall des V-opt, oder Variable - wählen Technik. Die populärsten von den k-opt Methoden sind 3 - wählen, und diese wurden von Shen Lin von Glockenlaboratorien 1965 eingeführt. Es gibt einen speziellen Fall 3 - wählen, wo die Ränder nicht zusammenhanglos sind (zwei der Ränder sind neben einander). In der Praxis ist es häufig möglich, wesentliche Verbesserung zu erreichen, mehr als 2 - wählen ohne die kombinatorischen Kosten der allgemeinen 3 - wählen durch das Einschränken der 3 Änderungen zu dieser speziellen Teilmenge, wo zwei der entfernten Ränder angrenzend sind. Das so genannte zwei und eine Hälfte wählen normalerweise Fälle grob auf halbem Wege zwischen 2 - wählt, und 3 - wählen, sowohl in Bezug auf die Qualität von Touren erreicht als auch in Bezug auf die Zeit, die erforderlich ist, jene Touren zu erreichen.

Heuristischer V-opt: Die Variable - wählt Methode ist mit, und eine Generalisation der k-opt Methode verbunden. Wohingegen die k-opt Methoden eine festgelegte Zahl (k) Ränder von der ursprünglichen Tour entfernen, die Variable - wählen Methoden befestigen die Größe des Rand-Satzes nicht, um umzuziehen. Stattdessen bauen sie den Satz an, als der Suchprozess weitergeht. Die am besten bekannte Methode in dieser Familie ist die Methode von Lin-Kernighan (erwähnt oben als eine falsche Bezeichnung für 2 - wählen). Shen Lin und Brian Kernighan haben zuerst ihre Methode 1972 veröffentlicht, und es war das zuverlässigste heuristische, um Handlungsreisender-Probleme seit fast zwei Jahrzehnten zu beheben. Fortgeschrittenere Variable - wählt Methoden wurden an Glockenlaboratorien gegen Ende der 1980er Jahre von David Johnson und seiner Forschungsmannschaft entwickelt. Diese Methoden (hat manchmal Lin-Kernighan-Johnson genannt), bauen auf die Methode von Lin-Kernighan, Ideen von der tabu Suche und Entwicklungscomputerwissenschaft hinzufügend. Die grundlegende Technik von Lin-Kernighan gibt Ergebnisse, die, wie man versichert, sind, wählen mindestens 3-. Die Methoden von Lin-Kernighan-Johnson schätzen eine Tour von Lin-Kernighan, und stören dann die Tour dadurch, was als eine Veränderung beschrieben worden ist, die mindestens vier Ränder und das Wiederanschließen der Tour auf eine verschiedene Weise, dann V-Entscheiden die neue Tour entfernt. Die Veränderung ist häufig genug, um die Tour vom lokalen von Lin-Kernighan identifizierten Minimum zu bewegen. V-opt Methoden werden als die stärkste Heuristik für das Problem weit betrachtet und sind im Stande, spezielle Fälle, wie das Zyklus-Problem von Hamilton und anderer nichtmetrischer TSPs zu richten, auf dem andere Heuristik scheitert. Viele Jahre lang hatte Lin-Kernighan-Johnson optimale Lösungen für den ganzen TSPs identifiziert, wo eine optimale Lösung bekannt war und die am besten bekannten Lösungen für ganzen anderen TSPs identifiziert hatte, auf dem die Methode versucht worden war.

Verbesserung von Randomised

Optimierte Kettenalgorithmen von Markov, die lokale forschende heuristische Subalgorithmen verwenden, können einen Weg äußerst in der Nähe vom optimalen Weg für 700 bis 800 Städte finden.

TSP ist ein Prüfstein für viele allgemeine Heuristik, die für die kombinatorische Optimierung wie genetische Algorithmen, das vorgetäuschte Ausglühen, die Tabu Suche, die Ameise-Kolonie-Optimierung, Flussbildungsdynamik ausgedacht ist (sieh Schwarm-Intelligenz), und die böse Wärmegewicht-Methode.

Ameise-Kolonie-Optimierung

Forscher der künstlichen Intelligenz Marco Dorigo beschrieben 1997 eine Methode, heuristisch "gute Lösungen" des TSP das Verwenden einer Simulation einer Ameise-Kolonie genannt ACS (Ameise-Kolonie-System) zu erzeugen. Es modelliert in echten Ameisen beobachtetes Verhalten zu finden, dass kurze Pfade zwischen Nahrungsmittelquellen und ihrem Nest, ein auftauchendes Verhalten, das sich aus der Vorliebe jeder Ameise ergibt Spur pheromones abgelegt von anderen Ameisen folgen.

ACS verbreitet eine Vielzahl von virtuellen Ameise-Agenten, um viele mögliche Wege auf der Karte zu erforschen. Jede Ameise probabilistically wählt die folgende Stadt, um gestützt auf einem heuristischen Kombinieren der Entfernung zur Stadt und dem Betrag von virtuellem pheromone zu besuchen, der am Rand zur Stadt abgelegt ist. Die Ameisen erforschen, sich pheromone an jedem Rand ablagernd, den sie durchqueren, bis sie alle eine Tour vollendet haben. An diesem Punkt legt die Ameise, die die kürzeste Tour vollendet hat, virtuellen pheromone entlang seinem ganzen Tour-Weg (globale Spur aktualisierend) ab. Der Betrag von abgelegtem pheromone ist zur Tour-Länge umgekehrt proportional: Je kürzer die Tour, desto mehr es sich ablagert.

Spezielle Fälle

Metrischer TSP

Im metrischen TSP, auch bekannt als Delta-TSP oder Δ-TSP befriedigen die Intercityentfernungen die Dreieck-Ungleichheit.

Eine sehr natürliche Beschränkung des TSP ist zu verlangen, dass die Entfernungen zwischen Städten einen metrischen bilden, d. h. sie befriedigen die Dreieck-Ungleichheit. Das kann als die Abwesenheit von "Abkürzungen" im Sinn verstanden werden, dass der Direktanschluss von bis B nie länger ist als der Weg über das Zwischenglied C:

:

Die Rand-Längen bilden dann einen metrischen auf dem Satz von Scheitelpunkten. Wenn die Städte als Punkte im Flugzeug angesehen werden, sind viele natürliche Entfernungsfunktionen Metrik, und so viele natürliche Beispiele von TSP befriedigen diese Einschränkung.

Der folgende ist einige Beispiele von metrischem TSPs für die verschiedene Metrik.

• Im Euklidischen TSP (sieh unten) ist die Entfernung zwischen zwei Städten die Euklidische Entfernung zwischen den entsprechenden Punkten.
• Im geradlinigen TSP ist die Entfernung zwischen zwei Städten die Summe der Unterschiede ihres x- und Y-Koordinaten. Das metrisch wird häufig die Entfernung von Manhattan oder den metrischen Stadtblock genannt.
• Im metrischen Maximum ist die Entfernung zwischen zwei Punkten das Maximum der absoluten Werte von Unterschieden ihres x- und Y-Koordinaten.

Die letzte zwei Metrik erscheint zum Beispiel in der Routenplanung eine Maschine, die einen gegebenen Satz von Löchern in einer gedruckten Leiterplatte bohrt. Metrisches Manhattan entspricht zu einer Maschine, die zuerst eine Koordinate, und dann den anderen anpasst, so ist die Zeit, um sich zu einem neuen Punkt zu bewegen, die Summe von beiden Bewegungen. Das metrische Maximum entspricht zu einer Maschine, die beide Koordinaten gleichzeitig anpasst, so ist die Zeit, um sich zu einem neuen Punkt zu bewegen, langsamer der zwei Bewegungen.

In seiner Definition erlaubt der TSP Städten nicht, zweimal besucht zu werden, aber viele Anwendungen brauchen diese Einschränkung nicht. In solchen Fällen kann ein symmetrisches, nichtmetrisches Beispiel auf ein metrisches reduziert werden. Das ersetzt den ursprünglichen Graphen durch einen ganzen Graphen, in dem die Intercityentfernung durch den kürzesten Pfad zwischen und im ursprünglichen Graphen ersetzt wird.

Es gibt einen Annäherungsalgorithmus des unveränderlichen Faktors für das metrische TSP erwartete zu Christofides, der immer eine Tour der Länge höchstens 1.5mal die kürzeste Tour findet. In den folgenden Paragrafen erklären wir einen schwächeren (aber einfacher) Algorithmus, der eine Tour der Länge höchstens zweimal die kürzeste Tour findet.

Die Länge des minimalen Überspannen-Baums des Netzes ist ein für die Länge des optimalen Wegs tiefer gebundener natürlicher. Im TSP mit dem Dreieck-Ungleichheitsfall ist es möglich, obere Grenzen in Bezug auf den minimalen Überspannen-Baum zu beweisen und einen Algorithmus zu entwerfen, der einen nachweisbaren oberen hat, hat zur Länge des Wegs gebunden. Das erste veröffentlicht (und das einfachste) Beispiel folgt:

1. Bauen Sie den minimalen Überspannen-Baum.
2. Kopieren Sie alle seine Ränder. D. h. wo auch immer es einen Rand von u bis v gibt, fügen Sie einen zweiten Rand von v bis u hinzu. Das gibt uns einen Graphen von Eulerian.
3. Finden Sie einen Zyklus von Eulerian darin. Klar ist seine Länge zweimal die Länge des Baums.
4. Wandeln Sie den Zyklus von Eulerian in Hamiltonian ein folgendermaßen um: Gehen Sie entlang dem Zyklus von Eulerian, und jedes Mal spazieren, wenn Sie vorhaben, in einen bereits besuchten Scheitelpunkt einzutreten, ihn auszulassen und zu versuchen, zum folgenden (entlang dem Zyklus von Eulerian) zu gehen.

Es ist leicht zu beweisen, dass der letzte Schritt arbeitet. Außerdem, dank der Dreieck-Ungleichheit, ist jeder, am Schritt 4 hüpfend, tatsächlich eine Abkürzung; d. h. die Länge des Zyklus nimmt nicht zu. Folglich gibt es uns eine nicht mehr als zweimal so lange TSP-Tour wie die optimale.

Der Christofides Algorithmus folgt einem ähnlichen Umriss, aber verbindet den minimalen Überspannen-Baum mit einer Lösung eines anderen Problems, minimales Gewicht das vollkommene Zusammenbringen. Das gibt eine TSP-Tour, die höchstens 1.5mal das optimale ist. Der Christofides Algorithmus war einer der ersten Annäherungsalgorithmen, und war teilweise dafür verantwortlich, Aufmerksamkeit auf Annäherungsalgorithmen als eine praktische Annäherung an unnachgiebige Probleme zu lenken. Eigentlich wurde der Begriff "Algorithmus" zu Annäherungsalgorithmen bis später nicht allgemein erweitert; der Algorithmus von Christofides ist am Anfang heuristischen Christofides genannt geworden.

Im speziellen Fall, dass Entfernungen zwischen Städten alle entweder ein oder zwei sind (und so ist die Dreieck-Ungleichheit notwendigerweise zufrieden), gibt es einen polynomisch-maligen Annäherungsalgorithmus, der eine Tour der Länge an die meisten 8/7 Male der optimalen Tour-Länge findet. Jedoch ist es ein langjähriger (seit 1975) offenes Problem, den Annäherungsfaktor von Christofides 1.5 für allgemeinen metrischen TSP zu einer kleineren Konstante zu verbessern. Es ist bekannt, dass, wenn P = NP, es keinen polynomisch-maligen Algorithmus nicht gibt, der eine Tour der Länge am grössten Teil von 220/219=1.00456 … Zeiten die Länge der optimalen Tour findet. Im Fall von der begrenzten Metrik ist es bekannt, dass es keinen polynomischen Zeitalgorithmus gibt, der eine Tour der Länge an die meisten 321/320 Male der Länge der optimalen Tour, wenn P = NP baut.

Euklidischer TSP

Der Euklidische TSP oder planarer TSP, ist der TSP mit der Entfernung, die die gewöhnliche Euklidische Entfernung ist.

Der Euklidische TSP ist ein besonderer Fall des metrischen TSP, da Entfernungen in einem Flugzeug der Dreieck-Ungleichheit folgen.

Wie der allgemeine TSP sind der Euklidische TSP (und deshalb der allgemeine metrische TSP) NP-complete. Jedoch in etwas Hinsicht scheint es, leichter zu sein, als der allgemeine metrische TSP. Zum Beispiel ist der minimale Überspannen-Baum des mit einem Beispiel des Euklidischen TSP vereinigten Graphen ein Euklidischer minimaler Überspannen-Baum, und kann so in erwartetem O geschätzt werden (n loggen n) die Zeit für N-Punkte (beträchtlich weniger als die Zahl von Rändern). Das ermöglicht dem einfachen 2-Annäherungen-Algorithmus für TSP mit der Dreieck-Ungleichheit oben, schneller zu funktionieren.

Im Allgemeinen, für jeden c> 0, wo d die Zahl von Dimensionen im Euklidischen Raum ist, gibt es einen polynomisch-maligen Algorithmus, der eine Tour der Länge höchstens (1 + 1/c) Zeiten das optimale für geometrische Beispiele von TSP rechtzeitig findet; das wird ein polynomisch-maliges Annäherungsschema (PTAS) genannt. Sanjeev Arora und Joseph S. B. Mitchell wurden dem Gödel Preis 2010 für ihre gleichzeitige Entdeckung eines PTAS für den Euklidischen TSP zuerkannt.

In der Praxis, Heuristik mit schwächeren Garantien setzen fort, verwendet zu werden.

Asymmetrischer TSP

In den meisten Fällen ist die Entfernung zwischen zwei Knoten im TSP Netz dasselbe in beiden Richtungen. Der Fall, wo die Entfernung von bis B der Entfernung von B bis A nicht gleich ist, wird asymmetrischen TSP genannt. Eine praktische Anwendung eines asymmetrischen TSP ist Weg-Optimierung mit der Straßenniveau-Routenplanung (der asymmetrisch durch Einbahnstraßen, Autobahnauffahrten, Autobahn, usw. gemacht wird).

Das Lösen durch die Konvertierung zu symmetrischem TSP

Das Lösen eines asymmetrischen TSP Graphen kann etwas kompliziert sein. Der folgende ist 3×3 Matrix, die alle möglichen Pfad-Gewichte zwischen den Knoten A, B und C enthält. Eine Auswahl ist, eine asymmetrische Matrix der Größe N in eine symmetrische Matrix der Größe 2N zu drehen.

:

Um die Größe zu verdoppeln, wird jeder der Knoten im Graphen kopiert, einen zweiten Geisterknoten schaffend. Das Verwenden von Doppelpunkten mit sehr niedrigen Gewichten, wie , stellt einem preiswerten Weg "Verbindung" zurück mit dem echten Knoten und Erlauben symmetrische Einschätzung zur Verfügung weiterzugehen. Das Original 3×3 Matrix, die oben gezeigt ist, ist in unten links und das Gegenteil des Originals im Spitzenrecht sichtbar. Beide Kopien der Matrix haben ihre Diagonalen durch die preisgünstigen Sprung-Pfade ersetzen lassen, die durch  vertreten sind.

:

Das Original 3×3 würde Matrix zwei Zyklen von Hamiltonian erzeugen (ein Pfad, der jeden Knoten einmal besucht), zählt nämlich Ein B C [9], und Ein C B [zählen 12]. Wenn sie 6×6 bewertet, erzeugt die symmetrische Version desselben Problems jetzt viele Pfade, einschließlich A-A′-B-B′-C-C′-A, A-B′-C-A′-A, A-A′-B-C′-A [die ganze Kerbe 9 - ].

Das wichtige Ding über jede neue Folge besteht darin, dass es einen Wechsel zwischen dem verflixten geben wird (A′,B′,C′) und unverflixte Knoten (A, B, C) und dass die Verbindung, um zwischen jedem verwandten Paar (A-A&prime "zu springen";) ist effektiv frei. Eine Version des Algorithmus konnte jedes Gewicht für A-A&prime verwenden; Pfad so lange ist dieses Gewicht niedriger als ganze andere Pfad-Gewicht-Gegenwart im Graphen. Da das Pfad-Gewicht, um "zu springen", effektiv "frei" sein muss, konnte die Wertnull (0) verwendet werden, um diese Kosten zu vertreten —, wenn Null zu einem anderen Zweck bereits (wie Kennzeichnung ungültiger Pfade) nicht verwendet wird. In den zwei Beispielen oben werden nicht existierende Pfade zwischen Knoten als ein leeres Quadrat gezeigt.

Abrisspunkte

Um von TSP Algorithmen zu bewerten, ist TSPLIB eine Bibliothek von Beispielbeispielen des TSP, und verwandte Probleme wird aufrechterhalten, sieh den TSPLIB externen Verweis. Viele von ihnen sind Listen von wirklichen Städten und Lay-Outs von wirklichen gedruckten Stromkreisen.

Menschliche Leistung auf TSP

Der TSP, insbesondere die Euklidische Variante des Problems, hat die Aufmerksamkeit von Forschern in der kognitiven Psychologie angezogen. Es wird bemerkt, dass Menschen im Stande sind, gute Qualitätslösungen schnell zu erzeugen. Das erste Problem der Zeitschrift des Problem-Lösens wird dem Thema der menschlichen Leistung auf TSP gewidmet.

TSP Pfad-Länge für zufälligen pointset in einem Quadrat

Nehmen Sie an, dass N-Punkte in einem 1 x 1 Quadrat mit N>> 1 zufällig verteilt werden. Denken Sie viele solche Quadrate. Nehmen Sie an, dass wir den Durchschnitt der kürzesten Pfad-Länge wissen wollen (d. h. TSP Lösung) jedes Quadrats.

Tiefer gebunden

ist ein niedrigerer gebunden erhalten durch das Annehmen von mir, ein Punkt in der Tour-Folge sein, und ich habe seinen nächsten Nachbar als sein folgendes im Pfad.

ist ein besserer tiefer gebunden erhalten durch das Annehmen, dass ich folgend bin, ist ich bin am nächsten, und ich bin vorherig ist ich bin am nächsten zweit.

ist ein noch besserer tiefer gebunden erhalten durch das Teilen der Pfad-Folge in zwei Teile als before_i und after_i mit jedem Teil, der N/2 Punkte enthält, und dann den before_i Teil löscht, um einen verdünnten pointset zu bilden (sieh Diskussion).

• David S. Johnson hat einen durch das Computerexperiment gebundenen niedrigeren erhalten:

wohin 0.522 aus den Punkten in der Nähe von der Quadratgrenze kommt, die weniger Nachbarn haben.

• Christine L. Valenzuela und Antonia J. Jones haben einen anderen erhalten, der tiefer durch das Computerexperiment gebunden ist:

Ober gebunden

Durch die Verwendung der Vorgetäuschten Ausglühen-Methode an Proben von N=40000 zeigt Computeranalyse einen gebundenen oberen

, wohin 0.72 aus der Grenzwirkung kommt.

Weil die wirkliche Lösung nur der kürzeste Pfad zu den Zwecken von der Programmatic-Suche ist, ist ein anderer ober gebunden die Länge jeder vorher entdeckten Annäherung.

Das Handlungsreisender-Problem des Analytikers

Es gibt ein analoges Problem in der geometrischen Maß-Theorie, die den folgenden fragt: Unter welchen Bedingungen eine Teilmenge E des Euklidischen Raums kann, in einer korrigierbaren Kurve enthalten werden (d. h. wenn ist dort eine dauernde Kurve, die besucht jeden Punkt in E)? Dieses Problem ist als das Handlungsreisender-Problem des Analytikers oder das geometrische Handlungsreisender-Problem bekannt.

Populäre Kultur

Handlungsreisender (2012-Film), durch Direktor Timothy Lanzone, ist die Geschichte von 4 von der US-Regierung angestellten Mathematikern, um das am meisten schwer erfassbare Problem in der Informatik-Geschichte zu beheben: P dagegen. NP.

Siehe auch

• Kanadisches Reisender-Problem
• Fahrzeugroutenplanungsproblem
• Weg-Schauproblem
• Satz TSP Problem
• Sieben Brücken von Königsberg
• Reisen-Reiseproblem
• Tube-Herausforderung

Referenzen

..............

Weiterführende Literatur

....................

Links

• Handelsreisender-Problem an der Technologie von Georgia
• TSPLIB an der Universität Heidelbergs
• Handelsreisender-Problem durch Jon McLoone, der auf einem Programm von Stephen Wolfram, nach der Arbeit von Stan Wagon, Demonstrationsprojekt von Wolfram gestützt ist.
• optimap eine Annäherung mit ACO auf GoogleMaps mit JavaScript
• tsp ein genauer solver das Verwenden der Einschränkungsprogrammierung auf GoogleMaps
• Demo applet eines genetischen Algorithmus, TSPs und VRPTW Probleme lösend
• Quellcodebibliothek für das Handlungsreisender-Problem
• TSP solvers in R für symmetrischen und asymmetrischen TSPs. Führt verschiedene Einfügung durch, nächster Nachbar und 2 - wählen Heuristik und eine Schnittstelle zu Technologie-Concorde von Georgia und Verkettete Heuristik von Lin-Kernighan.
• Handelsreisender (auf IMDB)
• Handelsreisender-Filmbeamter webpage des Handelsreisender-Films (2012)