Warum ist das Problem des Handlungsreisenden „schwierig“?

Das Problem des Handlungsreisenden ist ursprünglich ein Mathematik/Informatik-Optimierungsproblem, bei dem es darum geht, einen Weg zwischen einer Gruppe von Städten so zu bestimmen, dass man nach genau einem Besuch jeder Stadt zur Ausgangsstadt zurückkehrt und die Gesamtstrecke (Längengrad/ Breitengrad) wird minimiert. Für N Städte gibt es ( N − 1 ) ! / 2 einzigartige Wege - und das können wir so sehen N zunimmt, wird die Anzahl der zu berücksichtigenden Pfade enorm groß. Selbst für eine kleine Anzahl von Städten (z. B. 15 Städte) können moderne Computer dieses Problem nicht mit "brute force" lösen (dh alle möglichen Routen berechnen und die kürzeste zurückgeben) - die Folge sind ausgefeilte Optimierungsalgorithmen und Näherungsverfahren verwendet, um dieses Problem im wirklichen Leben anzugehen.

Ich habe versucht, meinem Freund dieses Problem zu erklären, aber mir ist kein Beispiel eingefallen, das zeigt, warum das Problem des Handlungsreisenden schwierig ist! Aus dem Kopf heraus habe ich versucht, ein Beispiel zu geben, wo jemand den kürzesten Weg zwischen Boston, Chicago und Los Angeles finden muss - aber dann wurde mir klar, dass der kürzeste Weg in diesem Fall ziemlich offensichtlich ist! (dh Bewegung in der allgemeinen Ost-West-Richtung).

Reale Anwendungen des Problems des Handlungsreisenden neigen dazu, eine zusätzliche Komplexitätsebene aufzuweisen, da sie im Allgemeinen „Kosten“ haben, die zwischen Paaren von Städten verbunden sind – und diese Kosten müssen nicht symmetrisch sein. Beispielsweise könnten Busse häufiger von einer Kleinstadt in eine Großstadt fahren, aber seltener von der Großstadt in die Kleinstadt zurückkehren - daher können wir möglicherweise jeder Richtung "Kosten" zuordnen . Oder sogar ein einfacheres Beispiel: Sie müssen möglicherweise "bergauf" fahren, um von Stadt A nach Stadt B zu fahren, aber "bergab", um von Stadt B nach Stadt A zu fahren - daher entstehen wahrscheinlich höhere Kosten, um von Stadt A nach zu fahren Stadt B. Oft sind diese "Kosten" nicht vollständig bekannt und müssen mit einem statistischen Modell angenähert werden. Jedoch,

Aber ich suche immer noch nach einem Beispiel, um es meinem Freund zu erklären - kann mir bitte jemand helfen, ein offensichtliches und einfaches Beispiel für das Problem des Handlungsreisenden zu finden, bei dem offensichtlich klar wird, dass die Wahl des kürzesten Weges nicht offensichtlich ist? Jedes einfache Beispiel, an das ich zu denken versuche, ist tendenziell sehr offensichtlich (z. B. Manhattan, Newark, Nashville) - ich möchte meinen Freund nicht mit einem Beispiel von 1000 Städten in den USA überwältigen: nur etwas Einfaches mit 4-5 Städten darin denen nicht sofort klar ist (und vielleicht sogar kontraintuitiv ist), welcher Weg eingeschlagen werden sollte?

Ich habe versucht, ein Beispiel mit der Programmiersprache R zu zeigen, in dem es 10 (zufällige) Punkte auf einem Gitter gibt - ausgehend vom niedrigsten Punkt beinhaltet der eingeschlagene Weg die Auswahl des nächstgelegenen Punkts von jedem aktuellen Punkt:

library(ggplot2)

set.seed(123)

x_cor = rnorm(5,100,100)
y_cor = rnorm(5,100,100)


my_data = data.frame(x_cor,y_cor)

      x_cor     y_cor
1  43.95244 271.50650
2  76.98225 146.09162
3 255.87083 -26.50612
4 107.05084  31.31471
5 112.92877  55.43380


ggplot(my_data, aes(x=x_cor, y=y_cor)) + geom_point() + ggtitle("Travelling Salesperson Example")

Geben Sie hier die Bildbeschreibung ein

Aber selbst in diesem Beispiel sieht der kürzeste Weg "offensichtlich" aus (stellen Sie sich vor, Sie müssten dieses Problem am unteren rechten Punkt beginnen):

Geben Sie hier die Bildbeschreibung ein

Ich habe es mit mehr Punkten versucht:

set.seed(123)

x_cor = rnorm(20,100,100)
y_cor = rnorm(20,100,100)


my_data = data.frame(x_cor,y_cor)

ggplot(my_data, aes(x = x_cor, y = y_cor)) +
    geom_path() +
    geom_point(size = 2)

Geben Sie hier die Bildbeschreibung ein

Aber mein Freund argumentiert immer noch, dass "den nächsten Punkt vom aktuellen Punkt finden und wiederholen" (stellen Sie sich vor, Sie müssten dieses Problem am untersten Punkt rechts beginnen):

Geben Sie hier die Bildbeschreibung ein

Wie überzeuge ich meinen Freund, dass das, was er tut, einer "gierigen Suche" entspricht, die nur ein "lokales Minimum" zurückgibt und es sehr wahrscheinlich ist, dass ein kürzerer Pfad existiert? (nicht einmal der "kürzeste Weg" - nur ein "kürzerer Weg" als die "Greedy Search")

