Wie funktioniert der 3-Opt-Algorithmus für TSP?

8

Ich verstehe, dass die 3-Opt-Heuristik zur Lösung des Problems des Handlungsreisenden darin besteht, drei Kanten aus einem Diagramm zu entfernen und drei weitere hinzuzufügen, um die Tour erneut abzuschließen. Ich habe jedoch viele Artikel gesehen, in denen erwähnt wird, dass es beim Entfernen von drei Kanten nur noch zwei Möglichkeiten gibt, die Tour neu zu kombinieren - dies macht für mich keinen Sinn.

Zum Beispiel habe ich ein Papier [1] gefunden, in dem steht:

Der 3-Opt-Algorithmus funktioniert auf ähnliche Weise, aber anstatt zwei Kanten zu entfernen, entfernen wir drei. Dies bedeutet, dass wir zwei Möglichkeiten haben, die drei Pfade wieder zu einer gültigen Tour1 zu verbinden (Abbildung 2 und Abbildung 3). Eine 3-Opt-Bewegung kann tatsächlich als zwei oder drei 2-Opt-Bewegungen angesehen werden.

Ich zähle jedoch 3 verschiedene Möglichkeiten, um die Tour wieder zu verbinden. Was fehlt mir hier?

Kann mich jemand nach Möglichkeit mit einem Algorithmus für 3-opt verknüpfen? Ich versuche nur, es zu verstehen, aber ich habe noch keine klaren Algorithmen gefunden: Alle Ressourcen, die ich finde, sagen einfach "drei Kanten entfernen, sie wieder verbinden". Das ist es, was irgendwie vage ist.

Hier sind die 3 Touren, die mir nach dem Entfernen von drei Kanten als 3-Opt-Moves erscheinen.

Geben Sie hier die Bildbeschreibung ein


  1. Heuristik für das Problem des Handlungsreisenden von C. Nilsson
u3l
quelle
2
Das von Ihnen verlinkte Papier ist in einem sehr informellen Stil verfasst und enthält im ersten Satz eine nicht standardmäßige Definition von TSP. es scheint auch nirgendwo veröffentlicht worden zu sein. Das hat natürlich keinen Einfluss auf die Gültigkeit Ihrer Frage, aber es gibt wahrscheinlich bessere Erklärungen für 3-OPT als die, die Sie gefunden haben.
David Richerby
Artikel auf dieser Ebene gehen wahrscheinlich davon aus, dass interessierte Leser keine Probleme haben, eine mehr oder weniger eindeutige Beschreibung in Code zu übersetzen. Das ist bei (T) CS üblich. Wenn dies ein Hindernis für Sie ist, sollten Sie zuerst mehr grundlegende Dinge lesen, um mehr Training zu erhalten.
Raphael
Als Gymnasiast finde ich nichts von alledem grundlegend, haha. Wie auch immer, ich bin mir ziemlich sicher, dass es mehr als zwei Möglichkeiten gibt (3 um genau zu sein), um die Tour wieder zu verbinden, so dass der Zug nicht mit einem Zwei-Opt-Zug identisch ist ... also habe ich mich gefragt, warum in diesem Artikel dort angegeben wird sind nur zwei. Ich habe nach anderen Artikeln gesucht, um nach einem endgültigen Algorithmus zu suchen, den ich leicht implementieren kann, aber keinen gefunden habe. Deshalb habe ich versucht, ihn (in Java) basierend auf dem, was ich weiß, zu implementieren, und er hat nicht wirklich gut funktioniert, da ich ' Ich bin immer noch verwirrt darüber, wie viele verschiedene Möglichkeiten es gibt, die Verbindung wiederherzustellen.
U3l
1
Für 2d euklidischen TSP kann eine Tour mit sich überschneidenden Linien immer zu einer anderen Tour ohne Schnittlinien und einer kürzeren Tour führen, dh nur der von Ihnen aufgeführte Fall Nr. 1 (nach der anfänglichen Konfiguration) kann berücksichtigt werden. Vielleicht werden einige dieser Informationen in den von Ihnen zitierten Aufzeichnungen weggelassen. dh sie berücksichtigen / schließen die garantierten nicht optimalen sich überschneidenden Fälle nicht aus. ps Es wäre hilfreich / klarer, wenn Sie jedes Diagramm beschriften würden. nimm es du meinst: initial, tour1, tour2, tour3.
vzn
Versuchen Sie, bei Wikipedia 3opt Eintrag für Refs zu beginnen. Einige sind Jahrzehnte alt, aber elektronische Kopien sind verfügbar.
vzn

