Problem mit reisenden Verkäufern

Das Problem mit reisenden Verkäufern (auch als die genannt Reiseberacher Problem oder TSP) stellt die folgende Frage: "Was ist angesichts einer Liste von Städten und den Entfernungen zwischen jedem Städtepaar die kürzeste Route, die jede Stadt genau einmal besucht und in die Ursprungsstadt zurückkehrt?" Es ist ein Np-harte Problem in Kombinatorische Optimierung, wichtig in Theoretische Informatik und Unternehmensforschung.

Das Reiseberagerproblem und die Fahrzeugroutingproblem sind beide Verallgemeinerungen von TSP.

In dem Theorie der rechnerischen Komplexität, die Entscheidungsversion des TSP (wo eine Länge gegeben wurde LDie Aufgabe ist zu entscheiden, ob die Grafik höchstens eine Tournee hat L) gehört zur Klasse von NP-Complete Probleme. Somit ist es möglich, dass die schlimmsten Fall Laufzeit Für jeden Algorithmus für den TSP erhöht sich superpolynomial (aber nicht mehr als exponentiell) mit der Anzahl der Städte.

Das Problem wurde erstmals 1930 formuliert und ist eines der intensiv untersuchten Probleme bei der Optimierung. Es wird als Benchmark für viele Optimierungsmethoden. Obwohl das Problem rechenintensiv ist, viele, viele Heuristik und exakte Algorithmen sind bekannt, so dass einige Fälle mit Zehntausenden von Städten vollständig gelöst werden können und sogar Probleme mit Millionen von Städten innerhalb eines kleinen Bruchteils von 1%angenähert werden können.^[1]

Der TSP hat auch in seiner reinsten Formulierung mehrere Anwendungen, wie z. Planung, Logistikund die Herstellung von Mikrochips. Leicht modifiziert, es erscheint in vielen Bereichen als Teilproblem, wie z. DNA-Sequenzierung. In diesen Anwendungen das Konzept Stadt repräsentiert zum Beispiel Kunden, Lötpunkte oder DNA -Fragmente und das Konzept Distanz repräsentiert Reisezeiten oder Kosten oder a Ähnlichkeitsmaß zwischen DNA -Fragmenten. Der TSP erscheint auch in der Astronomie, da Astronomen, die viele Quellen beobachten, die Zeit minimieren möchten, die das Teleskop zwischen den Quellen verschiebt. Bei solchen Problemen kann der TSP in eine eingebettet werden Optimales Kontrollproblem. In vielen Anwendungen können zusätzliche Einschränkungen wie begrenzte Ressourcen oder Zeitfenster auferlegt werden.

Geschichte

Die Ursprünge des Problems mit reisenden Verkäufern sind unklar. Ein Handbuch für reisende Verkäufer aus 1832 erwähnt das Problem und beinhaltet Beispieltouren durch Deutschland und Schweizenthält aber keine mathematische Behandlung.^[2]

Der TSP wurde im 19. Jahrhundert vom irischen Mathematiker mathematisch formuliert William Rowan Hamilton und vom britischen Mathematiker Thomas Kirkman. Hamilton's icosianisches Spiel war ein Freizeitpuzzle, das auf der Suche nach einem basierte Hamilton -Zyklus.^[3] Die allgemeine Form des TSP scheint in den 1930er Jahren in Wien und in Harvard erstmals von Mathematikern untersucht worden zu sein, insbesondere von Karl Menger, der das Problem definiert, betrachtet den offensichtlichen Brute-Force-Algorithmus und beobachtet die Nichtoptimalität des nächsten Nachbarn Heuristic:

Wir bezeichnen durch Messenger -Problem (Da diese Frage in der Praxis von jedem Postboten sowieso auch von vielen Reisenden gelöst werden sollte.) Natürlich ist dieses Problem durch endlich viele Versuche lösbar. Regeln, die die Anzahl der Versuche unter die Anzahl der Permutationen der angegebenen Punkte untersuchen würden, sind nicht bekannt. Die Regel, dass man zuerst vom Ausgangspunkt zum nächsten Punkt wechselt, dann bis zu dem Punkt usw., im Allgemeinen liefert im Allgemeinen nicht die kürzeste Route.^[4]

Es wurde erstmals in den 1930er Jahren von mathematisch angesehen Merrill M. Flood Wer wollte ein Problem mit dem Schulbus lösen.^[5] Hassler Whitney bei Princeton Universität generierte Interesse an dem Problem, das er als "48 -Staaten -Problem" bezeichnete. Die früheste Veröffentlichung unter Verwendung des Ausdrucks "Reisebereicherproblem" war 1949 Rand Corporation berichtet von Julia Robinson"Über das Hamiltonian -Spiel (ein Problem mit reisenden Verkäufern)."^[6][7]

In den 1950er und 1960er Jahren wurde das Problem in wissenschaftlichen Kreisen in Europa und den Vereinigten Staaten nach dem immer beliebter Rand Corporation in Santa Monica Angebotene Preise für Schritte zur Lösung des Problems.^[5] Bemerkenswerte Beiträge wurden von geleistet von George Dantzig, Delbert Ray Fulkerson und Selmer M. Johnson von der Rand Corporation, die das Problem als Ganzzahl lineares Programm und entwickelte die Schneidebene Methode für seine Lösung. Sie schrieben das, was als wegweisende Papier zu dem Thema gilt, in dem sie mit diesen neuen Methoden eine Instanz mit 49 Städten auf Optimalität lösten, indem sie eine Tour konstruierten und beweisen, dass keine andere Tour kürzer sein könnte. Dantzig, Fulkerson und Johnson spekulierten jedoch, dass wir angesichts einer nahezu optimalen Lösung möglicherweise Optimalität finden oder Optimalität nachweisen können, indem wir eine kleine Anzahl zusätzlicher Ungleichheiten (Schnitte) hinzufügen. Sie verwendeten diese Idee, um ihr anfängliches 49 Stadtproblem mit einem String -Modell zu lösen. Sie stellten fest, dass sie nur 26 Schnitte brauchten, um für ihr 49 Stadtproblem zu einer Lösung zu kommen. Während dieses Papier keinen algorithmischen Ansatz für TSP -Probleme enthielt, waren die Ideen, die darin lagen, unverzichtbar, um später genaue Lösungsmethoden für den TSP zu erstellen, obwohl es 15 Jahre dauern würde, um einen algorithmischen Ansatz bei der Erstellung dieser Schnitte zu finden.^[5] Dantzig, Fulkerson und Johnson benutzten nicht nur die Methoden der Ebene, sondern verwendeten nicht nur Methoden Zweig und gebunden Algorithmen vielleicht zum ersten Mal.^[5]

Im Jahr 1959, Jillian Beardwood, J.H. Halton und John Hammersley veröffentlichte einen Artikel mit dem Titel "Der kürzeste Weg durch viele Punkte" im Journal of the Cambridge Philosophical Society.^[8]Das Bartwood -Haldon -Hammersley -Theorem bietet eine praktische Lösung für das Problem der reisenden Verkäufer. Die Autoren haben eine asymptotische Formel abgeleitet, um die Länge der kürzesten Route für einen Verkäufer zu bestimmen, der in einem Haus oder Büro startet, und eine feste Anzahl von Standorten besucht, bevor sie zum Start zurückkehrten.

In den folgenden Jahrzehnten wurde das Problem von vielen Forschern von untersucht Mathematik, Informatik, Chemie, Physikund andere Wissenschaften. In den 1960er Jahren wurde jedoch ein neuer Ansatz erzeugt, der anstatt optimale Lösungen zu suchen, die eine Lösung erzeugen würden, deren Länge nachdenklich durch ein Vielfaches der optimalen Länge begrenzt ist und dabei niedrige Grenzen für das Problem schaffen würde; Diese unteren Grenzen würden dann mit Zweig- und gebundenen Ansätzen verwendet. Eine Methode, dies zu tun, bestand darin, a zu erstellen Minimum Spanning Tree des Diagramms und dann alle seine Kanten verdoppeln, was die Grenze erzeugt, dass die Länge einer optimalen Tour höchstens das Gewicht eines minimalen Spannungsbaums ist.^[5]