Ich habe versucht, dieses Beispiel zu veranschaulichen, indem ich ihn auf die Wikipedia-Seite zu Greedy Search verlinkt habe, die zeigt, warum Greedy Search oft das wahre Minimum verfehlen kann: https://en.wikipedia.org/wiki/Greedy_algorithm#/media/File:Greedy-search -path-example.gif

  • Könnte mir jemand helfen, ein Beispiel zu finden, um meinem Freund zu zeigen, dass die Wahl des unmittelbar nächstgelegenen Punkts von Ihrem Standort aus nicht zum insgesamt kürzesten Weg führt? (z. B. ein Beispiel, das nicht intuitiv erscheint, dh wenn Sie einen Pfad wählen, der immer auf dem nächstgelegenen Punkt von Ihrer aktuellen Position basiert, können Sie deutlich sehen, dass dies nicht der optimale Pfad ist.)

  • Gibt es einen mathematischen Beweis, der zeigt, dass der „Greedy Search“-Algorithmus in Traveling Salesperson die Möglichkeit hat, manchmal den wahren optimalen Pfad zu verfehlen?

Danke!

Es gibt einfache Beispiele auf K 4 dass Showgier nicht funktioniert. Machen Sie 5 Kanten mit dem Gewicht 1 und eine Kante mit dem Gewicht 10000.
Dem Bonuspanel dieses Comics nach zu urteilen , sollten Sie dies lesen . Eine geeignete Städtewahl würde dazu führen, dass Sie durch gieriges Suchen in einen Kreislauf geraten.
@JG Würde der Algorithmus nicht nur Städte berücksichtigen, die noch nicht besucht wurden?
@Randall Der Freund akzeptiert dieses Beispiel möglicherweise nicht, da die Abstände der Dreiecksungleichung nicht gehorchen.
@eyeballfrog Ich frage mich, ob der vorgeschlagene Text Beispiele enthält, bei denen selbst dieser gierige Algorithmus nicht geeignet ist.
@Randall: Danke für deine Antwort! Kann man sich ein solches Beispiel ohne irgendwelche Gewichte vorstellen? Danke schön!
@JG: Danke für diesen Comic und diese Empfehlungen! Ich werde sie überprüfen!
"Für n Städte gibt es (n−1)!/2" Warum haben Sie dann versucht, Beispiele mit drei Städten zu geben? Wenn N = 2 , gibt Ihre Formel nur einen eindeutigen Pfad an, daher ist es natürlich trivial, ihn zu finden.
Um es klar zu sagen, ein Greedy-Algorithmus gibt nicht unbedingt ein "lokales Minimum" zurück, in dem Sinne, dass Sie häufig die Ausgabe eines Greedy-Algorithmus nehmen, die Reihenfolge von zwei aufeinanderfolgenden Scheitelpunkten tauschen und einen kürzeren Pfad erhalten können. Die folgende Antwort von Andrew P. ist ein Beispiel dafür.
Genügend große Beispiele von TSP haben oft eklatante Fehler in ihrer Lösung für den nächsten Nachbarn, wo der Algorithmus endet, indem er eine Reihe von Punkten aufgreift, die übersehen wurden, und oft offensichtliche Linien über die gesamte Karte zieht.
Wenn Sie beweisen können, dass es schwierig ist , wartet ein Millennium-Preis auf Sie.
@Ray Gleicher Preis, wenn Sie beweisen können, dass es nicht schwierig ist.
Das Problem mit dem Greedy-Algorithmus ist nicht der Algorithmus, sondern sein Beweis. Der Nachweis, dass GA richtig oder falsch ist, ist so komplex wie TSP selbst.
Das letzte Beispiel selbst scheitert an dem vorgeschlagenen "finde den nächsten Punkt vom aktuellen Punkt und wiederhole"-Prozess. Der 2. Schritt der Lösung (gegen den Uhrzeigersinn) ist länger als der Schritt, den sie bis zu dem Punkt bei ~(170, 60) hätte machen können usw.
Eine andere Idee, die ich hatte, war, den Massenmittelpunkt zu finden und dann einen Pfad gegen den Uhrzeigersinn / im Uhrzeigersinn um ihn herum zu zeichnen. Ich habe voll und ganz mit einem weiteren Gegenbeispiel dazu gerechnet.
Ich bin ziemlich überrascht, dass ggplot diese Punkte verbindet, indem es das globale Optimum sucht? Ich meine, wie würde es aussehen, wenn es 1000 Punkte gibt? Oder hast du sie angeschlossen?
Es gibt kein Problem mit reisenden Verkäufern (?)
Etwas verwandt: Warum ist Dantzigs Lösung für das Rucksackproblem nur ungefähr, fragt, warum ein verwandtes Problem „Rucksack“ schwierig ist und warum ein analoger „gieriger“ Algorithmus nicht funktioniert. In meiner Antwort gab ich einige Gründe an, die auch hier gelten: „Wir könnten die allgemeine Schwierigkeit wie folgt charakterisieren: Eine Wahl, die früh gut schien, geriet später in Schwierigkeiten, weil unsere frühe Entscheidung uns dazu zwingt, [einen sehr schlechten Zug] danach zu machen . Die optimale Lösung erfordert viele Entscheidungen, die auf kurze Sicht suboptimal erscheinen, aber gut zusammenarbeiten.“
@stats_noob Falls Sie sich fragen, worum es bei dieser Bearbeitung ging: Ich glaube, sie diente dem einzigen Zweck, Ihre Frage von der Hot Network Question (HNQ)-Liste zu streichen. Fragen mit mathjax im Titel kommen für diese Liste nicht in Frage, da nicht jede SE-Site mathjax unterstützt. Ich persönlich halte das für Vandalismus ...
Versuchen Sie immer noch herauszufinden, wie „Busse häufiger geplant werden können, um von einer kleinen Stadt in eine große Stadt zu fahren“, ohne dass am Ende ein Überschuss an ungenutzten Bussen in der kleinen Stadt entsteht.

Antworten (10)

Hier ist ein einfaches explizites Beispiel, bei dem der Greedy-Algorithmus immer fehlschlägt, diese Anordnung von Städten (und euklidischen Entfernungen):

(0,1), (10, 0), (0,-1), (-10,0)