Antworten:

6

Sie haben die Fußnote verpasst - diese Methoden beinhalten "nicht, dass die Verbindungen mit einem einzelnen 2-Opt-Zug identisch sind". Tatsächlich gibt es in nur zwei Permutationen ohne Fixpunkte (auch als Störungen bezeichnet ), nämlich und . Im Allgemeinen reicht es für eine opt-Bewegung aus, Permutationen ohne feste Punkte zu berücksichtigen, da diejenigen mit festen Punkten -Züge sind.S3(123)(132)kt(kt)

Der Algorithmus für die lokale Suche mit opt ist wie folgt. Beginnen Sie mit einer ersten Lösung, beispielsweise der von Christofides 'Algorithmus. Versuchen Sie wiederholt, es zu verbessern, indem Sie eine Option ausführen: Wählen Sie Kanten aus und verbinden Sie sie auf andere Weise wieder (diesmal ist es in Ordnung, wenn die Verschiebung auch eine Bewegung für einige ), was zu einer kürzeren Tour führt .kkk<k

Die Art und Weise, wie dies implementiert wird, besteht darin, alle Sätze von Kanten und alle Arten des erneuten Verbindens der Kanten, möglicherweise in einer intelligenten Reihenfolge, zu durchlaufen und den Längenunterschied zu berechnen (es besteht lediglich keine Notwendigkeit, die Länge der gesamten Tour neu zu berechnen die unterschiedliche Länge, die anstelle von ); Wenn eine Verbesserung festgestellt wird, wechseln wir und wiederholen von Anfang an. Wir machen so weiter, bis wir stecken bleiben.kO(k)O(n)

Eine andere Variante besteht darin, immer alle Möglichkeiten auszuprobieren und die zu verwenden, die zur besten Verbesserung führt. Es gibt auch andere Varianten, die Sie wahrscheinlich in der Literatur finden können.

Yuval Filmus
quelle
1
Okay ... Ich habe vermisst, dass einige dieser Permutationen jetzt nur noch zwei Opt-Moves sind. Ich zähle jedoch immer noch 3 verschiedene Permutationen, mit Ausnahme derjenigen vor dem Zug, die 0 Fixpunkte haben. (Ich werde in ein paar Minuten ein Bild in meinem Beitrag bearbeiten)
u3l
0

Nehmen wir an, wir haben 3 Punkte A, B und C. Zuerst tauschen wir (A, B) und dann können wir nur (B, C) oder (A, C) tauschen. Auf diese Weise haben wir nur zwei verschiedene Möglichkeiten.

matejs
quelle
1
Dies bedarf definitiv weiterer Erklärungen.
David Richerby
Nun ... vielleicht irre ich mich. Korrigieren Sie mich bitte. 2-opt: Wir haben ABCD-Städte. Wir tauschen zwei und wir bekommen ACBD. Nur zwei Möglichkeiten, original und eine neue - ABCD und ACBD. 3-opt: ABCD-Städte. Wir tauschen (1,2) und bekommen BACD. Wir tauschen die dritte Stadt entweder mit der ersten oder der zweiten aus und erhalten BCAD - Swap (2,3) oder CABD durch Swap (1,3). Drei Möglichkeiten, original und zwei neu - ABCD, BACD und BCAD. Was ist mit k-opt (4,5,6 ...)?
Matejs
0

Ich konnte 4 3-Opt-Züge finden (die nicht 2-Opt sind): Geben Sie hier die Bildbeschreibung ein Wenn ich der Sechseck-Tour eine Nummerierung von 123456 (beginnend am oberen linken Scheitelpunkt) geben würde, hätten die anderen Touren Nummern von 125634, 124365, 126534 und 125643 , die eine Teilmenge der Störung von 12 sind [3456] (wobei 3456 gestört wird).

kritinsai
quelle
3
Willkommen auf der Website, aber ich bin mir nicht sicher, wie dies die Frage beantwortet. Auf Stack Exchange-Websites suchen wir nach der Antwort auf die Frage oben auf der Seite, nicht nach "Hier sind einige verwandte Informationen".
David Richerby