1976 machten Christofides und Serdyukov unabhängig voneinander einen großen Fortschritt in diese Richtung:^[9] das Christofides-serdyukov-Algorithmus ergibt eine Lösung, die im schlimmsten Fall höchstens 1,5 -mal länger ist als die optimale Lösung. Da der Algorithmus einfach und schnell war, hofften viele, dass dies einer nahezu optimalen Lösungsmethode weichen würde. Diese Verbesserungs Hoffnung trat jedoch nicht sofort zu, und Christofides-Serdyukov blieb die Methode mit dem besten Worst-Case-Szenario bis 2011, als ein (sehr) leicht verbesserter Approximationsalgorithmus für die Untergruppe von "grafischen" TSPs entwickelt wurde.^[10] Im Jahr 2020 wurde diese winzige Verbesserung auf den vollen (metrischen) TSP ausgedehnt.^[11][12]

Richard M. Karp zeigten 1972, dass die Hamilton -Zyklus Problem war NP-Completedas impliziert die NP-Hardness von TSP. Dies lieferte eine mathematische Erklärung für die offensichtliche rechnerische Schwierigkeit, optimale Touren zu finden.

Große Fortschritte wurden in den späten 1970er und 1980 erzielten, als Grötschel, Padberg, Rinaldi und andere es schafften, Instanzen mit bis zu 2.392 Städten zu lösen, wobei Schneidebenen und mit Schneidebenen und mit Zweig und gebunden.

In den 1990ern, Applegate, Bixby, Chvátal, und Kochen entwickelte das Programm Concorde Das wurde in vielen neueren Rekordlösungen verwendet. Gerhard Reinelt veröffentlichte 1991 die TSPLIB, eine Sammlung von Benchmark -Fällen unterschiedlicher Schwierigkeiten, die von vielen Forschungsgruppen zum Vergleich der Ergebnisse verwendet wurden. Im Jahr 2006 berechneten Cook und andere eine optimale Tour durch eine 85.900-Städte-Instanz, die durch ein Microchip-Layout-Problem gegeben wurde, derzeit die größte gelöste TSPLIB-Instanz. In vielen anderen Fällen mit Millionen von Städten können Lösungen gefunden werden, die garantiert innerhalb von 2–3% einer optimalen Tour liegen.^[13]

Beschreibung

Als Grafikproblem

TSP kann als modelliert werden ungerichtete gewichtete Grafik, so dass Städte die Grafiken sind Eckpunkte, Pfade sind die Grafiken Kantenund der Abstand eines Pfades ist das Gewicht der Kante. Es handelt sich um ein Minimierungsproblem Scheitel Nachdem sie sich besucht haben Scheitel genau einmal. Oft ist das Modell a Komplette Graph (d. H. Jedes Eckpaar ist durch eine Kante verbunden). Wenn zwischen zwei Städten kein Weg vorhanden ist, vervollständigt das Hinzufügen einer ausreichend langen Kante das Diagramm, ohne die optimale Tour zu beeinflussen.

Asymmetrisch und symmetrisch

In dem Symmetrischer TSPDer Abstand zwischen zwei Städten ist in jeder entgegengesetzten Richtung gleich und bildet eine ungerichtete Grafik. Diese Symmetrie halbiert die Anzahl der möglichen Lösungen. In dem Asymmetrischer TSP, Wege existieren möglicherweise nicht in beide Richtungen oder die Entfernungen können unterschiedlich sein und bilden a gerichteter Graph. Verkehrskollisionen, Einbahnstraßenund Flugpreise für Städte mit unterschiedlichen Abfahrungs- und Ankunftsgebühren sind Beispiele dafür, wie diese Symmetrie zusammenbrechen könnte.

Verwandte Probleme

• Eine äquivalente Formulierung in Bezug auf Graphentheorie IS: gegeben a Komplette gewichtete Grafik (Wenn die Eckpunkte die Städte darstellen, die Kanten die Straßen darstellen und die Gewichte die Kosten oder Entfernung dieser Straße sind) finden Sie a Hamilton -Zyklus mit dem geringsten Gewicht.
• Die Anforderung, in die Startstadt zurückzukehren Rechenkomplexität von dem Problem siehe Hamiltonian Path Problem.
• Ein anderes verwandtes Problem ist das Engpass -Travel -Verkäuferproblem (TSP -TSP): Finden Sie einen Hamiltonschen Zyklus in a gewichtete Grafik mit dem minimalen Gewicht der Gewichtsten Kante. Vermeiden Sie beispielsweise enge Straßen mit großen Bussen.^[14] Das Problem ist von erheblicher praktischer Bedeutung, abgesehen von offensichtlichen Transport- und Logistikbereichen. Ein klassisches Beispiel ist in Leiter Fertigung: Planung einer Route der bohren Maschine zum Bohren von Löchern in einer Leiterplatte. Bei Roboterbearbeitungs- oder Bohranwendungen sind die "Städte" Teile für Maschinen oder Löcher (unterschiedlicher Größen) zum Bohrer, und die "Reisekosten" beinhalten Zeit für die Umrüstung des Roboters (Problem mit einer einzigen Maschine -Auftragssequenzierung).^[15]
• Das Verallgemeinerter ReiseverkäuferproblemAuch als "reisender Politikerproblem" bezeichnet, befasst sich mit "Staaten", die (eine oder mehrere) "Städte" haben, und der Verkäufer muss genau eine "Stadt" von jedem "Staat" besuchen. Eine Anwendung wird angetroffen, um eine Lösung für die zu bestellen Lagerprobleme abschneiden Um Messeränderungen zu minimieren. Ein anderer geht es mit dem Bohren in Halbleiter Fertigung, siehe z. B., US -Patent 7.054.798. Noon und Bean zeigten, dass das verallgemeinerte Trailsman -Verkäuferproblem mit der gleichen Anzahl von Städten in einen Standard -TSP umgewandelt werden kann, aber eine modifizierte TSP Entfernungsmatrix.
• Das aufeinanderfolgende Auftragsproblem befasst sich mit dem Problem, eine Reihe von Städten zu besuchen, in denen Vorrangverhältnisse zwischen den Städten bestehen.
• Eine gemeinsame Interviewfrage bei Google ist, wie Daten zwischen Datenverarbeitungsknoten weitergeleitet werden. Die Routen variieren nach Zeit, um die Daten zu übertragen, aber Knoten unterscheiden sich auch durch ihre Rechenleistung und -speicher, wodurch das Problem des Sendens von Daten verbessert wird.
• Das Reiseberagerproblem Angebote mit einem Käufer, der mit dem Kauf einer Reihe von Produkten beauftragt ist. Er kann diese Produkte in mehreren Städten kaufen, aber zu unterschiedlichen Preisen und nicht alle Städte bieten die gleichen Produkte an. Ziel ist es, eine Route zwischen einer Teilmenge der Städte zu finden, die die Gesamtkosten (Reisekosten + Einkaufskosten) minimiert und den Kauf aller erforderlichen Produkte ermöglicht.

Ganzzahl lineare Programmierformulierungen

Der TSP kann als formuliert werden Ganzzahl lineares Programm.^[16][17][18] Mehrere Formulierungen sind bekannt. Zwei bemerkenswerte Formulierungen sind die Formulierung von Miller -Tucker -Zemlin (MTZ) und die Formulierung von Dantzig -Fulkerson -Johnson (DFJ). Die DFJ -Formulierung ist stärker, obwohl die MTZ -Formulierung in bestimmten Einstellungen immer noch nützlich ist.^[19][20]

Gemeinsam für diese beiden Formulierungen ist, dass man die Städte mit den Zahlen bezeichnet ${\ displayStyle 1, \ ldots, n}$ und nimmt ${\ displayStyle c_ {ij}> 0}$ die Entfernung von der Stadt sein ${\ displayStyle i}$ nach Stadt ${\ displayStyle j}$. Die Hauptvariablen in den Formulierungen sind:

$oder }}}$