Wenn Sie den Greedy-Algorithmus auf dieses Diagramm anwenden, sieht es wie folgt aus (oder eine umgedrehte Version):

Dies gilt unabhängig vom Ausgangspunkt. Das heißt, der Greedy-Algorithmus gibt uns einen Pfad mit einer zurückgelegten Gesamtstrecke von 20 + 2 + 2 101 ≈ 42.1

Das ist natürlich nicht die optimale Lösung. Wenn Sie es nur genau betrachten, können Sie sehen, dass dies der beste Weg ist:

Es hat eine Gesamtlänge von 4 101 ≈ 40.2 , was besser ist als der Greedy-Algorithmus.

Sie können Ihrem Freund erklären, dass der Greedy-Algorithmus fehlschlägt, weil er nicht vorausschaut. Es sieht den kürzesten Weg (in diesem Fall den vertikalen) und nimmt ihn. Dies kann es jedoch später zwingen, einen viel langen Weg einzuschlagen, wodurch es auf lange Sicht schlechter gestellt wird. Während es in diesem Beispiel einfach zu sehen ist, ist es viel schwieriger, jeden Fall zu erkennen, in dem dies passiert.

Tolles Beispiel. Wenn Sie ganze Zahlen bevorzugen, verwenden Sie eine Raute ( 0 , ± 5 ) , ( ± 12 , 0 ) also sind die Seiten 13 und die Diagonalen 10 und 24. Dann ist der beste Zyklus 13+13+13+13=52, aber der gierige Zyklus (egal wo du beginnst) ist 13+10+13+24=60.
Beachten Sie, dass der gierige Pfad hier tatsächlich für einen nicht kreisförmigen Pfad erfolgreich sein würde, wenn Sie von den Ost- oder Weststädten aus starten. Nur die Anforderung, zum Ausgangspunkt zurückzukehren, lässt dieses Beispiel für den Greedy-Algorithmus fehlschlagen.

Mir scheint, Sie suchen nach einer intuitiven Einsicht und nicht nach einem Gegenbeispiel oder einem formalen Beweis. Das habe ich mich vor vielen Jahren auch gefragt und folgendes hat mir zu einer intuitiven Einsicht verholfen:

Ich habe mit einem TSP-Solver-Programm namens Concorde experimentiert. Mit diesem Programm können Sie Punkte platzieren und es kann auch zufällig Punkte fallen lassen. Es zeigt dann den Lösungsprozess, während er passiert.

Sie können dann live sehen, wie sich der derzeit bekannte beste Pfad entwickelt. Es werden ganz unterschiedliche Wege gezeigt, jeder ein bisschen besser als zuvor.

Das hat mir gezeigt, dass sehr unterschiedliche Wege zu inkrementellen kleinen Verbesserungen führen können. Und das hat mir gezeigt, wie "nicht-konvex" die Lösung ist. Sie können nicht einfach einen Hill-Climbing-Algorithmus verwenden, um sich auf die beste Lösung zu konzentrieren. Das Problem enthält Entscheidungspunkte, die zu sehr unterschiedlichen Teilen des Suchraums führen.

Das ist eine völlig unformelle Betrachtungsweise, aber es hat mir sehr geholfen.

Hier ist ein Beispiel mit 7 Städten aus Wikipedia . Der Nächster-Nachbar-Algorithmus gibt unterschiedliche Pfade an, je nachdem, in welcher Stadt Sie beginnen, sodass das Ergebnis für alle bis auf einen dieser Pfade suboptimal sein muss. Die Illustration verwendet Pfade anstelle von Zyklen, aber Sie können all diese Pfade mental mit Zyklen verbinden, und mein Punkt gilt immer noch.

Geben Sie hier die Bildbeschreibung ein

„Der Nächste-Nachbar-Algorithmus gibt unterschiedliche Pfade an, je nachdem, in welcher Stadt Sie beginnen, daher muss das Ergebnis für alle bis auf einen dieser Pfade suboptimal sein.“ Könnten sie nicht alle unterschiedlich aussehen, aber immer noch die gleiche Gesamtentfernung haben? Zum Beispiel 3 Städte auf einem gleichseitigen Dreieck?
@EricDuminil Die Entfernung wird in dieser Animation oben angezeigt. Es unterscheidet sich von 249 - 325. Es kann natürlich Beispiele geben, wo die Pfade gleich sind, aber sie sind im allgemeinen Fall nicht gleich.
@kutschkem ja. Ich brauchte nur ein einziges Gegenbeispiel, um zu zeigen, dass die obige Behauptung nicht stimmt.
Der Anspruch bezieht sich auf das bereitgestellte spezifische Beispiel. Es spielt keine Rolle, dass es triviale Fälle gibt, in denen die Methode des nächsten Nachbarn optimal ist. Wie Sie sagten, ein Beispiel genügt.

Das Problem ist aufgrund der kombinatorischen Komplexität des Beweises , dass Sie die beste Antwort haben, schwierig

Es gibt einen subtilen Unterschied, wenn Leute bei Problemen wie diesem von optimalen Ergebnissen sprechen. Ein Mathematiker oder ein Operational-Research-Experte verwendet den Begriff „optimal“ anders als Laien. Viele Nicht-Experten interpretieren optimal als „gut genug“, aber Experten bestehen oft auf einem Beweis der Optimalität.

Bei der Lösung realer TSP-ähnlicher Probleme kann man argumentieren, dass die Laiendefinition ("gut genug") tatsächlich nützlicher ist (insbesondere wenn die Kosten für das Finden einer besseren Antwort hoch sind). Aber TSP-ähnliche Probleme haben ein ernsthaftes Problem damit, zu beweisen, dass eine Antwort im Expertensinn optimal ist. Wir kennen keinen effizienten Weg, um zu beweisen, dass eine gegebene Antwort die beste ist, die nicht das Testen jeder möglichen Route beinhaltet , was lächerlich ist, da die Anzahl der Möglichkeiten mit der Fakultät der Anzahl der Städte steigt (selbst kleine Probleme sind zu groß: 50! ist mehr als 10^64).

Seien Sie fair gegenüber einigen Kommentatoren, es gibt einige Methoden, die besser als Brute Force sind, aber keine entgeht der grundlegenden Schwierigkeit von NP-schweren Problemen, bei denen die Zeit zur Lösung eines Problems mit der Größe des Problems zu schnell wächst, als dass irgendein brauchbarer Algorithmus von Nutzen wäre allgemeiner Gebrauch. Goyal , der einige Ergebnisse zu effizienten Algorithmen zusammenfasst, fasst diese Erkenntnis mathematischer zusammen (mein Highlight):

Die kombinatorische Optimierungsversion, dh das Problem, den minimalen Hamilton-Zyklus in einem Diagramm von Städten zu finden, und die Entscheidungsversion, dh das Problem, das Vorhandensein eines Hamilton-Zyklus in einem Diagramm kleiner als ein gegebenes Gewicht zu überprüfen. In der Theorie der Rechenkomplexität gehört die kombinatorische Optimierungsversion zur NP-schweren Problemgruppe, was impliziert, dass es keinen polynomiellen Zeitalgorithmus gibt, nicht einmal um die Korrektheit einer gegebenen Lösung des Problems zu überprüfen, während die Entscheidungsversion zur Klasse von NP gehört vollständige Probleme, was impliziert, dass eine Lösung in polynomieller Zeit überprüft werden kann. Obwohl ohne einen Beweis, dass P≠NP ist, kann nur angenommen werden, dass es keinen effizienten Algorithmus gibt, um irgendeine Version des TSP zu lösen.

In der Praxis gibt es Heuristiken, die schnell sehr gute Ergebnisse liefern können, aber keine kann das absolut beste Ergebnis garantieren .

Wie Andrew P in seiner Antwort betonte, kann gezeigt werden, dass selbst in sehr einfachen Systemen ein gieriger Algorithmus manchmal beim Optimalitätskriterium des Experten falsch ist. Aber Ihr Freund fragt sich vielleicht, ob dieser Unterschied eine Rolle spielt, da er im Vergleich zur bekannten optimalen Antwort oft nicht sehr groß ist.

Hier ist es wichtig, sich darüber im Klaren zu sein, was optimal bedeutet. Experten könnten argumentieren, dass sie einen absoluten Beweis brauchen, dass die Antwort die bestmögliche ist. Nicht-Experten könnten argumentieren, dass "gut genug" in Ordnung ist. Oder sogar, dass die Idee der Optimalität erweitert werden muss, einschließlich der Kosten, um die Antwort zu erhalten (eine Kombination aus Computerleistung und Zeitaufwand).

Wenn Sie der Meinung sind, dass die Kosten zum Finden der Antwort relevant sind (wie es viele praktische Benutzer in der realen Welt sind), dann ist Ihre "optimale" Antwort gut genug, ohne im Expertensinn optimal zu sein. Die meisten TSP-ähnlichen Probleme haben viele leicht zu findende gute Antworten, die innerhalb weniger Prozent des bekannten Expertenoptimums liegen. Gierige Algorithmen finden diese oft in nicht-pathologischen Fällen, obwohl es komplexere Algorithmen gibt, die besser sind.

Seien Sie sich also klar über Ihre Definition von "optimal", und ein Großteil des Arguments könnte verschwinden.