Dies liegt daran, dass die Formulierungen mit 0/1 Variablen integer -Programme werden; Alle anderen Einschränkungen sind rein linear. Insbesondere das Ziel im Programm ist zu

Minimieren Sie die Tourlänge $oder$.

Ohne weitere Einschränkungen, die ${\ displaystyle \ {x_ {ij} \} _ {i, j}}$ wird jedoch effektiv über alle Teilmengen der Kantenmenge liegen, was weit von den Kanten in einer Tour entfernt ist, und ermöglicht ein triviales Minimum, wo alle ${\ displaystyle x_ {ij} = 0}$. Daher haben beide Formulierungen auch die Einschränkungen, dass es an jedem Scheitelpunkt genau eine eingehende Kante und eine ausgehende Kante ist, was als die ausgedrückt werden kann ${\ displayStyle 2n}$ lineare Gleichungen

${\ displayStyle \ sum _ {i = 1, i \ neq j}^{n} x_ {ij} = 1}$ zum ${\ displayStyle j = 1, \ ldots, n}$ und ${\ displaystyle \ sum _ {j = 1, j \ neq i}^{n} x_ {ij} = 1}$ zum ${\ displayStyle i = 1, \ ldots, n}$.

Diese sorgen dafür eines Tour, die alle Scheitelpunkte besucht, während die gewählten Kanten mehrere Touren ausmachen, die jeweils nur eine Untergruppe der Eckpunkte besuchen. Es ist wohl diese globale Anforderung, die TSP zu einem schwierigen Problem macht. Die MTZ- und DFJ -Formulierungen unterscheiden sich darin, wie sie diese endgültige Anforderung als lineare Einschränkungen ausdrücken.

Miller -Tucker -Zemlin -Formulierung^[21]

In Ergänzung zu ${\ displaystyle x_ {ij}}$ Variablen wie oben, gibt es für jeden ${\ displayStyle i = 2, \ ldots, n}$ eine Dummy -Variable ${\ displayStyle u_ {i}}$ Das verfolgt die Reihenfolge, in der die Städte besucht werden, und zählt aus der Stadt ${\ displayStyle 1}$; Die Interpretation ist das ${\ displayStyle u_ {i} <u_ {j}}$ impliziert Stadt ${\ displayStyle i}$ wird vor der Stadt besucht ${\ displayStyle j}$. Für eine bestimmte Tour (wie in Werte der Werte der ${\ displaystyle x_ {ij}}$ Variablen) kann man zufriedenstellende Werte für die finden ${\ displayStyle u_ {i}}$ Variablen durch machen ${\ displayStyle u_ {i}}$ entspricht der Anzahl der Kanten entlang dieser Tour, wenn sie aus der Stadt gehen ${\ displayStyle 1}$ nach Stadt ${\ displayStyle i}$.

Weil lineare Programmierfestigkeit nicht strenge Ungleichheiten (${\ displayStyle \ Geq}$) über strenger (${\ displayStyle>}$), wir möchten den Effekt einschränken

${\ displayStyle u_ {j} \ geq u_ {i} +1}$ wenn ${\ displaystyle x_ {ij} = 1}$.

Nur erforderlich ${\ displayStyle u_ {j} \ geq u_ {i}+x_ {ij}}$ möchten nicht Erreichen Sie das, weil dies auch erfordert ${\ displayStyle u_ {j} \ geq u_ {i}}$ Wenn ${\ displaystyle x_ {ij} = 0}$, was nicht korrekt ist. Stattdessen verwenden MTZ die ${\ displayStyle (n-1) (n-2)}$ lineare Einschränkungen

$oder$ für alle unterschiedlich ${\ displayStyle i, j \ in \ {2, \ dotsc, n \}}$

wo der ständige Begriff ${\ displayStyle n-2}$ bietet ausreichend Locker, dass ${\ displaystyle x_ {ij} = 0}$ verhängt keine Beziehung zwischen ${\ displayStyle u_ {j}}$ und ${\ displayStyle u_ {i}}$.

Wie die ${\ displayStyle u_ {i}}$ Variablen erzwingen dann, dass eine einzelne Tour alle Städte besucht, dass sie (zumindest) zunehmen. ${\ displayStyle 1}$ Für jeden Schritt entlang einer Tour, wobei nur ein Rückgang zulässig ist, wo die Tour durch die Stadt verläuft${\ displayStyle 1}$. Diese Einschränkung würde durch jede Tour verletzt, die nicht durch die Stadt fließt${\ displayStyle 1}$Die einzige Möglichkeit, es zu befriedigen, ist, dass die Tour vorbei an der Stadt ist${\ displayStyle 1}$ geht auch durch alle anderen Städte.

Die MTZ -Formulierung von TSP ist daher das folgende ganzzahlige lineare Programmierungsproblem:

$oder Colon && \\ x_ {ij} \ in {} & \ {0,1 \} && i, j = 1, \ ldots, n; \\ u_ {i} \ in {} & \ mathbf {Z} && i = 2 , \ ldots, n; \\\ sum _ {i = 1, i \ neq j}^{n} x_ {ij} = {} & 1 && j = 1, \ ldots, n; \\\ sum _ {j = 1 , j \ neq i}^{n} x_ {ij} = {} & 1 && i = 1, \ ldots, n; \\ u_ {i} -u_ {j}+(n-1) x_ {ij} \ leq { } & n-2 && 2 \ leq i \ neq j \ leq n; \\ 1 \ leq u_ {i} \ leq {} & n-1 && 2 \ leq i \ leq n. \ end {ausgerichtet}}}}$

Der erste Satz von Gleichheiten erfordert, dass jede Stadt von genau einer anderen Stadt aus erreicht wird, und der zweite Satz von Gleichheiten erfordert, dass aus jeder Stadt eine Abkehr in genau eine andere Stadt gibt. Die letzten Einschränkungen erzwingen, dass es nur eine einzige Tour gibt, die alle Städte abdeckt, und nicht zwei oder mehr unzusammenhängende Touren, die nur gemeinsam alle Städte abdecken. Um dies zu beweisen, wird unten (1) gezeigt, dass jede realisierbare Lösung nur eine geschlossene Sequenz von Städten enthält und (2), dass es für jede einzelne Tour, die alle Städte abdeckt, Werte für die Dummy -Variablen gibt ${\ displayStyle u_ {i}}$ Das befriedigt die Einschränkungen.

Um zu beweisen, dass jede praktikable Lösung nur eine geschlossene Sequenz von Städten enthält, reicht es aus, zu zeigen, dass jede Untertourne in einer realisierbaren Lösung durch Stadt 1 fließt (da die Gleichheiten sicherstellen, dass es nur eine solche Tour geben kann). Denn wenn wir alle Ungleichheiten zusammenfassen, die entsprechend entsprechen ${\ displaystyle x_ {ij} = 1}$ für jede Untertour von k Schritte, die nicht durch Stadt 1 gehen, erhalten wir:

${\ displayStyle (n-1) k \ leq (n-2) k,}$

Welches ist ein Widerspruch.

Es muss nun gezeigt werden, dass für jede einzelne Tour, die alle Städte abdeckt, Werte für die Dummy -Variablen gibt ${\ displayStyle u_ {i}}$ Das befriedigt die Einschränkungen.

Definieren Sie die Tour ohne Verlust der Allgemeinheit als Ursprung (und Ende) in City 1. Wählen Sie ${\ displayStyle u_ {i} = t}$ Wenn Stadt ${\ displayStyle i}$ wird im Schritt besucht ${\ displayStyle t (i, t = 2,3, \ ldots, n)}$. Dann

${\ displayStyle u_ {i} -u_ {j} \ leq n-2,}$

seit ${\ displayStyle u_ {i}}$ kann nicht größer sein als ${\ displayStyle n}$ und ${\ displayStyle u_ {j}}$ kann nicht weniger als 2 sein; Daher sind die Einschränkungen erfüllt, wann immer ${\ displayStyle x_ {ij} = 0.}$ Zum ${\ displaystyle x_ {ij} = 1}$, wir haben:

${\ displayStyle u_ {i} -u_ {j}+(n-1) x_ {ij} = (t)-(t+1)+n-1 = n-2,}$