Ich glaube nicht, dass diese Antwort richtig ist. Sie betrachten die Optimierungsversion von TSP, bei der wir eine Karte erhalten und gebeten werden, die minimale Route zu finden. Wir können aber auch die Entscheidungsversion in Betracht ziehen, bei der wir eine Karte und eine Grenze erhalten und gefragt werden, ob es eine Route gibt, deren Länge die Grenze nicht überschreitet. Die Entscheidungsversion ist nicht schwieriger als die Optimierungsversion und wahrscheinlich einfacher. Aber das Entscheidungsproblem ist immer noch NP-schwer und nicht aus dem Grund, den Sie angegeben haben, denn es ist einfach, eine richtige Antwort zu beweisen: Geben Sie einfach die Route an, ermitteln Sie ihre Länge und beobachten Sie, dass sie die Grenze nicht überschreitet.
@MJD Wie würden Sie beweisen, dass die Antwort richtig ist, wenn die Antwort "es gibt keine" lautet?
Wenn ich das wüsste, könnte ich NP = co-NP beweisen.
@MJD Ja, ich habe die Optimalitätsfrage angesprochen. Das liegt aber daran, dass die Existenzfrage bereits eine wesentliche Lockerung des gestellten Problems ist und weil die heuristischen Routen auch das Existenzproblem ansprechen. Der Beweis der Existenz einer Antwort sagt niemandem darüber aus, ob ein Greedy-Algorithmus jemals problematisch ist oder nicht, und spricht nicht die zentrale Frage der Optimalität an.
Die Frage war „Warum ist Handlungsreisender schwierig?“. Ihr Vorschlag ist, dass es aufgrund der kombinatorischen Komplexität schwierig ist, zu beweisen, dass Sie die beste Antwort haben. Aber das Problem des Handlungsreisenden ist auch ohne die kombinatorische Komplexität des Beweises, dass man die beste Antwort hat, schwierig. Ihrer Antwort fehlt also etwas Entscheidendes.
IIRC, jedes TSP-Problem kann als Problem der linearen Programmierung (LP) formuliert werden. Dieses LP-Problem hat ein Dual, das ein weiteres LP-Problem ist. Wenn Sie Lösungen für das ursprüngliche und das duale LP-Problem mit dem gleichen Wert finden können, dann haben Sie eine optimale Lösung gefunden. Die meisten TSP-Algorithmen verwenden diese Dualität und können eine Grenze dafür angeben, wie weit eine Lösung vom Optimum entfernt ist, und wenn diese Grenze Null geworden ist, ist dies ein Beweis dafür, dass die Lösung optimal ist.
@JaapScherphuis Diese Algorithmen sind manchmal schnell, können aber das Problem der Expertenoptimalität nicht lösen . Wenn sie schnell global optimale Lösungen finden würden, wären sie der Beweis dafür, dass P = NP und jemand für eine Fields-Medaille in Frage käme.
@MJD Die kombinatorische Explosion von Routen im TSP ist der Grund, warum es im Allgemeinen schwierig ist. Die Optimalität der Lösung ist eine Teilmenge davon, aber die Ursache ist die gleiche.
Ich habe Ihre Behauptung widerlegt: "Wir kennen keinen effizienten Weg, um zu beweisen, dass eine bestimmte Antwort die beste ist, bei der nicht jede mögliche Route getestet wird, was lächerlich ist, da die Anzahl der Möglichkeiten mit der Fakultät der Anzahl der Städte steigt." Der Beweis der Optimalität ist für viele große TSP-Probleme durchaus machbar und hat nichts damit zu tun, jeden möglichen Weg zu testen. Sie haben sich zum Beispiel auf einer 85.900-City-Strecke als optimal erwiesen. Optimale Lösungen zu finden ist schwierig, der Beweis, dass sie optimal sind, ist oft ein Nebenprodukt des Algorithmus.
@JaapScherphuis Wenn Sie meinen, sich im Sinne von "Diese Route ist die bestmögliche" zu beweisen, muss ich meiner Meinung nach Referenzen sehen. LP-Lösungen können optimale Lösungen des LP-Problems sein, aber das ist eine unvollkommene Darstellung jedes TSP. Sehr gute Lösungen sind oft sehr schnell über einen LP-Algorithmus möglich, wenn Sie einen allgemeinen Beweis von LP für die beste TSP-Lösung haben, die einen Beweis dafür darstellen würde, dass P = NP, und ich glaube, ich hätte einen solchen Durchbruch bemerkt. Oder behaupten Sie, dass sich nur einige Probleme als optimal erweisen lassen?
Hmmm, ich erinnere mich wahrscheinlich nicht richtig. Ich dachte, dass die durch das duale (ganzzahlige) LP gegebene Grenze eng ist, sodass es immer als Beweiszertifikat funktionieren könnte, wenn Sie nur passende optimale Lösungen für beide finden könnten. Aber ich denke, das könnte durchaus falsch sein, dh dass dies nur in einigen glücklichen Fällen passiert und dass in den meisten Fällen immer eine Lücke zwischen ihnen bleibt, sodass kein automatischer Beweis der Optimalität möglich ist. Selbst wenn die Grenze eng wäre, würde dies P = NP meiner Meinung nach überhaupt nicht beweisen, da es immer noch schwierig ist, die optimalen ganzzahligen LP-Lösungen zu finden.
Entschuldigung, aber ich habe diese Antwort aus ähnlichen Gründen wie frühere Kommentatoren abgelehnt. Es scheint, dass Sie sich der Ergebnisse der linearen Programmierung nicht bewusst sind, aber die Details sind etwas subtiler als nur die Feststellung, dass es eine einfache Widerlegung gibt von „Wir kennen keine effiziente Methode, um zu beweisen, dass eine gegebene Antwort die beste ist, die dies nicht tut beinhaltet das Testen jeder möglichen Route, was lächerlich ist, da die Anzahl der Möglichkeiten mit der Fakultät der Anzahl der Städte steigt". Es gibt nämlich einen dynamischen Programmieralgorithmus mit Komplexität Ö ( 2 N poly ( N ) ) , basierend auf der Berücksichtigung, welche Städte besucht wurden.
@A.Rex, wie eine akademische Zusammenfassung sagt : "Angesichts der Tatsache, dass das TSP ein NP-schweres Problem ist, werden häufig heuristische Algorithmen verwendet, um ungefähre Lösungen zu geben, die gut, wenn auch nicht unbedingt optimal sind. Die Algorithmen garantieren keine optimale Lösung, liefert aber nahezu optimale Lösungen in angemessener Rechenzeit". Wenn Sie ein Ergebnis kennen, das zeigt, dass eine LP/heuristische Methode universelle Optimalität beweisen kann, dann müssen wir die Referenz sehen.
@matt_black: Dieser Algorithmus en.wikipedia.org/wiki/Held%E2%80%93Karp_algorithm , der von der Wikipedia-Hauptseite zu TSP verlinkt ist, ist bereits schneller als "jede mögliche Route testen". Wie gesagt, die Diskussion über LP-Methoden ist subtiler, aber auch sie (in Form von Branch-and-Bound) sind auch schneller als "alle möglichen Wege zu testen". Ich schlage vor, mich auf den dynamischen Programmieralgorithmus (Held-Karp) und nicht auf die lineare Programmierung zu konzentrieren, wenn ich diese Behauptung über das "Testen jeder möglichen Route" analysiere.
@A.Rex Mein Punkt war nicht, dass es keinen besseren Algorithmus geben kann, als jede Lösung zu testen (vielleicht hätte ich klarer sein sollen), sondern dass das Nachdenken über kombinatorische Komplexität eine gute Intuition dafür gibt, warum NP-schwere Probleme schwer sind (NP-Härte ist ziemlich grundlegend hier). Held-Karp ist bekanntermaßen weitaus besser als Brute Force, aber auch enorm schlechter als jeder Polynomzeitalgorithmus. Siehe die Zusammenfassung in diesem akademischen Vergleich von 2016 von Algorithmen für TSP-Lösungen ...
@A.Rex Dieses Papier kommt zu dem Schluss: "Bei diesen Komplexitäten steht der Held-Karp-Algorithmus häufig vor einem Speicherproblem, wenn er auf einen TSP mit 30 oder mehr Knoten trifft." was für reale Probleme ziemlich unpraktisch ist. Es könnte viel besser sein als Brute Force, aber es steht immer noch vor der NP-harten Grenze, dass es für echte Probleme äußerst unpraktisch ist, da es in seiner Komplexität weitaus schlechter ist als polynomiale Zeit (und in diesem Fall Raum). Gute Näherungslösungen über verschiedene Heuristiken haben diese grundsätzliche Nachahmung nicht.
Ich habe das Gefühl, dass diese Antwort etwas Großes ignoriert, wenn sie die Bedeutung einer echten optimalen Lösung herunterspielt: Der Grund, warum das Problem zunächst interessant ist, ist, dass eine effiziente Lösung zu einer effizienten Lösung für jedes Problem in NP führen würde. Heuristiken für nahezu optimale Lösungen helfen Ihnen dabei nicht weiter, da die Übersetzung eines schwierigen Problems zwangsläufig auf pathologisch schwere Fälle von TSP abbildet.