Befriedigung der Einschränkung.

Dantzig -Fulkerson -Johnson -Formulierung

Beschriften Sie die Städte mit den Zahlen 1,…, n und definieren:

$oder }}}$

Nehmen ${\ displayStyle c_ {ij}> 0}$ die Entfernung von der Stadt sein i nach Stadt j. Dann kann TSP als das folgende ganzzahlige lineare Programmierungsproblem geschrieben werden:

$oder Colon && \\ & \ sum _ {i = 1, i \ neq j}^{n} x_ {ij} = 1 && j = 1, \ ldots, n; \\ & \ sum _ {j = 1, j \ neq i}^{n} x_ {ij} = 1 && i = 1, \ ldots, n; \\ & \ sum _ {i \ in q} {\ sum _ {j \ neq i, j \ in Q} {x_ {{ ij}}} \ leq | q | -1 && \ forall q \ subsetneq \ {1, \ ldots, n \}, | q | \ Geq 2 \\\ end {ausgerichtet}}}$

Die letzte Einschränkung der DFJ-Formulierung sorgt dafür, dass keine ordnungsgemäße Untergruppe q eine Untertour bilden kann. Die zurückgegebene Lösung ist also eine einzige Tour und nicht die Vereinigung kleinerer Touren. Weil dies zu einer exponentiellen Anzahl möglicher Einschränkungen führt, wird es in der Praxis mit gelöst Reihengenerierung.^[22]

Berechnung einer Lösung

Die traditionellen Angriffslinien für die NP-harten Probleme sind die folgenden:

• Sich entwickeln exakte Algorithmen, die nur für kleine Problemgrößen einigermaßen schnell funktionieren.
• "Suboptimal" entwickeln oder Heuristische Algorithmen, d.h. Algorithmen, die in einer angemessenen Zeit ungefähre Lösungen liefern.
• Sonderfälle für das Problem ("Teilprobleme") finden, für die entweder bessere oder genaue Heuristiken möglich sind.

Exakte Algorithmen

Die direkteste Lösung wäre, alle zu versuchen Permutationen (bestellte Kombinationen) und sehen Sie, welches am billigsten ist (mit Verwendung Brute-Force-Suche). Die Laufzeit für diesen Ansatz liegt in einem Polynomfaktor von ${\ displayStyle o (n!)}$, das Fakultät der Anzahl der Städte, so dass diese Lösung auch in nur 20 Städten unpraktisch wird.

Eine der frühesten Anwendungen von Dynamische Programmierung ist der Held -Karp -Algorithmus Das löst das Problem rechtzeitig ${\ displayStyle o (n^{2} 2^{n})}$.^[23] Diese Grenze wurde auch durch Ausschließung inklusion erreicht, um vor dem dynamischen Programmieransatz vorzugehen.

Die Verbesserung dieser Zeitgrenzen scheint schwierig zu sein. Zum Beispiel wurde nicht festgelegt, ob eine Klassiker exakter Algorithmus Für TSP, der rechtzeitig läuft ${\ displayStyle o (1.9999^{n})}$ existiert.^[24]

Andere Ansätze sind:

• Verschiedene Zweig und gebunden Algorithmen, mit denen TSPs mit 40–60 Städten verarbeitet werden können.

• Progressive Verbesserungsalgorithmen, die Techniken verwenden, die an erinnern Lineares Programmieren. Funktioniert gut für bis zu 200 Städte.
• Implementierungen von Zweig und gebunden und problemspezifische Schnittgenerierung (Zweig und Schnitt^[25]); Dies ist die Methode der Wahl zur Lösung großer Instanzen. Dieser Ansatz enthält den aktuellen Rekord und löst eine Instanz mit 85.900 Städten, siehe Applegate et al. (2006).

Eine genaue Lösung für 15.112 deutsche Städte von TSPSPLIB wurde 2001 mit dem gefunden Schneidemethode vorgeschlagen von George Dantzig, Ray Fulkerson, und Selmer M. Johnson im Jahr 1954 basierend auf Lineares Programmieren. Die Berechnungen wurden in einem Netzwerk von 110 Prozessoren durchgeführt, die sich unterrichteten Rice University und Princeton Universität. Die Gesamtberechnungszeit entsprach 22,6 Jahren bei einem einzigen 500 MHz Alpha -Prozessor. Im Mai 2004 wurde das Problem des reisenden Verkäufers beim Besuch aller 24.978 Städte in Schweden gelöst: Es wurde eine Länge -Tournee gefunden, die ungefähr 72.500 Kilometer entspricht, und es wurde nachgewiesen, dass keine kürzere Tour vorhanden ist.^[26] Im März 2005 wurde das Problem des reisenden Verkäufers beim Besuch aller 33.810 Punkte in einer Leiterplatte gelöst Concorde TSP Solver: Es wurde eine Tour durch eine Länge von 66.048.945 Einheiten gefunden, und es wurde nachgewiesen, dass keine kürzere Tour vorhanden ist. Die Berechnung dauerte ungefähr 15,7 CPU-Jahre (Cook et al. 2006). Im April 2006 wurde eine Instanz mit 85.900 Punkten verwendet Concorde TSP Solver, über 136 CPU-Jahre, siehe Applegate et al. (2006).

Heuristik- und Annäherungsalgorithmen

Verschiedene Heuristik und Näherungsalgorithmen, die schnell gute Lösungen ergeben, wurden entwickelt. Dazu gehören die Multi-Fragment-Algorithmus. Moderne Methoden finden Lösungen für extrem große Probleme (Millionen von Städten) innerhalb einer angemessenen Zeit, die mit einer hohen Wahrscheinlichkeit nur 2–3% von der optimalen Lösung entfernt sind.^[13]

Es werden verschiedene Kategorien von Heuristiken anerkannt.

Konstruktive Heuristiken

Das Algorithmus des nächsten Nachbarn (NN) (a Gieriger Algorithmus) Lasst den Verkäufer die nächste nicht besuchte Stadt als seinen nächsten Schritt auswählen. Dieser Algorithmus ergibt schnell eine effektiv kurze Route. Für N -Städte, die zufällig in einer Ebene verteilt sind, ergibt der Algorithmus durchschnittlich einen Pfad um 25% länger als der kürzest mögliche Weg.^[27] Es gibt jedoch viele speziell arrangierte Stadtverteilungen, die dazu führen, dass der NN -Algorithmus die schlimmste Route bietet.^[28] Dies gilt sowohl für asymmetrische als auch für symmetrische TSPs.^[29] Rosenkrantz et al.^[30] zeigte, dass der NN -Algorithmus den Approximationsfaktor hat ${\ displayStyle \ theta (\ log | v |)}$ für Fälle, die die Dreieck -Ungleichheit befriedigen. Eine Variation des NN -Algorithmus, der als NF -Operator (NEST Fragment) bezeichnet wird und eine Gruppe (Fragment) der nächsten nicht besuchten Städte verbindet, kann kürzere Routen mit aufeinanderfolgenden Iterationen finden.^[31] Der NF -Bediener kann auch auf eine von NN -Algorithmus erhaltene erste Lösung zur weiteren Verbesserung eines elitären Modells angewendet werden, bei dem nur bessere Lösungen akzeptiert werden.

Das Bitonische Tour von einer Reihe von Punkten ist der Mindestperimeter Monoton Polygon Das hat die Punkte als seine Eckpunkte; es kann effizient berechnet werden Dynamische Programmierung.

Andere konstruktive Heuristik, Zweimal übereinstimmen und Stitch (MTS), zwei sequentielle Ausführungen durchführen Übereinstimmungen, wo die zweite Übereinstimmung ausgeführt wird, nachdem alle Kanten der ersten Übereinstimmung gelöscht werden, um einen Satz von Zyklen zu erhalten. Die Zyklen werden dann genäht, um die letzte Tour zu produzieren.^[32]

Der Algorithmus von Christofides und Serdyukov

Das Algorithmus von Christofides und Serdyukov Folgt einem ähnlichen Umriss, kombiniert jedoch den minimalen Spannungsbaum mit einer Lösung eines anderen Problems, Mindestgewicht Perfektes Matching. Dies gibt eine TSP -Tour, die höchstens das 1,5 -fache des optimalen ist. Es war einer der ersten Näherungsalgorithmenund war teilweise dafür verantwortlich, die Aufmerksamkeit auf Annäherungsalgorithmen als praktischen Ansatz für unlösbare Probleme. Tatsächlich wurde der Begriff "Algorithmus" erst später auf Annäherungsalgorithmen ausgedehnt; Der Christofides -Algorithmus wurde ursprünglich als die Christofides Heuristic bezeichnet.^[9]

Dieser Algorithmus untersucht die Dinge anders, indem ein Ergebnis aus der Graphentheorie verwendet wird, das die Untergrenze des TSP verbessert, die durch Verdoppelung der Kosten des minimalen Spannungsbaums stammte. Gegeben an Eulerianische Grafik Wir können eine finden Eulerian Tour in ${\ displayStyle o (n)}$ Zeit.^[5] Wenn wir also ein eulerisches Diagramm mit Städten aus einer TSP als Eckpunkte hatten, können wir leicht erkennen, dass wir eine solche Methode verwenden können, um eine eulerische Tour zu finden, um eine TSP -Lösung zu finden. Durch dreieckige Ungleichheit Wir wissen, dass die TSP -Tour nicht länger als die eulerische Tour sein kann und als solche eine untere Grenze für den TSP. Eine solche Methode wird unten beschrieben.

1. Finden Sie einen minimalen Spannungsbaum für das Problem
2. Erstellen Sie Duplikate für jede Kante, um eine eulerische Grafik zu erstellen
3. Finden Sie eine eulerische Tour für diese Grafik
4. Konvertieren Sie zu TSP: Wenn eine Stadt zweimal besucht wird, erstellen Sie eine Abkürzung aus der Stadt, bevor dies danach in der Tour zu der einen ist.

Um die untere Grenze zu verbessern, ist eine bessere Möglichkeit, ein eulerisches Diagramm zu erstellen. Durch dreieckige Ungleichheit muss das beste eulerische Diagramm die gleichen Kosten wie die beste Reiseverkäufer -Tour haben, weshalb die Suche nach optimalen eulerischen Grafiken mindestens so schwierig ist wie TSP. Eine Möglichkeit, dies zu tun, ist das minimale Gewicht Matching Verwenden von Algorithmen von ${\ displayStyle o (n^{3})}$.^[5]

Das Erstellen eines Diagramms in ein eulerisches Diagramm beginnt mit dem minimalen Spannungsbaum. Dann müssen alle Scheitelpunkte der ungeraden Reihenfolge ausgeführt werden. Daher muss eine Übereinstimmung für die Odd -Grad -Scheitelpunkte hinzugefügt werden, die die Reihenfolge jedes ungeraden Gradscheiters um eins erhöht.^[5] Dies hinterlässt uns mit einem Graphen, bei dem jeder Scheitelpunkt gleichzeitig eulerisch ist. Die Anpassung der obigen Methode gibt den Algorithmus von Christofides und Serdyukov an.

1. Finden Sie einen minimalen Spannungsbaum für das Problem
2. Erstellen Sie eine Übereinstimmung für das Problem mit den Städten der ungeraden Reihenfolge.
3. Finden Sie eine eulerische Tour für diese Grafik
4. Konvertieren Sie mit Verknüpfungen in TSP.

Paarweise Austausch

Der paarweise Austausch oder 2-opt Bei der Technik werden zwei Kanten iterativ entfernt und diese durch zwei verschiedene Kanten ersetzt, die die durch Kantenentfernung erzeugten Fragmente wieder in eine neue und kürzere Tour verbinden. Ebenso das 3-opt Technik entfernt 3 Kanten und verbindet sie wieder zu einer kürzeren Tour. Dies sind besondere Fälle der k-opt -Methode. Das Etikett Lin -Kernighan ist ein oft hörer Fehlbezeichnung für 2-opt. Lin-Kernighan ist eigentlich die allgemeinere K-OPT-Methode.

Für euklidische Fälle liefern 2-OPT-Heuristiken im Durchschnitt Lösungen, die etwa 5% besser sind als Christofides 'Algorithmus. Wenn wir mit einer anfänglichen Lösung mit a beginnen Gieriger AlgorithmusDie durchschnittliche Anzahl der Bewegungen nimmt wieder stark ab und ist ${\ displayStyle o (n)}$. Für zufällige Starts ist jedoch die durchschnittliche Anzahl der Bewegungen ${\ displayStyle o (n \ log (n))}$. Während dies in der Reihenfolge ist, ist dies eine geringe Größe, die anfängliche Anzahl der Bewegungen für kleine Probleme für einen zufälligen Start so groß ist im Vergleich zu einer aus einer gierigen Heuristik. Dies liegt daran, dass solche 2-OPT-Heuristiken "schlechte" Teile einer Lösung wie Kreuzungen ausnutzen. Diese Arten von Heuristiken werden häufig innerhalb verwendet Fahrzeugroutingproblem Heuristik zur Wiederoptimierung von Routenlösungen.^[27]

k-opt Heuristik oder Lin -Kernighan -Heuristik

Das Lin -Kernighan Heuristic ist ein Sonderfall der V-opt- oder variable-opt-Technik. Es handelt sich um die folgenden Schritte:

1. Löschen Sie bei einer Tour k gegenseitig disjunkte Kanten.
2. Zusammenbinden Sie die verbleibenden Fragmente in eine Tour zusammen und lassen Sie keine disjunkten Untertürme (dh den Endpunkt eines Fragments nicht miteinander verbinden). Dies vereinfacht tatsächlich den TSP, der in ein viel einfacheres Problem berücksichtigt wird.
3. Jeder Fragmentendpunkt kann mit verbunden sein mit 2k- 2 Andere Möglichkeiten: von 2k Gesamtfragmentendpunkte verfügbar, die beiden Endpunkte des geprüften Fragments sind nicht zugelassen. So ein eingeschränkter 2k-City TSP kann dann mit Brute-Kraft-Methoden gelöst werden, um die am wenigsten günstige Rekombination der ursprünglichen Fragmente zu finden.

Das beliebteste der k-opt-Methoden sind 3-OPT, wie von Shen Lin von eingeführt Bell Labs In einem Sonderfall von 3-OPT sind die Kanten nicht unzusammenhängend (zwei der Kanten liegen nebeneinander). In der Praxis ist es häufig möglich, eine erhebliche Verbesserung gegenüber 2-OPT ohne die kombinatorischen Kosten des allgemeinen 3-OPT zu erzielen, indem die 3-änderungen auf diese spezielle Untergruppe einschränken, in der zwei der entfernten Kanten benachbart sind. Diese sogenannte zweieinhalb-opt-OPT fällt normalerweise ungefähr in der Mitte zwischen 2-OPT und 3-OPT, sowohl hinsichtlich der Qualität der erreichten Touren als auch der Zeit, die erforderlich ist, um diese Touren zu erreichen.

V-opt heuristisch