Ein analoges Problem ist die Springertour (einen Springer dazu bringen, jedes Feld auf einem Schachbrett genau einmal zu besuchen). In meinem Buch XSLT Programmer's Reference habe ich eine (in XSLT geschriebene) "Lösung" dafür eingefügt, die den intuitiven Ansatz verwendet, immer zum verfügbaren Quadrat mit den wenigsten Ausgängen zu gehen: und ich appellierte an meine Leser, Feedback zu geben, ob der Algorithmus tatsächlich garantiert war erfolgreich sein. Zehn Jahre später antwortete ein Leser mit einem Gegenbeispiel: einem Startquadrat, bei dem der Springer stecken blieb und zurückgehen musste. Es stellte sich heraus, dass es nur ein solches Startquadrat gab (Symmetrien ignorieren).

Ich erwähne dies nur als Beispiel dafür, wie ein intuitiver Algorithmus meistens eine nützliche Lösung liefern kann, obwohl sie falsch ist.

Übrigens legt das Beispiel von @AndrewP nahe, dass die von einem naiven Algorithmus erzeugte Route nur etwas schlechter ist als die optimale Route. Das wird nicht immer der Fall sein. Betrachten Sie 1000 Punkte im Abstand von 1 km um den Umfang eines Kreises und einen Punkt 20 km außerhalb des Kreises. Es gibt eine gute "offensichtliche" Lösung, die darin besteht, den Ausreißer zu besuchen, wenn Sie sich an dem Punkt befinden, der ihm am nächsten ist. aber diese "offensichtliche" Lösung ist weitaus besser als der vereinfachende Greedy-Algorithmus.

Ein Gegenargument gegen die Vorstellung, dass der Greedy-Algorithmus optimal ist, ist zu beachten, dass die Greedy-Lösung je nach Ausgangspunkt unterschiedliche Lösungen erzeugen kann, es jedoch normalerweise nur eine optimale Schleife durch alle Städte gibt, unabhängig vom Ausgangspunkt. Der Greedy-Algorithmus kann mehr als eine Lösung erzeugen, und solange sie Lösungen unterschiedlicher Gesamtlänge darstellen, können nicht alle optimal sein.

Angenommen, Sie haben 4 Städte, A, B, C und X. A und B haben beide X als nächsten Nachbarn, während X C als nächsten Nachbarn hat. Wenn Sie bei A beginnen, enthält der gierige Pfad AXC, während der gierige Pfad BXC enthält, wenn Sie bei B beginnen. Es ist einfach, Pfadentfernungen so zu konstruieren, dass die Gesamtentfernungen dieser Lösungen ungleich sind und sie daher nicht beide optimal sein können. Die Länge des kürzesten Weges ist nur eine Funktion der Reisekostenmatrix, der Startpunkt ist unerheblich. Da die Greedy-Methode mehrere Lösungen mit unterschiedlicher Gesamtlänge erzeugen kann, können wir sicherlich nicht garantieren, dass eine bestimmte Lösung, die sie erzeugt, optimal ist (obwohl dies in einigen Fällen der Fall sein kann).

Hier ist ein Beispiel, das für mich nicht offensichtlich ist. Ihr Ziel ist es, die Hauptstädte aller 50 US-Bundesstaaten so günstig wie möglich zu besuchen. Sie können ein Auto mieten, solange Sie nicht nach Hawaii oder Alaska fahren, und die Kosten sind so hoch, wie Sie bezahlen müssen, um von einer Stadt in die nächste zu gelangen, unter Berücksichtigung von Fahrzeit, Verkehr, Benzinpreisen, Mietpreise, Hotelpreise usw. Sie können auch fliegen, und die Flugkosten hängen davon ab, wie beliebt die Strecke ist und wie weit Sie fliegen. Nehmen wir an, es gibt immer Direktflüge, aber die könnten für ungewöhnliche Strecken sehr teuer werden. Ich habe ehrlich gesagt keine Ahnung, wie Sie ohne Informatik auch nur eine halbwegs anständige Route herausfinden würden.

Warum der Greedy-Algorithmus nicht funktioniert: Nehmen wir an, Sie starten in Maine und die teuersten Ziele sind Hawaii und Alaska (nicht überraschend). Sie würden sich gierig auf dem US-amerikanischen Festland bewegen, bis Sie die unteren 48 erschöpft hätten, dann würden Sie wahrscheinlich nach Alaska fliegen, dann einen weiteren Flug nach Hawaii nehmen und direkt zurück nach Maine fliegen. Meine Vermutung ist, dass Direktflüge zwischen Alaska und Hawaii und zwischen Hawaii und Maine, falls es sie gäbe, verheerend teuer wären, und genau hier haben Sie einen strategischen Fehler gemacht. Es wäre viel besser gewesen, von einer gut angebundenen Westküstenstadt nach Hawaii zu fliegen und ebenso von Hawaii in eine gut angebundene Westküstenstadt zurückzukehren, als eine Alaska->Hawaii->Maine-Reise zu machen.