Die Variable-OPT-Methode bezieht sich auf und eine Verallgemeinerung der k-opt -Methode. Während die k-opt Methoden entfernen eine feste Nummer (k) Von den Kanten aus der Original-Tour reparieren die Variable-OPT-Methoden die Größe des zum Entfernen gesetzten Kanten nicht. Stattdessen wachsen sie den Satz, während der Suchprozess fortgesetzt wird. Die bekannteste Methode in dieser Familie ist die Lin-Kernighan-Methode (oben als Fehlbezeichnung für 2-OPT). Shen Lin und Brian Kernighan Erstmals veröffentlichte ihre Methode 1972 und war die zuverlässigste Heuristik für die Lösung von Problemen mit reisenden Verkäufern seit fast zwei Jahrzehnten. In den späten 1980er Jahren wurden in Bell Labs von David Johnson und seinem Forschungsteam in Bell Labs fortgeschrittener Variable-OPT-Methoden entwickelt. Diese Methoden (manchmal als Lin -Kernighan -Johnson bezeichnet) bauen auf der Lin -Kernighan -Methode auf und fügen Ideen hinzu Tabu -Suche und Evolutionscomputer. Die grundlegende Lin-Kernighan-Technik liefert Ergebnisse, die garantiert mindestens 3-OPT betragen. Die Lin -Kernighan -Johnson -Methoden berechnen eine Lin -Kernighan -Tour und stören dann die Tour durch eine Mutation, die mindestens vier Kanten entfernt und die Tour wieder verbindet, dann auf eine andere Weise V-optieren Sie die neue Tour. Die Mutation reicht oft aus, um die Tour von der zu bewegen Lokales Minimum Identifiziert von Lin -Kernighan. V-OPT-Methoden werden weithin als die leistungsstärksten Heuristiken für das Problem angesehen und können Sonderfälle wie das Hamilton-Zyklusproblem und andere nicht-metrische TSPs angehen, an denen andere Heuristiken scheitern. Seit vielen Jahren hatte Lin-Kernighan-Johnson optimale Lösungen für alle TSPs identifiziert, bei denen eine optimale Lösung bekannt war und die bekanntesten Lösungen für alle anderen TSPs identifiziert hatte, auf denen die Methode ausprobiert worden war.

Randomisierte Verbesserung

Optimiert Markov -Kette Algorithmen, die lokale heuristische Subalgorithmen verwenden, finden eine Route, die für 700 bis 800 Städte extrem nahe der optimalen Route ist.

TSP ist ein Prüfstein für viele allgemeine Heuristiken, die für die kombinatorische Optimierung entwickelt wurden, wie z. genetische Algorythmen, simuliertes Glühen, Tabu -Suche, Ameisenkolonieoptimierung, Flussformationsdynamik (siehe Schwarmintelligenz) und die Cross Entropy -Methode.

Ameisenkolonieoptimierung

Künstliche Intelligenz Forscher Marco Dorigo beschrieben 1993 eine Methode zur heuristischen Erzeugung von "guten Lösungen" für den TSP mit a Simulation einer Ameisenkolonie genannt ACS (Ameisenkoloniensystem).^[33] Es modelliert das Verhalten in realen Ameisen, um kurze Wege zwischen Nahrungsquellen und ihrem Nest zu finden, und ein Emergent Verhalten, die sich aus der Präferenz der einzelnen Ameise ergeben, um zu folgen Trail -Pheromone von anderen Ameisen deponiert.

ACS sendet eine große Anzahl virtueller Ameisenagenten aus, um viele mögliche Routen auf der Karte zu untersuchen. Jede Ameise wählt wahrscheinlich die nächste Stadt aus, die auf einer Heuristik besucht wird, die die Entfernung zur Stadt und die Menge an virtuellem Pheromon kombiniert, die am Rande der Stadt abgelagert sind. Die Ameisen erforschen und deponieren das Pheromon an jeder Kante, die sie überqueren, bis sie alle eine Tour abgeschlossen haben. Zu diesem Zeitpunkt, der das kürzeste Tour -Ablagerungen virtuelles Pheromon entlang ihrer kompletten Tourroute absolvierte (Globales Trail -Aktualisierung). Die Menge an abgelagerten Pheromon ist umgekehrt proportional zur Tourlänge: Je kürzer die Tour ist, desto mehr IT -Einzahlungen.

Spezialfälle

Metrisch

In dem Metrische TSP, auch bekannt als Delta-TSP oder δ-TSP erfüllen die Intercity-Entfernungen die Dreiecksungleichung.

Eine sehr natürliche Einschränkung des TSP besteht darin, zu verlangen, dass die Entfernungen zwischen Städten a metrisch um das zu befriedigen Dreiecksungleichung; Das ist die direkte Verbindung von A zu B ist nie weiter als die Route über Zwischenprodukt C:

${\ displayStyle d_ {ab} \ leq d_ {ac}+d_ {cb}}$.

Die Kante erstreckt sich dann a metrisch auf dem Satz von Scheitelpunkten. Wenn die Städte als Punkte in der Ebene angesehen werden, viele natürlich Entfernungsfunktionen sind Metriken, und so viele natürliche Instanzen von TSP erfüllen diese Einschränkung.

Im Folgenden sind einige Beispiele für metrische TSPs für verschiedene Metriken aufgeführt.

• Im euklidischen TSP (siehe unten) ist der Abstand zwischen zwei Städten der Euklidische Entfernung zwischen den entsprechenden Punkten.
• In der geradlinigen TSP ist der Abstand zwischen zwei Städten die Summe der absoluten Werte der Unterschiede ihrer x- und y-Coordinaten. Diese Metrik wird oft als die genannt Manhattan -Entfernung oder City-Block-Metrik.
• In dem maximale Metrik, der Abstand zwischen zwei Punkten ist das Maximum der absoluten Werte ihrer Unterschiede ihrer x- und y-Coordinaten.

Die letzten beiden Metriken erscheinen beispielsweise beim Routing einer Maschine, die einen bestimmten Satz von Löchern in a bohrt gedruckte Leiterplatte. Die Manhattan-Metrik entspricht einer Maschine, die zuerst eine Koordinate und dann die andere anpasst. Die Zeit, sich zu einem neuen Punkt zu bewegen, ist die Summe beider Bewegungen. Die maximale Metrik entspricht einer Maschine, die beide Koordinaten gleichzeitig anpasst. Daher ist die Zeit, um sich zu einem neuen Punkt zu bewegen, der langsamere der beiden Bewegungen.

In seiner Definition erlaubt der TSP nicht, dass Städte zweimal besucht werden, aber viele Anwendungen benötigen diese Einschränkung nicht. In solchen Fällen kann eine symmetrische, nicht metrische Instanz auf eine metrische reduziert werden. Dies ersetzt das Originalgraphen durch ein komplettes Diagramm, in dem die Inter-City-Entfernung ${\ displayStyle d_ {ab}}$ wird durch die ersetzt kürzester Weg Länge zwischen A und B in der Originalgrafik.

Euklidisch

Wenn die Eingangszahlen willkürliche reelle Zahlen sein können, ist der euklidische TSP ein besonderer Fall von metrischer TSP, da Entfernungen in einer Ebene der Dreiecksungleichheit gehorchen. Wenn die Eingangszahlen Ganzzahlen sein müssen, wird der Vergleich der Tourenlängen mit dem Vergleich der Summen von Quadratwurzeln geeignet.

Wie der allgemeine TSP ist der euklidische TSP in beiden Fällen NP-Hard. Mit rationalen Koordinaten und diskretisierten Metrik (auf eine Ganzzahl abgerundete Entfernungen) ist das Problem NP-Vervollständigung.^[34] Mit rationalen Koordinaten und der tatsächlichen euklidischen Metrik ist der euklidische TSP in der Zählhierarchie bekannt.^[35] Eine Unterklasse PSPACE. Bei willkürlichen realen Koordinaten kann der euklidische TSP nicht in solchen Klassen sein, da es unbeabsichtigt viele mögliche Eingaben gibt. Der euklidische TSP ist jedoch wahrscheinlich die einfachste Version für Annäherung.^[36] Beispielsweise ist der minimale Spannungsbaum des Graphen, der einer Instanz des euklidischen TSP zugeordnet ist Euklidischer Minimum Spanning Treeund kann so in erwarteten o (erwartet) berechnet werdenn Protokoll n) Zeit für n Punkte (erheblich geringer als die Anzahl der Kanten). Dies ermöglicht den einfachen 2-Anerkennungsalgorithmus für TSP, wobei die obige Dreiecksungleichheit schneller funktioniert.