Ich werde ein wenig von der gestellten Frage abweichen, um zu versuchen, eine intuitivere Erklärung dafür zu liefern, warum TSP schwierig ist. Die Antwort von @matt_block ist ausgezeichnet, richtet sich jedoch an diejenigen mit mehr Erfahrung und / oder formaler Ausbildung in Mathematik, als ich hoffe.

Aber ich suche immer noch nach einem Beispiel, um es meinem Freund zu erklären - kann mir bitte jemand helfen, ein offensichtliches und einfaches Beispiel für das Problem des Handlungsreisenden zu finden, bei dem offensichtlich klar wird, dass die Wahl des kürzesten Weges nicht offensichtlich ist? Jedes einfache Beispiel, an das ich zu denken versuche, ist tendenziell sehr offensichtlich (z. B. Manhattan, Newark, Nashville) - ich möchte meinen Freund nicht mit einem Beispiel von 1000 Städten in den USA überwältigen: nur etwas Einfaches mit 4-5 Städten darin denen nicht sofort klar ist (und vielleicht sogar kontraintuitiv ist), welcher Weg eingeschlagen werden sollte?

Es sind diese Tausend-Städte-Szenarien, die wirklich nach Hause kommen, dass der TSP hart ist.

Menschen sind keine Computer und Computer sind keine Menschen

Menschen können Dinge tun, die Computer noch nicht können. Dazu gehört das heuristische Aussortieren offensichtlich schlechter TSP-Pfade; Wenn Sie beispielsweise versuchen, "den kürzesten Weg zwischen Boston, Chicago und Los Angeles zu finden", ist es einfach, auf eine Karte zu schauen und "zu erkennen, dass der kürzeste Weg in diesem Fall ziemlich offensichtlich ist". Computer können das nicht (zumindest noch nicht). Vielmehr muss der Computer sowohl B->C->LA als auch B->LA->C prüfen, um zu wissen, welches besser ist. Menschen müssen das (glauben, dass sie) das für einen so offensichtlichen Fall nicht tun müssen, daher ist es nicht intuitiv, wie schwer es für einen Computer ist.

Fügen Sie weitere Städte hinzu und es wird deutlicher, dass es schwierig ist, den richtigen Weg zu finden.

Natürlich verlangt TSP einen Rundweg; Es ist durchaus möglich, dass beide Routen die gleichen Kosten haben, wobei die Hin- und Rückfahrt berücksichtigt wird.

Menschen haben Schwierigkeiten mit extremem Wachstum

Es ist einfach, sich eine Karte mit 3, 5 oder 11 Punkten anzusehen und den offensichtlich besten Weg auszuwählen – oder zumindest 2 oder 3 Hauptkandidaten zum Vergleich auszuwählen. Es scheint intuitiv, dass das Hinzufügen eines weiteren Punktes es nicht viel schwieriger machen würde, den optimalen Pfad zu finden. Und das ist es nicht, bis es so ist. Es kommt ein Punkt (wo das von Person zu Person und Karte zu Karte unterschiedlich sein wird), an dem das Hinzufügen eines weiteren Punktes die Anzahl der Kandidaten drastisch erhöht - die Heuristik, die die Person verwendet, um schlechte Pfade auszusortieren (Boston nach LA nach Chicago). angesichts zu vieler Optionen zusammenbrechen.

Bis Sie diesen Zusammenbruch der Heuristik sehen, kann es schwierig sein, sich darüber klar zu werden, wie steil diese Klippe sein kann.

Computer sind wirklich dumm

Computer sind nicht schlau, sie geben nur vor, schlau zu sein, indem sie schummeln. Sie schummeln, indem sie in der Lage sind, grundlegende Mathematik wirklich schnell zu machen , und dann so tun, als ob alles im Universum grundlegende Mathematik wäre (was, um fair zu sein, erstaunlich oft funktioniert).

Meistens ist dieses Schummeln gut genug, um uns Computer als intelligente (oder „magische“) Kästen vorzustellen – ein paar Daten werden rein, und als Ergebnis kommt eine Excel-Datei mit hübschen Diagrammen heraus; In gehen einige andere Daten, heraus kommt ein CGI Gollum.

Aber Computer – selbst die ausgefallenen neuen maschinell lernenden neuronalen Netze – haben keine Ahnung vom Kontext der Dinge, die sie tun sollen. Sie haben keine Ahnung, ob sie die Anzahl der Ticketverkäufe für den neuesten Blockbuster-Film zusammenzählen, die Leihvideos beim letzten Blockbuster zählen oder ein Flugzeug steuern. Sie können einfach addieren, subtrahieren, multiplizieren, dividieren und bitweise Logik ausführen (manchmal eins über das andere emulieren); alles andere baut darauf auf.

Computer können also nicht auf eine Karte schauen (sie haben weder Augen noch eine Vorstellung davon, was eine „Karte“ ist) und die kürzeste Schleife auf sie springen lassen (was ist eine Schleife? was ist „kurz“?). Sie müssen rechnen und jede mögliche Route prüfen, um zu sehen, ob es die kürzeste ist.

Bist du dir wirklich sicher, dass das der kürzeste ist?

Wie @matt_block betonte, besteht ein Teil des Problems mit TSP (und verwandten Problemen) darin, zu 100% sicher zu sein, dass Sie einen kürzesten Weg gefunden haben (möglicherweise gibt es Verbindungen).

Wenn Sie sich nur um die Entfernung kümmern (oder eine andere gute Möglichkeit finden, die Punkte auf etwas Kartenähnliches zu setzen), können Menschen einige offensichtlich schlechte Pläne ausmerzen (wenn Sie versuchen, die Hauptstädte der Bundesstaaten zu treffen, macht es keinen Sinn direkt von Boston nach St. Paul zu fahren), wodurch der Suchraum für "optimal" reduziert wird. Aber: Um zu beweisen, dass es keine kürzeren Routen als "diese" gibt, muss man sich eine ganze Reihe von Varianten der Reihe nach ansehen (es ist sehr wahrscheinlich, dass Boston -> Concord -> Augusta -> Montpelier Teil der optimalen Route ist, aber es ist theoretisch möglich dass es zwischen Boston und Concord keine Straßen gibt, die nicht durch Augusta führen, um diese Metapher zu quälen).

Computer können nicht einmal die offensichtlich schlechten Reisen (Boston nach St. Paul) von der Hand streichen. Sie können aufhören, eine Route in Betracht zu ziehen, wenn ihre aktuelle Länge größer als die kürzeste bekannte Länge ist, aber sie können die Option von Boston nach St. Paul nicht vollständig verwerfen. Daher müssen Computer alle (n – 1)!/2 Routen zumindest teilweise untersuchen.

Die Rucksack-Analogie

Wenn ich mich richtig an meine CS101-Klasse erinnere, ist das Rucksackproblem in TSP umwandelbar. Grundsätzlich: Wie effizient können Sie einen Rucksack packen (was ist die am wenigsten ungenutzte Kapazität des Rucksacks, die Sie bei einer Reihe von Gegenständen haben können).

Intuitiv ist TSP eine Variante des Rucksackproblems: Was ist der kleinste Rucksack, der bei einer gegebenen Menge von Städten einen Rundweg aufnehmen kann, der jede Stadt besucht? ... wobei die Kapazität des Rucksacks "Meilen" oder "Dollar" oder "Stunden" oder sogar "Dollar-Meilen pro Stunde" ist, je nachdem, wofür wir optimieren.

Gierige Algorithmen funktionieren eindeutig nicht. Stellen Sie sich einen Rucksack vor, der 12 Einheiten aufnehmen kann, und eine Reihe von Artikelkosten [ 10, 3, 3, 3, 3 ] - ein gieriger Algorithmus würde den 10-Kosten-Artikel hineinlegen und 2 Kapazität übrig haben, aber es ist klar, dass das Verlassen Wenn Sie den 10-Kosten-Artikel herausnehmen, würden die 4x3-Kosten-Artikel den Rucksack perfekt füllen.

"Anti-gierige" Algorithmen (d. h. zuerst mit den kleinsten Zahlen beginnen) funktionieren ebenfalls eindeutig nicht. Betrachten Sie den gleichen 12-Einheiten-Rucksack und die Artikelkosten von [ 1, 12 ]: Legen Sie den 1-Kosten-Artikel hinein und haben Sie 11 Kapazität übrig, obwohl es einen 12-Kosten-Artikel gibt, der den Rucksack perfekt füllen kann.

Nochmals: Viele Menschen (zu einem Rundungsfehler wahrscheinlich "alle, die diese Antwort wahrscheinlich sehen") können sich diese Artikelkostensätze ansehen und sofort sehen, was die optimale Wahl ist. Aber beginnen Sie, die Kapazität des Rucksacks und die Anzahl der Gegenstände im Set zu erhöhen, und diese Unmittelbarkeit fällt schnell auf „ziemlich schnell“ und dann auf „Ich habe noch 2 Kapazität übrig und sehe keinen offensichtlichen Weg um es zu füllen, aber ich bin mir nicht sicher, ob es keine gibt".

Um ausdrücklich auf TSP zurückzukommen, lautet dieser letzte Fall: "Ich habe die Schaltung auf Kosten von 302 reduziert, und ich sehe keinen offensichtlichen Weg, sie zu reduzieren, aber ich bin mir nicht sicher, ob es keinen gibt".

Wenn Sie eine reale Demonstration der Schwierigkeit bei der Auswahl eines guten Reisepfads wünschen, besorgen Sie sich einen 3D-Drucker und drucken Sie ein komplexes Modell mit vielen getrennten Komponenten in jeder Schicht. Die Software, die es zum Drucken aufteilt (Anmerkung: Sie können Dinge einfach ohne Drucker aufteilen, um die Ergebnisse zu sehen, aber das eigentliche Drucken "macht es real"), muss die Reihenfolge auswählen, um Komponenten zu besuchen und zwischen ihnen zu reisen, und wird es unweigerlich tun Dinge, die "falsch erscheinen" und oft falsch (suboptimal) sind, weil eine optimale Lösung des Problems nicht machbar ist.

Das Problem des Handlungsreisenden ist nicht „schwer“ zu realisieren. Das Problem ist, es ist sehr teuer in der Zählung der Suche.

Um den besten Weg zu finden, müssen Sie jede Stadt von jedem Startpunkt aus besuchen, und diese Anzahl der Besuche wächst sehr schnell auf eine Größe, die Sie nicht erkennen können.

In der Fakultät oder n!

  • Der beste Weg, um 8 Städte zu besuchen, führt zu 40320 Überprüfungen.
  • Für 12 Städte ergibt das mehr als 4 Milliarden Schecks.

In unserer heutigen Zeit sind 4 Milliarden Checks für Rechner mit 4GHz nicht wirklich viel. Vor einigen Jahrzehnten zu der Zeit, als ich zu studieren begann (1992), sind die Computer viel langsamer (~486DX40 40 MHz) als heute (Alder Lake 12900 5,2 GHz) haben wir heute 130-mal mehr MHz, aber die Anzahl der berechenbaren Städte ist um die Hälfte gewachsen. Von 8 auf 12 vielleicht 13 in der gleichen Rechenzeit.

Heute kann es hilfreicher sein, eine Lösung zu finden, die „vorerst gut genug“ ist.

Warum ist das Problem des Handlungsreisenden „schwierig“?
AntwortenHierDatenschutz-Bestimmungen1y, 1v