Im Allgemeinen für jeden c > 0, wo d Ist die Anzahl der Dimensionen im euklidischen Raum, gibt es einen Polynom-Zeit-Algorithmus, der höchstens eine Länge-Tour findet (1 + 1//c) mal das optimale für geometrische Instanzen von TSP in

${\ displaystyle o \ links (n (\ log n)^{(o (c {\ sqrt {d}})^{d-1} \ rechts),},}$

Zeit; Dies wird a genannt Polynom-Zeit-Approximationsschema (PTAs).^[37] Sanjeev Arora und Joseph S. B. Mitchell wurden mit dem ausgezeichnet Gödel -Preis 2010 für ihre gleichzeitige Entdeckung eines PTAs für den euklidischen TSP.

In der Praxis werden weiterhin einfachere Heuristiken mit schwächeren Garantien verwendet.

Asymmetrisch

In den meisten Fällen ist der Abstand zwischen zwei Knoten im TSP -Netzwerk in beiden Richtungen gleich. Der Fall, wo der Abstand von A zu B ist nicht gleich dem Abstand von B zu A wird als asymmetrischer TSP bezeichnet. Eine praktische Anwendung eines asymmetrischen TSP ist die Routenoptimierung unter Verwendung des Routings auf Straßenebene (das von Einwegstraßen, Slip-Roads, Autobahnen usw. asymmetrisch gemacht wird).

Konvertierung in symmetrisch

Das Lösen eines asymmetrischen TSP -Diagramms kann etwas komplex sein. Das Folgende ist eine 3 × 3 -Matrix, die alle möglichen Pfadgewichte zwischen den Knoten enthält A, B und C. Eine Möglichkeit besteht darin, eine asymmetrische Matrix der Größe zu drehen N in eine symmetrische Matrix der Größe 2N.^[38]

Asymmetrische Pfadgewichte

	A	B	C
A		1	2
B	6		3
C	5	4

Um die Größe zu verdoppeln, wird jeder der Knoten im Diagramm dupliziert, was eine Sekunde erstellt Geisterknoten, verbunden mit dem ursprünglichen Knoten mit einer "Ghost" -Rande des sehr niedrigen (möglicherweise negativen) Gewichts, hier bezeichnet -w. (Alternativ haben die Geisterkanten Gewicht 0 und an allen anderen Kanten Gewicht W wird hinzugefügt.) Die oben gezeigte ursprüngliche 3 × 3-Matrix ist unten links und die Transponierung des Originals im oberen rechten. Beide Kopien der Matrix haben ihre Diagonalen durch die kostengünstigen Hopfenpfade ersetzt, dargestellt durch-w. Im neuen Diagramm verknüpft kein Edge die ursprünglichen Knoten direkt und kein Edge verknüpft direkt Ghost -Knoten.

Symmetrische Pfadgewichte

	A	B	C	EIN'	B'	C'
A				−w	6	5
B				1	−w	4
C				2	3	−w
EIN'	−w	1	2
B'	6	−w	3
C'	5	4	−w

Das Gewicht -w Von den "Ghost" -Kanten, die die Geisterknoten mit den entsprechenden Originalknoten verknüpfen, müssen niedrig genug sein, um sicherzustellen, dass alle Geisterkanten zu einer optimalen symmetrischen TSP -Lösung für das neue Diagramm gehören müssen (W = 0 ist nicht immer niedrig genug). Infolgedessen erscheint in der optimalen symmetrischen Tour jeder ursprüngliche Knoten neben seinem Geisterknoten (z. B. ein möglicher Weg ist $oder$) und durch das Zusammenführen der ursprünglichen und Geisterknoten erneut eine (optimale) Lösung des ursprünglichen asymmetrischen Problems (in unserem Beispiel, ${\ displayStyle \ mathrm {a \ bis c \ bis b \ to a}}$).

Problem des Analysten

Es gibt ein analoges Problem in Geometrische Messtheorie Dies fragt Folgendes: Unter welchen Bedingungen können eine Untergruppe eine Untergruppe sein E von Euklidischer Raum in a enthalten sein reparierbare Kurve (Das heißt, wann gibt es eine Kurve mit endlicher Länge, die jeden Punkt besucht E)? Dieses Problem wird als das bezeichnet Problem des reisenden Verkäufers des Analysten.

Pfadlänge für zufällige Punktesätze in einem Quadrat

Vermuten ${\ displaystyle x_ {1}, \ ldots, x_ {n}}$ sind ${\ displayStyle n}$ unabhängige Zufallsvariablen mit gleichmäßiger Verteilung auf dem Quadrat ${\ displayStyle [0,1]^{2}}$, und lass ${\ displayStyle l_ {n}^{\ ast}}$ Seien Sie die kürzeste Pfadlänge (d. H. TSP -Lösung) für diesen Satz von Punkten gemäß den üblichen Punkten Euklidische Entfernung. Es ist bekannt^[8] das fast sicher,

$oder$

wo ${\ displayStyle \ Beta}$ ist eine positive Konstante, die nicht explizit bekannt ist. Seit ${\ displayStyle l_ {n}^{*} \ leq 2 {\ sqrt {n}}+2}$ (Siehe unten), es folgt aus Begrenzter Konvergenzsatz das $oder$daher untere und obere Grenzen auf ${\ displayStyle \ Beta}$ folgen von Grenzen auf ${\ displaystyle \ mathbb {e} [l_ {n}^{*}]}$.

Die fast sichere Grenze ${\ displaystyle {\ frac {l_ {n}^{*}} {\ sqrt {n}} \ rightarrow \ Beta}$ wie ${\ displayStyle n \ to \ inty}$ dürfen nicht existieren, wenn die unabhängigen Stellen ${\ displaystyle x_ {1}, \ ldots, x_ {n}}$ werden durch Beobachtungen aus einem stationären ergodischen Prozess mit einheitlichen Randen ersetzt.^[39]

Obere Grenze

• Hat man ${\ displayStyle l^{*} \ leq 2 {\ sqrt {n}}+2}$, und deshalb ${\ displayStyle \ Beta \ Leq 2}$durch Verwendung eines naiven Pfades, der monoton die Punkte innerhalb von jeweils besucht ${\ displayStyle {\ sqrt {n}}}$ Breite Scheiben ${\ displayStyle 1/{\ sqrt {n}}}$ im Quadrat.
• Wenig^[40] bewiesen ${\ displayStyle l_ {n}^{*} \ leq {\ sqrt {2n}}+1.75}$, somit ${\ displayStyle \ Beta \ Leq {\ sqrt {2}}}$später von Karloff (1987) verbessert: ${\ displayStyle \ Beta \ Leq 0,984 {\ sqrt {2}}}$.
• Fietcher^[41] zeigte eine Obergrenze von ${\ displayStyle \ Beta \ Leq 0.73 \ dots}$.

Untergrenze

• Indem Sie das beobachten ${\ displaystyle \ mathbb {e} [l_ {n}^{*}]}$ ist größer als ${\ displayStyle n}$ mal den Abstand zwischen ${\ displayStyle x_ {0}}$ und der engste Punkt ${\ displaystyle x_ {i} \ neq x_ {0}}$, man bekommt (nach einer kurzen Berechnung)

$oder$

• Eine bessere Untergrenze wird erhalten^[8] Indem Sie das beobachten ${\ displaystyle \ mathbb {e} [l_ {n}^{*}]}$ ist größer als ${\ displayStyle {\ tfrac {1} {2}} n}$ mal die Summe der Entfernungen zwischen ${\ displayStyle x_ {0}}$ und die engsten und zweitnächsten Punkte ${\ displaystyle x_ {i}, x_ {j} \ neq x_ {0}}$, was gibt

$oder {n}} = {\ tfrac {5} {8}} {\ sqrt {n}},},},},},}$

• Derzeit^[42] Die beste Untergrenze ist

$oder ,}$

• Gehalten und Karp^[43] gab einen Polynom-Zeit-Algorithmus, der numerische untere Grenzen für ${\ displayStyle l_ {n}^{*}}$und so für ${\ displayStyle \ Beta (\ simenq l_ {n}^{*}/{\ sqrt {n}})}$ Die scheinen bis zu mehr oder weniger 1%gut zu sein.^[44] Insbesondere David S. Johnson^[45] erhielt eine untere Bindung durch Computerexperiment:

${\ displayStyle l_ {n}^{*} \ gtrsim 0.7080 {\ sqrt {n}}+0.522,}$

wo 0,522 von den Punkten in der Nähe der quadratischen Grenze kommt, die weniger Nachbarn haben, und Christine L. Valenzuela und Antonia J. Jones^[46] erhielt die folgenden anderen numerischen Untergrenze:

${\ displayStyle l_ {n}^{*} \ gtrsim 0.7078 {\ sqrt {n}}+0.551}$.

Rechenkomplexität

Es wurde gezeigt, dass das Problem ist Np-harte (Genauer gesagt ist es vollständig für die Komplexitätsklasse FP^Np; sehen Funktionsproblem), und die Entscheidungsproblem Version ("Angesichts der Kosten und einer Nummer xentscheiden x") ist NP-Complete. Das Engpass -Travel -Verkäuferproblem ist auch np-hard. Das Problem bleibt auch für den Fall, wenn sich die Städte im Flugzeug befinden Euklidische Entfernungensowie in einer Reihe anderer restriktiver Fälle. Wenn Sie den Zustand des Besuchs jeder Stadt "nur einmal" besuchen DreiecksungleichungEine Abkürzung, die einen wiederholten Besuch überspringt, würde die Tourdauer nicht erhöhen.

Komplexität der Annäherung

Im allgemeinen Fall ist die Suche nach einer kürzesten Tour für reisende Verkäufe zu finden NPO-Komplett.^[47] Wenn die Entfernungsmaßnahme a ist metrisch (und damit symmetrisch), das Problem wird APX-Komplett^[48] und Der Algorithmus von Christofides und Serdyukov ungefähr innerhalb von 1,5.^[49][50][9] A 2020 Vordruck verbessert dies an gebunden an ${\ displayStyle 1.5-10^{-36}}$.^[51] Die bekannteste unangemessene gebundene Unangemessenheit ist 123/122.^[52]

Wenn die Entfernungen auf 1 und 2 beschränkt sind (aber immer noch eine Metrik), wird das Approximationsverhältnis 8/7.^[53] Im asymmetrischen Fall mit DreiecksungleichungBis vor kurzem waren nur logarithmische Leistungsgarantien bekannt.^[54] Im Jahr 2018 wurde von Svensson, Tarnawski und Végh eine Annäherung an konstanter Faktor entwickelt.^[55] Der beste aktuelle Algorithmus von Traub und Vygen erreicht das Leistungsverhältnis von ${\ displayStyle 22+ \ varepsilon}}$.^[56] Die bekannteste unangemessene gebundene Unangemessenheit ist 75/74.^[52]

Das entsprechende Maximierungsproblem beim Auffinden der am längsten Die Reiseverkäuferin ist innerhalb von 63/38 zu ungefähr.^[57] Wenn die Entfernungsfunktion symmetrisch ist, kann die längste Tour innerhalb von 4/3 durch einen deterministischen Algorithmus angenähert werden^[58] und innen ${\ displayStyle {\ tfrac {1} {25}} (33+ \ varepsilon)}$ durch einen randomisierten Algorithmus.^[59]

Menschliche und tierische Leistung

Der TSP, insbesondere die Euklidisch Die Variante des Problems hat die Aufmerksamkeit von Forschern in Aufmerksamkeit auf sich gezogen kognitive Psychologie. Es wurde beobachtet, dass Menschen in nahezu linearer Weise schnell optimale Lösungen produzieren können, wobei die Leistung von 1% weniger effizient für Diagramme mit 10 bis 20 Knoten bis zu 11% weniger effizient für Diagramme liegt mit 120 Knoten.^[60][61] Die offensichtliche Leichtigkeit, mit der Menschen nahezu optimale Lösungen für das Problem erzeugen, hat die Forscher dazu veranlasst, zu hypothe, dass Menschen eine oder mehrere Heuristiken verwenden.^[62][63][64] Zusätzliche Nachweise deuten jedoch darauf hin, dass die menschliche Leistung sehr unterschiedlich ist und individuelle Unterschiede sowie die Graphgeometrie die Leistung in der Aufgabe zu beeinflussen scheinen.^[65][66][67] Die Ergebnisse deuten jedoch darauf hin, dass die Computerleistung des TSP durch das Verständnis und die Emulation der von Menschen für diese Probleme verwendeten Methoden verbessert werden kann.^[68] und haben auch zu neuen Einsichten in die Mechanismen des menschlichen Denkens geführt.^[69] Die erste Ausgabe der Journal of Problemlösung war dem Thema menschlicher Leistung auf TSP gewidmet,^[70] und in einer Überprüfung von 2011 wurden Dutzende von Papieren zu diesem Thema aufgeführt.^[69]

Eine Studie von 2011 in Tierkognition Mit dem Titel "Lass die Pigeon fahren den Bus fahren", benannt nach dem Kinderbuch Lass die Taube nicht den Bus fahren!, untersuchte die räumliche Erkenntnis in Tauben, indem sie ihre Flugmuster zwischen mehreren Feeder in einem Labor in Bezug auf das Problem des reisenden Verkäufers untersuchen. Im ersten Experiment wurden Tauben in die Ecke eines Laborraums gelegt und zu den nahe gelegenen Futterhäuschen fliegen, die Erbsen enthielten. Die Forscher fanden heraus, dass Tauben weitgehend die Nähe verwendeten, um zu bestimmen, welchen Feeder sie als nächstes auswählen würden. Im zweiten Experiment wurden die Feeder so angeordnet, dass das Fliegen zum nächsten Feeder bei jeder Gelegenheit weitgehend ineffizient wäre, wenn die Tauben jeden Feeder besuchen mussten. Die Ergebnisse des zweiten Experiments weisen darauf hin, dass Tauben, während sie dennoch mit proximitätsbasierter Lösungen bevorzugen, "mehrere Schritte entlang des Weges planen können, wenn die Unterschiede in den Reisekosten zwischen effizienten und weniger effizienten Routen basierend auf der Nähe größer werden".^[71] Diese Ergebnisse stimmen mit anderen Experimenten überein, die mit Nicht-Primaten durchgeführt wurden, die gezeigt haben, dass einige Nicht-Primate komplexe Reiserouten planen konnten. Dies deutet darauf hin, dass Nicht-Primate eine relativ ausgefeilte räumliche kognitive Fähigkeit besitzen.

Natürliche Berechnung

Wenn Sie eine räumliche Konfiguration von Nahrungsquellen präsentieren, ist die Amoeboid Physarum polycephalum passt seine Morphologie an einen effizienten Weg zwischen den Nahrungsquellen, der auch als ungefähre Lösung für TSP angesehen werden kann.^[72]

Benchmarks

Für das Benchmarking von TSP -Algorithmen, TSplib^[73] ist eine Bibliothek von Beispielfällen des TSP und verwandte Probleme werden beibehalten, siehe die externe TSPLIB -Referenz. Viele von ihnen sind Listen der tatsächlichen Städte und Layouts der tatsächlichen Layouts Leiterplatte.

Popkultur

• Reisender VerkäuferVon Regisseur Timothy Lanzone ist die Geschichte von vier Mathematikern, die von der US-Regierung eingestellt wurden, um das schwer fassbare Problem in der Geschichte der Computerwissenschaft zu lösen: P gegen NP.^[74] Lösungen für das Problem werden von Mathematiker verwendet Bob Bosche in einem Subgenre namens TSP Art.^[75]

Siehe auch

• Kanadisches Reisenderproblem
• Exakter Algorithmus
• Routeninspektionsproblem (Auch als "chinesisches Postmanproblem" bekannt))
• Setzen Sie das TSP -Problem
• Sieben Brücken von Königsberg
• Steiner reisender Verkäuferproblem
• U -Bahn -Herausforderung
• Rohr Herausforderung
• Fahrzeugroutingproblem
• Graph -Erkundung
• Gemischtes chinesisches Postmanproblem
• Bogenrouting
• Schneepflugroutingproblem

Anmerkungen

Verweise

Weitere Lektüre

Externe Links

• Problem mit reisenden Verkäufern Bei der Wayback -Maschine (archiviert am 17. Dezember 2013) bei Universität von Waterloo
• Tsplib Bei der Universität von Heidelberg
• Problem mit reisenden Verkäufern von Jon McLoone beim Wolfram Demonstrationsprojekt
• TSP -Visualisierungstool