Matroids Matheplanet Forum Index
Moderiert von matroid
Kombinatorik & Graphentheorie » Graphentheorie » TSP - Christofides ... Schritt 5 unklar. Muss hier optimiert werden?
Autor
Kein bestimmter Bereich TSP - Christofides ... Schritt 5 unklar. Muss hier optimiert werden?
CSharper
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.11.2021
Mitteilungen: 8
  Themenstart: 2021-11-20

Ich hab mir die letzten Tage mal einen Spaß gemacht, programmiert und das TSP mit verschiedenen Algorithmen lösen lassen. Zuletzt hab ich mich über den Christofides-Algorithmus hergemacht (Puh, das Minimale Perfekte Matching hat es aber schon in sich :) Gebaut hab ich: 1. Minimalen Spannbaum finden 2. Minimales Perfektes Matching finden 3. Spannbaum und Matching vereinigen 4. Eine Eulertour darin suchen 5. Eulertour ablaufen und wenn man einen Knoten zum zweiten mal besucht eine Abkürzungen einfügen um diesen zu umgehen. (So entsteht Hamiltonkreis) Funktioniert soweit so gut. Jetzt aber meine Frage: Wie genau muss eigentlich Schritt 5 gemacht werden? Mein Problem: Einfach die Tour ablaufen und doppelte Knoten überspringen und eine Abkürzungskante einfügen ist zwar einfach und nett - aber nicht deterministisch! Muss man hier nicht ALLE Möglichkeiten wie man den Graph durch Abkürzungen zum Hamiltonkreis machen kann prüfen, und dann den besten wählen? Leider fällt es mir gerade sehr schwer abzuschätzen, welche Komplexität das hat, weil ich nicht sehe, wie viele Abkürzungsmöglichkeiten so ein Spannbaum+Matching-Graph besitzt. Und wenn man die "beste" Abkürzungsmöglichkeit nimmt, welche ist das dann? Die Kürzeste, weil man dann das beste Ergebnis hat? Oder die Längste, weil man dann mit der Länge des erhaltenen Hamiltonkreise * 2/3 die höchste Untergrenze für die unbekannte, optimale Tour bestimmen kann? (Gilt bei einer "nicht-optimalen" Abkürzung überhaupt die 1,5-Gütegarantie?) Kennt sich jemand aus? Vielen Dank vorab! CS


   Profil
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1996
  Beitrag No.1, eingetragen 2021-11-20

Hallo CSharper! Willkommen auf dem Matheplaneten! Eine Antwort auf Deine Frage habe ich im Moment nicht, aber: Ich habe vor einiger Zeit mal einen Ameisenalgorithmus auf ein TSP mit 81 und eines mit 96 Städten gestartet. Siehe: https://www.matheplanet.de/matheplanet/nuke/html/viewtopic.php?rd2&topic=256064&start=0#p1861257 und https://www.matheplanet.de/matheplanet/nuke/html/article.php?sid=1859 Auch habe ich lokale Suche für das TSP benutzt. Was ich noch machen möchte ist ein 3Opt korrekt zu implementieren. (Dies ist eine Nachoptimierung einer schon guten Lösung. Es werden 3 Kanten weggenommen und anders verbunden.) Viele Grüße Ronald


   Profil
CSharper
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.11.2021
Mitteilungen: 8
  Beitrag No.2, vom Themenstarter, eingetragen 2021-11-20

\quoteon(2021-11-20 19:43 - Delastelle in Beitrag No. 1) Auch habe ich lokale Suche für das TSP benutzt. Was ich noch machen möchte ist ein 3Opt korrekt zu implementieren. \quoteoff Ein "3-Opt" hab ich mit brute-force implementiert. Es werden einfach alle Tauschmöglichkeiten durchgeführt. Geht auf nem alte PC bei nem Kreis mit 500 Knoten in 20 sec. Arbeitet ca. so: Solange der Kreis besser wird Prüfe für alle Kombinationen von 3 Kanten im Kreis Entferne die 3 Kanten aus dem Kreis und prüfe, ob eine der 7 Möglichkeiten den Kreis wieder zu flicken besser ist Liefert sehr gute Ergebnisse. Muss ggf. ein paar mal wiederholt werden.


   Profil
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1996
  Beitrag No.3, eingetragen 2021-11-20

Ich hatte 3 Opt erst falsch und unvollständig im Programm. Ich hatte 3 Knoten verschieben wollen - naja. Nochmal zu Deiner Frage: Vielleicht findest Du einen Beispielgrafen mit dem Du eine Lösung Deiner Frage findest. Edit: was auch ganz nett ist: die Eröffnungsheuristiken. Sie liefern in kurzer Zeit Rundreisen ordentlicher Güte.


   Profil
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1996
  Beitrag No.4, eingetragen 2021-11-22

Hallo, noch eine Ergänzung. Wenn Du mehrere Verfahren mit bekannten Rechenzeiten hast, kannst Du diese z.B. in einen Matlab(Octave) loglog Graphen darstellen. Für ein Beispiel kann man so die Güte (Abstand in Prozent von der Optimallösung) gegen die Rechenzeit auftragen. Da sieht man dann welche Verfahren gut oder weniger gut sind. Viele Grüße Ronald


   Profil
philippw
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 01.06.2005
Mitteilungen: 1183
Wohnort: Hoyerswerda
  Beitrag No.5, eingetragen 2021-11-22

\quoteon(2021-11-20 17:09 - CSharper im Themenstart) 5. Eulertour ablaufen und wenn man einen Knoten zum zweiten mal besucht eine Abkürzungen einfügen um diesen zu umgehen. (So entsteht Hamiltonkreis) Funktioniert soweit so gut. Jetzt aber meine Frage: Wie genau muss eigentlich Schritt 5 gemacht werden? Mein Problem: Einfach die Tour ablaufen und doppelte Knoten überspringen und eine Abkürzungskante einfügen ist zwar einfach und nett - aber nicht deterministisch! Muss man hier nicht ALLE Möglichkeiten wie man den Graph durch Abkürzungen zum Hamiltonkreis machen kann prüfen, und dann den besten wählen? \quoteoff Ist ein bisschen her, dass ich mich damit beschäftigt habe, aber ich habe den Algorithmus wieder erkannt :-) . Die Antwort ist wahrscheinlich, dass es egal ist, wie du den 5. Schritt implementierst. Genauso wie es egal ist, welchen minimalen Spannbaum du berechnest oder welche Eulertour du findest. Diese Schritte sind an sich auch nicht "deterministisch", in dem Sinne dass verschiedene Implementierungen unterschiedliche Ergebnisse erreichen können. (Eine konkrete Implementierung wird meistens deterministisch sein, muss sie aber auch nicht.) Und ja, deine Idee, alle Abkürzungen anzuschauen und die besten auszuwählen, würde auch funktionieren, aber wahrscheinlich keine weitere theoretische Garantie bzgl. Qualität der Lösung liefern. Der ganze Algorithmus liefert halt eine Approximation, die man durch weitere Berechnungen eventuell verbessern kann. Edit: Ach übrigens, willkommen auf dem Matheplaneten :-)


   Profil
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1996
  Beitrag No.6, eingetragen 2021-11-24

Eine Frage zu 3 Opt an einem 10 Städte Beispiel: TSP 10 Städte Permutation 1 2 3 4 5 6 7 8 9 10 Kanten 1-2, 4-5, 8-9 aktuell in 3 Opt neu zu testen: 1-4 2-5 8-9 (2er) 1-4 2-8 5-9 1-4 2-9 5-8 1-5 2-4 8-9 (2er) 1-5 2-8 4-9 1-5 2-9 4-5 (2er) 1-8 2-4 5-9 1-8 2-5 8-9 (2er) 1-8 2-9 4-5 (2er) 1-9 2-4 5-8 1-9 2-5 4-8 1-9 2-8 4-5 (2er) Das sind 6 3er. Viele Grüße Ronald


   Profil
CSharper
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.11.2021
Mitteilungen: 8
  Beitrag No.7, vom Themenstarter, eingetragen 2021-11-24

\quoteon(2021-11-22 16:24 - philippw in Beitrag No. 5) Ist ein bisschen her, dass ich mich damit beschäftigt habe, aber ich habe den Algorithmus wieder erkannt :-) . Die Antwort ist wahrscheinlich, dass es egal ist, wie du den 5. Schritt implementierst. Genauso wie es egal ist, welchen minimalen Spannbaum du berechnest oder welche Eulertour du findest. Diese Schritte sind an sich auch nicht "deterministisch", in dem Sinne dass verschiedene Implementierungen unterschiedliche Ergebnisse erreichen können. (Eine konkrete Implementierung wird meistens deterministisch sein, muss sie aber auch nicht.) Und ja, deine Idee, alle Abkürzungen anzuschauen und die besten auszuwählen, würde auch funktionieren, aber wahrscheinlich keine weitere theoretische Garantie bzgl. Qualität der Lösung liefern. Der ganze Algorithmus liefert halt eine Approximation, die man durch weitere Berechnungen eventuell verbessern kann. Edit: Ach übrigens, willkommen auf dem Matheplaneten :-) \quoteoff Ok, danke für die Informationen. Das bedeutet also: In dem Schritt, wo ich aus der Eulertour durch Abkürzen einen Hamiltonkreis mache, kann ich die Abkürzungen wählen, die AM WENIGSTEN abkürzen. Also bekomm ich dann einen langen Kreis als Ergebnis. Trotzdem hat dieser lange Kreis noch eine Gütegarantie von 1,5, d.h. ich komme so zu einer sehr hohen Mindestlänge der unbekannten, optimalen Lösung. Sehr gut, das will ich haben... die Abschätzung ist damit besser :) Korrekt?


   Profil
CSharper
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.11.2021
Mitteilungen: 8
  Beitrag No.8, vom Themenstarter, eingetragen 2021-11-24

\quoteon(2021-11-24 15:15 - Delastelle in Beitrag No. 6) Eine Frage zu 3 Opt an einem 10 Städte Beispiel: TSP 10 Städte Permutation 1 2 3 4 5 6 7 8 9 10 Kanten 1-2, 4-5, 8-9 aktuell in 3 Opt neu zu testen: 1-4 2-5 8-9 (2er) 1-4 2-8 5-9 1-4 2-9 5-8 1-5 2-4 8-9 (2er) 1-5 2-8 4-9 1-5 2-9 4-5 (2er) 1-8 2-4 5-9 1-8 2-5 8-9 (2er) 1-8 2-9 4-5 (2er) 1-9 2-4 5-8 1-9 2-5 4-8 1-9 2-8 4-5 (2er) Das sind 6 3er. Viele Grüße Ronald \quoteoff Nein, wenn ich deine Notation richtig verstehe sind da einige Fehler drinnen... Du erzeugst oft losgelöste Kreise vom Hauptkreis. Wenn Du die Kanten 1-2, 4-5 und 8-9 aus dem Kreis entfernst, dann gibt es genau diese 8 Möglichkeiten, in die 3 Lücken neue Kanten einzusetzten, so dass wieder EIN EINZIGER neuer Kreis entsteht: 1-2 4-5 8-9 (das musst du nicht testen, das ist das Original) 1-4 2-5 8-9 1-4 2-8 5-9 1-2 4-8 5-9 1-5 8-2 4-9 1-5 8-4 2-9 1-8 5-4 2-9 1-8 5-2 4-9 Von den 8 ist eines die Ausgangssituation. Die anderen 7 musst Du testen. Kann man auch so lesen: Du zerschneidest den Kreis in: Start - Teilstück A - Teilstück B - Ende Es gibt 8 Möglichkeiten A und B wieder einzusetzten (R bedeutet: Revers/Rückwärts): A B AR B AR BR A BR B A B AR BR AR BR A Viele Grüße, CS


   Profil
philippw
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 01.06.2005
Mitteilungen: 1183
Wohnort: Hoyerswerda
  Beitrag No.9, eingetragen 2021-11-24

\quoteon(2021-11-24 15:20 - CSharper in Beitrag No. 7) In dem Schritt, wo ich aus der Eulertour durch Abkürzen einen Hamiltonkreis mache, kann ich die Abkürzungen wählen, die AM WENIGSTEN abkürzen. Also bekomm ich dann einen langen Kreis als Ergebnis. Trotzdem hat dieser lange Kreis noch eine Gütegarantie von 1,5, d.h. ich komme so zu einer sehr hohen Mindestlänge der unbekannten, optimalen Lösung. Sehr gut, das will ich haben... die Abschätzung ist damit besser :) Korrekt? \quoteoff Ja, das stimmt so. Wenn ich mich nicht irre geht es aber noch besser: Nimm einfach die Länge der Eulertour vor dem Abkürzen, die ist auch maximal um einen Faktor von 1,5 am Optimum. (Wenn ich den Beweis von https://de.wikipedia.org/wiki/Algorithmus_von_Christofides richtig verstanden habe.)


   Profil
CSharper
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.11.2021
Mitteilungen: 8
  Beitrag No.10, vom Themenstarter, eingetragen 2021-11-24

\quoteon(2021-11-24 18:03 - philippw in Beitrag No. 9) Ja, das stimmt so. Wenn ich mich nicht irre geht es aber noch besser: Nimm einfach die Länge der Eulertour vor dem Abkürzen, die ist auch maximal um einen Faktor von 1,5 am Optimum. (Wenn ich den Beweis von https://de.wikipedia.org/wiki/Algorithmus_von_Christofides richtig verstanden habe.) \quoteoff Hey, coole Sache. Stimmt das würde ich da auch so herauslesen! Ich hab das gleich mal probiert. Je nach Tour bringt das bei mir noch mal eine 3-5% höhere Mindesttourgröße 😃 Danke CS


   Profil
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1996
  Beitrag No.11, eingetragen 2021-11-24

Hallo CSharper! Danke für die Hinweise zu 3 Opt! Zur Qualität von Lösungen bei Startheuristiken. In meinem oben genannten Artikel zu einem Ameisenalgorithmus für TSP war die Qualität der Lösungen für die 96 französischen Städte so: opt = 6748 Heuristik 1: "Nearest Insertion" ff = 7295 -> +8.1 % über Optimum Heuristik 2: "Random Insertion" ff = ca. 6955 -> 3.1 % über Optimum Heuristik 3: "Farthest Insertion" ff = 6928 -> 2.7 % über Optimum Viele Grüße Ronald


   Profil
CSharper
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.11.2021
Mitteilungen: 8
  Beitrag No.12, vom Themenstarter, eingetragen 2021-11-24

\quoteon(2021-11-24 22:38 - Delastelle in Beitrag No. 11) Danke für die Hinweise zu 3 Opt! \quoteoff Gerne 👍 \quoteon(2021-11-24 22:38 - Delastelle in Beitrag No. 11) Zur Qualität von Lösungen bei Startheuristiken. In meinem oben genannten Artikel zu einem Ameisenalgorithmus für TSP war die Qualität der Lösungen für die 96 französischen Städte so: opt = 6748 Heuristik 1: "Nearest Insertion" ff = 7295 -> +8.1 % über Optimum Heuristik 2: "Random Insertion" ff = ca. 6955 -> 3.1 % über Optimum Heuristik 3: "Farthest Insertion" ff = 6928 -> 2.7 % über Optimum \quoteoff Interessant! Was bedeutet "ff"? Und noch interessanter: wie kommst Du bei 96 Städten zum Optimum? Ich hab aus Spaß mal bei mir 96 deutsche Städte laufen lassen. Da kommt das raus: (Durchläufe auf je 20 verschiedenen Sets von 96 Städten, Abweichung zum besten Ergebnis pro Set) https://matheplanet.com/matheplanet/nuke/html/uploads/b/55147_Screenshot_-_24.11.2021_23_16_04.png


   Profil
Kitaktus
Senior Letzter Besuch: im letzten Monat
Dabei seit: 11.09.2008
Mitteilungen: 6954
Wohnort: Niedersachsen
  Beitrag No.13, eingetragen 2021-11-25

Der Christofides-Algorithmus hat im Wesentlichen eine theoretische Bedeutung. Es ist ein Algorithmus mit polynomieller Laufzeit, der Lösungen produziert, die maximal 1,5 mal so lang sind, wie die optimale Lösung. Dabei war dieser Faktor 1,5 lange Zeit der beste Faktor, den man kannte. Ob man in den Schritten 4 und 5 irgendeine Auswahl trifft, oder von mehreren Möglichkeiten die beste nimmt, ist für den Faktor 1,5 unerheblich. Wenn ich Dich richtig verstanden habe, möchtest Du aus der Christofides-Lösung eine möglichst hohe untere Schranke für die optimale Lösung ablesen, richtig? Aber diese untere Schranke wäre doch gerade das Gewicht des MST. Ich muss also _nicht_ eine möglichst lange "Christofides"-Tour nehmen und deren Länge durch 1,5 teilen. Falls Deine Intension ist, eine möglichst hohe untere Schranke zu finden, dann probiere mal folgendes: Das Gewicht des MST ist eine untere Schranke für die kürzeste Rundreise. Angenommen der MST ist eindeutig und es gibt im MST einen Knoten v mit drei (oder mehr) Nachbarn. Wenn wir alle Kantenlängen von Kanten mit dem Eckpunkt v um d>0 verlängern, dann nimmt das Gewicht des MST um 3d (oder mehr) zu, die Länge der kürzesten Rundreise wächst aber nur um 2d. Der Abstand zwischen MST und Rundreise wird also kleiner. Mit anderen Worten, wir bekommen eine bessere untere Schranke. Das ganze geht natürlich nur so lange, bis sich ein neuer MST ergibt. Hat der Knoten v immer noch drei oder mehr Nachbarn, dann kann man die v-Kanten weiter verlängern. Rein praktisch muss man daher gar nicht so genau wissen, wie viel Verlängerung verkraftbar ist, ehe sich der MST ändert. Ich kann mit einem Offset d starten. Hat der Knoten v danach im MST nur noch einen Nachbarn, dann war d zu groß gewählt. Hat v im neuen MST drei oder mehr Nachbarn, dann kann man d wahrscheinlich noch größer machen. Das gleiche Verfahren kann man mit anderen Knoten mit drei oder mehr Nachbarn im MST machen und verbessert dabei kontinuierlich die untere Schranke. Man endet dann typischerweise bei einem MST des modifizierten Problems, bei dem alle Knoten bis auf zwei genau zwei genau zwei Nachbarn haben. Ich kann leider kein Schlagwort benennen, unter dem man diese Technik nachlesen kann.


   Profil
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1996
  Beitrag No.14, eingetragen 2021-11-25

ff meint Zielfunktionswert. Ich nehme an, dass die Optimallösung für 96 französische Städte 6748 ist. Sowohl ich als auch andere Leute haben bisher keine bessere Lösung gefunden. Ich habe meist mit 2 Problemen gerechnet: (a) eine Rundreise durch die 81 größten Städte (Nr 1 ist Berlin) opt = 3785 (b) eine Rundreise durch die Hauptstädte der 96 französischen Festlandsdepartements (ohne Überseegebiete) Problem (a) ist nicht so schwer, da extrem viele große deutsche Städte im Ruhrgebiet liegen, da muss man für ca.15 Städte nur eine gute Route durchs Ruhrgebiet finden. Das Problem ist vielleicht ähnlich schwer wie wenn man 65 Städte hat die eher gleichverteilt auf der Karte sind. Ich habe für (a) und (b) jeweils pro Ort 2 Koordinaten gespeichert: die geografische Länge und die geografische Breite. Mittels einer Formel die ich bei Matlab fand, habe ich dann aus diesen Angaben eine näherungsweise Distanzmatrix berechnet mit d(x,y) = d(y,x). Die Distanzen zu (a) und (b) werden wie folgt berechnet: \sourceon Fortran ort1(1) = lage(i,1) ort1(2) = lage(i,2) ort2(1) = lage(j,1) ort2(2) = lage(j,2) phi1 = ort1(1)*pi/180 tht1 = ort1(2)*pi/180+pi/4 phi2 = ort2(1)*pi/180 tht2 = ort2(2)*pi/180+pi/4 angularDistCos=sin(phi1)*sin(phi2)+cos(phi1)*cos(phi2)*cos(tht1-tht2) angularDist=acos(angularDistCos)*180.0d0/pi Erdradius=6350.0d0 distanz=(angularDist*pi/180.0d0)*Erdradius dist(i,j) = floor(distanz+0.5); dist(j,i) = dist(i,j) \sourceoff Die Koordinaten der 96 französischen Städte sind: \showon 96 46.2000 5.2330 49.5660 3.6160 46.5660 3.3330 44.1000 6.2330 44.5660 6.0830 43.7000 7.2660 44.7330 4.6000 49.7660 4.7160 42.9660 1.6000 48.3000 4.0830 43.2160 2.3500 44.3500 2.5660 43.3000 5.3830 49.1830 -0.3660 44.9330 2.4330 45.6500 0.1660 46.1660 -1.1500 47.0830 2.4000 45.2660 1.7660 41.9330 8.7330 47.3160 5.0500 48.5160 -2.7660 46.1660 1.8660 45.1830 0.7160 47.2500 6.0160 44.9330 4.8830 49.0160 1.1500 48.4500 1.4830 48.0000 -4.1000 43.8330 4.3660 43.6000 1.4500 43.6500 0.5830 44.8330 -0.5830 43.6160 3.8830 48.1160 -1.6830 46.8160 1.6830 47.4000 0.6830 45.1830 5.7330 46.6660 5.5500 43.8830 -0.5000 47.6000 1.3330 45.4330 4.3830 45.0500 3.8830 47.2160 -1.5500 47.9000 1.9000 44.4500 1.4330 44.2000 0.6160 44.5160 3.5000 47.4660 -0.5500 49.1160 -1.1000 48.9500 4.3660 48.1160 5.1330 48.0660 -0.7660 48.7000 6.1830 48.7660 5.1660 47.6500 -2.7660 49.1160 6.1830 47.0000 3.1500 50.6330 3.0500 49.4330 2.0830 48.4330 0.1000 50.2830 2.7830 45.7830 3.0830 43.3000 -0.3660 43.2330 0.0660 42.7000 2.9000 48.5830 7.7500 48.0830 7.3500 45.7660 4.8330 47.6160 6.1500 46.3000 4.8330 48.0000 0.2000 45.5660 5.9160 45.9000 6.1330 48.8500 2.3500 49.4500 1.1000 48.5330 2.6660 48.8000 2.1330 46.3330 -0.4660 49.9000 2.3000 43.9330 2.1500 44.0160 1.3500 43.1330 5.9330 43.9500 4.8000 46.6660 -1.4330 46.5830 0.3330 45.8330 1.2660 48.1660 6.4500 47.8000 3.5660 47.6330 6.8500 48.6330 2.4500 48.8830 2.2000 48.9160 2.4330 48.7830 2.4660 49.0330 2.0660 42.7000 9.4500 \showoff Wie finde ich ein Optimum? Ich habe das Optimum für (a) und (b) mittels eines ähnlichen Algorithmus wie lokale Suche und Ameisenalgortihmen gefunden. Jeweils tausende Läufe der Algortihmen. Ich kann nicht beweisen, dass die Lösungen optimal sind. Verwendet habe ich meist Fortran. Aktuell habe ich auch mal mit Java beim TSP gearbeitet. Für bis zu etwa n = 17 oder etwas mehr habe ich auch Branch&Bound/Backtracking verwendet. Dies liefert beweisbar beste Lösungen.


   Profil
CSharper
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.11.2021
Mitteilungen: 8
  Beitrag No.15, vom Themenstarter, eingetragen 2021-11-26

\quoteon(2021-11-25 03:14 - Delastelle in Beitrag No. 14) Ich nehme an, dass die Optimallösung für 96 französische Städte 6748 ist. Sowohl ich als auch andere Leute haben bisher keine bessere Lösung gefunden. (b) eine Rundreise durch die Hauptstädte der 96 französischen Festlandsdepartements (ohne Überseegebiete) Die Koordinaten der 96 französischen Städte sind: \showon 96 46.2000 5.2330 49.5660 3.6160 \quoteoff Ha, danke für die nette Anregung! Ich hab gleich mal dieFrankreich-96-Beispieldaten bei mir laufen lassen! Sehr interessante Konstellation. Es gibt sehr viel verschiedeneLösungen, die nahe an 6748 sind. Meistens finde ich diese (6752) mit einem All-Nearest-Neighbor + 3-Opt: https://matheplanet.com/matheplanet/nuke/html/uploads/b/55147_Screenshot_-_26.11.2021_00_33_04.png Aber ich hab auch 6748 gefunden mit MST-Heuristik + 2-Opt: https://matheplanet.com/matheplanet/nuke/html/uploads/b/55147_Screenshot_-_26.11.2021_00_32_35.png Beim Leisen von deinem Link ist mir aufgefallen, das Du Farthest-Insertation mit allen 96-Knoten je einmal als Startknoten machst - hab ich das richtig Verstanden? Danke & viele Grüße, CS


   Profil
CSharper
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.11.2021
Mitteilungen: 8
  Beitrag No.16, vom Themenstarter, eingetragen 2021-11-26

\quoteon(2021-11-25 01:11 - Kitaktus in Beitrag No. 13) Falls Deine Intension ist, eine möglichst hohe untere Schranke zu finden, dann probiere mal folgendes: Das Gewicht des MST ist eine untere Schranke für die kürzeste Rundreise. Angenommen der MST ist eindeutig und es gibt im MST einen Knoten v mit drei (oder mehr) Nachbarn. Wenn wir alle Kantenlängen von Kanten mit dem Eckpunkt v um d>0 verlängern, ... \quoteoff Das hört sich sehr interessant an! Danke, dass muss ich bei Gelegenheit mal testen... CS


   Profil
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1996
  Beitrag No.17, eingetragen 2021-11-26

Hallo, Oft habe ich einfach etwas probiert, was ich in der Literatur gefunden habe. Auch z.B. Wikipedia Artikel. Bei den 3 Startheuristiken wird die besten aus 96 Routen gewählt. Ein Start erfolgt in jeder Stadt einmal. Ob dies in der Literatur so gewünscht ist kann ich nicht sagen! Was mir persönlich fehlt ist ein gutes Buch zum Thema. Zu guten Heuristiken und gelösten Beispielen. Die von mir verwendeten Algorithmen arbeiten "gut". Die besten Algorithmen zum Thema weltweit arbeiten aber "sehr gut" - sie lösen auch größere Probleme noch ordentlich. https://www.matheplanet.de/matheplanet/nuke/html/uploads/b/15578_L1010772_kleiner_33Prozent.jpg Es gibt auch viele Beispielprobleme die man lösen kann. So gab es mal ein Bohrlochproblem. Also Löcher in eine Platine bohren. Dies sind 442 Löcher. (siehe Bild) https://www.matheplanet.de/matheplanet/nuke/html/uploads/b/15578_L1010771_kleiner_25Prozent.jpg Ein anderes Problem war eine Rundreise durch die 4461 Gemeinden der neuen Bundesländer der Bundesrepublik. (siehe Bild) Ein noch größeres Problem war/ist eine Rundreise durch 13509 Gemeinden der USA mit mehr als 500 Einwohnern. Es gibt auch noch größere Probleme. Viele Grüße Ronald


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3104
  Beitrag No.18, eingetragen 2021-11-26

Also für die 96 französischen Städte finde ich mit 3-Opt deutlich kürzere Rundreisen. Irgendwer macht also etwas falsch. (Vermutlich ich) Bspw. erhalte ich die Sortierung: [41, 25, 6, 83, 29, 33, 12, 82, 19, 95, 5, 3, 4, 37, 72, 73, 68, 70, 0, 38, 20, 24, 69, 89, 67, 66, 87, 53, 56, 54, 50, 7, 1, 58, 61, 79, 59, 75, 13, 49, 26, 94, 91, 77, 74, 92, 93, 90, 76, 21, 9, 51, 28, 88, 55, 44, 34, 27, 52, 60, 71, 48, 36, 40, 43, 17, 57, 2, 62, 22, 35, 84, 85, 78, 16, 86, 15, 23, 32, 18, 14, 45, 46, 39, 31, 64, 63, 8, 65, 10, 30, 81, 80, 11, 47, 42, ] mit Länge 6092. Indizes beziehen sich auf die Liste: \sourceon CSV \numberson 46.200, 5.233 49.566, 3.616 46.566, 3.333 44.100, 6.233 44.566, 6.083 43.700, 7.266 44.733, 4.600 49.766, 4.716 42.966, 1.600 48.300, 4.083 43.216, 2.350 44.350, 2.566 43.300, 5.383 49.183, 0.366 44.933, 2.433 45.650, 0.166 46.166, 1.150 47.083, 2.400 45.266, 1.766 41.933, 8.733 47.316, 5.050 48.516, 2.766 46.166, 1.866 45.183, 0.716 47.250, 6.016 44.933, 4.883 49.016, 1.150 48.450, 1.483 48.000, 4.100 43.833, 4.366 43.600, 1.450 43.650, 0.583 44.833, 0.583 43.616, 3.883 48.116, 1.683 46.816, 1.683 47.400, 0.683 45.183, 5.733 46.666, 5.550 43.883, 0.500 47.600, 1.333 45.433, 4.383 45.050, 3.883 47.216, 1.550 47.900, 1.900 44.450, 1.433 44.200, 0.616 44.516, 3.500 47.466, 0.550 49.116, 1.100 48.950, 4.366 48.116, 5.133 48.066, 0.766 48.700, 6.183 48.766, 5.166 47.650, 2.766 49.116, 6.183 47.000, 3.150 50.633, 3.050 49.433, 2.083 48.433, 0.100 50.283, 2.783 45.783, 3.083 43.300, 0.366 43.233, 0.066 42.700, 2.900 48.583, 7.750 48.083, 7.350 45.766, 4.833 47.616, 6.150 46.300, 4.833 48.000, 0.200 45.566, 5.916 45.900, 6.133 48.850, 2.350 49.450, 1.100 48.533, 2.666 48.800, 2.133 46.333, 0.466 49.900, 2.300 43.933, 2.150 44.016, 1.350 43.133, 5.933 43.950, 4.800 46.666, 1.433 46.583, 0.333 45.833, 1.266 48.166, 6.450 47.800, 3.566 47.633, 6.850 48.633, 2.450 48.883, 2.200 48.916, 2.433 48.783, 2.466 49.033, 2.066 42.700, 9.450 \sourceoff Eine andere vom 3-Opt-Solver vorgeschlagene Rundreise wäre [6, 42, 41, 68, 70, 0, 38, 20, 24, 69, 89, 87, 67, 66, 53, 56, 54, 51, 28, 9, 50, 7, 1, 58, 61, 79, 59, 94, 91, 77, 74, 92, 93, 90, 76, 21, 88, 55, 17, 57, 2, 62, 14, 18, 22, 16, 84, 35, 43, 40, 44, 34, 27, 26, 49, 75, 13, 60, 71, 52, 48, 36, 85, 78, 86, 15, 23, 32, 46, 39, 31, 64, 63, 8, 65, 10, 80, 30, 81, 45, 11, 47, 33, 29, 83, 12, 82, 19, 95, 5, 3, 4, 37, 72, 73, 25, ] mit laut Programm einer Länge von nur 6066. (Initialisierung ist jeweils zufällig)


   Profil
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1996
  Beitrag No.19, eingetragen 2021-11-26

Hallo DerEinfaeltige! https://www.matheplanet.de/matheplanet/nuke/html/uploads/b/15578_TSP_2021_Einfaeltige.gif (2 Routen von der Einfältige) Hast Du mal probiert, wie lange bei Dir die 6748er Route aus dem Artikel ist? x = [76 27 14 50 61 72 49 53 35 22 29 56 44 85 17 79 86 16 24 33 ... 40 64 65 32 47 46 82 81 31 9 11 66 34 30 84 13 83 20 96 6 ... 4 5 38 73 74 39 1 71 69 42 26 7 43 48 12 15 19 87 23 63 ... 3 58 18 36 37 41 45 28 78 92 95 93 75 94 91 77 89 10 52 21 ... 25 70 90 68 67 88 54 57 55 51 8 2 59 62 80 60]; mit Städten aus 1 bis 96. Eventuell ist die Distanzmatrix nicht ganz korrekt! Ich vermute anhand des Bildes, da gibt es Probleme mit - und + bei den Koordinaten. Manche Städte haben negative Koordinaten. In meinem Matheplanet Notizbuch ist die Distanzmatrix für TSP96 wie ich sie verwendet habe. Viele Grüße Ronald


   Profil
Kay_S
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.03.2007
Mitteilungen: 1387
Wohnort: Koblenz (früher: Berlin)
  Beitrag No.20, eingetragen 2021-11-26

\quoteon(2021-11-26 11:03 - Delastelle in Beitrag No. 17) Was mir persönlich fehlt ist ein gutes Buch zum Thema. Zu guten Heuristiken und gelösten Beispielen. \quoteoff Hi, Hinsichtlich TSP-Heuristiken empfehlenswert: https://www.matheplanet.com/matheplanet/nuke/html/uploads/b/17348_Hoos_St_tzle.jpg Eines der wenigen (teuren) Fachbücher, die ich mir zugelegt habe. Schwerpunkt sind Algorithmen aus dem Bereich Stochastische Lokale Suche, insbesondere ILS (Iterated Local Search) aber auch Simulated Annealing, Tabu Search oder Populationsbasierte (z.B. genetische Algorithmen). Neben einem Abschnitt allgemeiner Natur (u.a. über Fitnesslandschaften) geht es in einem zweiten über Anwendungen an konkreten Problemen. Neben SAT und Scheduling-Problemen widmet es sich auf ca. 60 Seiten dem TSP. Hilfreich ebenfalls die Verweise auf wissenschaftliche Paper zum Thema. Die sind allerdings schon etwas älter, da das Buch selbst von 2005 ist. Die grundlegenden Arbeiten sind aber ohnehin aus den 70er bis 90er Jahren. Ferner möchte ich auf meinen eigenen TSP-Solver hinweisen :-) Dieser basiert auf ILS und nutzt neben k-Opt auch Teilstreckenverschiebungen. Allerdings nur für das Euklidische TSP, d.h. für das 96er Problem nur bedingt geeignet. Kay


   Profil
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1996
  Beitrag No.21, eingetragen 2021-11-26

Hallo Kay_S! Ich kenne vor allen den Übersichtsband von 1999: Spektrum Digest "Wissenschaftliches Rechnen" 106 Seiten. Über: - kombinatorische Optimierung "Toleranzschwelle und Sintflut - neue Ideen zur Optimierung" - kombinatorische Optimierung "Die Optimierte Odysee" // etwas zu Optimierung von TSP mit 16 Städten - auch als ganzzahliges Lineares Problem auch zu Mehrgitterverfahren zur Lösung eines Phänomens des Bodensees. Aus dem Band sind auch die 2 Bilder von meinem Beitrag 17. Ich habe auch mal zur Softwarelösung von Kay_S geschaut. Sieht ja ziemlich gut aus! Viele Grüße Ronald


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3104
  Beitrag No.22, eingetragen 2021-11-27

\quoteon(2021-11-26 13:11 - Delastelle in Beitrag No. 19) Eventuell ist die Distanzmatrix nicht ganz korrekt! Ich vermute anhand des Bildes, da gibt es Probleme mit - und + bei den Koordinaten. Manche Städte haben negative Koordinaten. \quoteoff Das war es! Ich hatte deine zwei Testdatensätze kopiert und nicht gesehen, dass im zweiten negative Koordinaten vorlagen. Daher hatte ich beim Parsen die Minuszeichen vergessen. (Hier könnte ein Facepalmsmilie stehen!) Jetzt komme ich auf leicht schlechtere Ergebnisse als deine "Musterlösung"!


   Profil
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1996
  Beitrag No.23, eingetragen 2021-11-28

Hallo, ich habe noch etwas mit TSP, Java, Parallelen Programmen und Branch&Bound experimentiert. Ich kann ein TSP mit den 20 größten deutschen Städten in akzeptabler Zeit mit Java und Branch&Bound lösen. https://www.matheplanet.de/matheplanet/nuke/html/uploads/b/15578_TSP_Problem1_n20_ff1911.gif (TSP 20 größten Städte opt = 1911; einige Städte liegen dicht beieinander im Ruhrgebiet) \showon java NuSTopWatch.java /** Quelle: C.Horstmann - Computing Concepts With Java2 A stopwatch accumulates time when it is running. You can repeatedly start and stop the stopwatch. You can use a stopwatch to measure the running time of a program. */ public class NuStopWatch { /** Constructs a stopwatch that is in the stopped state and has no time accumulated. */ public NuStopWatch() { reset(); } /** Starts the stopwatch. Time starts accumulating now. */ public void start() { if (isRunning) return; isRunning = true; startTime = System.currentTimeMillis(); } /** Stops the stopwatch. Time stops accumulating and is is added to the elapsed time. */ public void stop() { if (!isRunning) return; isRunning = false; long endTime = System.currentTimeMillis(); elapsedTime = elapsedTime + endTime - startTime; } /** Returns the total elapsed time. @return the total elapsed time */ public long getElapsedTime() { if (isRunning) { long endTime = System.currentTimeMillis(); elapsedTime = elapsedTime + endTime - startTime; startTime = endTime; } return elapsedTime; } /** Stops the watch and resets the elapsed time to 0. */ public void reset() { elapsedTime = 0; isRunning = false; } private long elapsedTime; private long startTime; private boolean isRunning; } \showoff \showon java TSPBB.java public class TSPBB { public int opti; public int[] optbelegung = new int[96]; /* c n = 20 // 1911 // 30196.996 Sek (Laptop) Java 1 Prozessor c n = 19 // 1898 // 10658.511 Sek. (Laptop) Java 1 Prozessor c n = 18 // 1894 // 1983.069 Sek. (Laptop) Java 1 Prozessor c n = 17 // 1893 // 651.969 Sek (2000+) FTN 237.191 Sek (Laptop) Java c n = 16 // 1858 // 74.625 Sek (2000+) FTN 27.253 Sek (Laptop) Java c n = 15 // 1858 // 11.82 Sek (2000+) FTN 4.449 Sek (Laptop) Java c n = 14 // 1849 // 2.23438 Sek (2000+) FTN 0.883 Sek (Laptop) */ /* ************************************************** c Backtracking-Algorithmus für TSP c ************************************************** */ public void BBsolver(int[][] dist,int[] belegung,int[] frei,int tiefe,int n,int[] laenge) { tiefe = tiefe + 1; // System.out.println("Start: Tiefe "+tiefe+" opti "+opti); // System.out.println("n "+n); for (int i = 1; i <= n; i++) { if (frei[i] == 1) { frei[i] = 0; belegung[tiefe] = i; // System.out.println("i "+i+" tiefe "+tiefe); laenge[tiefe] = laenge[tiefe-1] + dist[i][belegung[tiefe-1]]; if (tiefe == n) { laenge[tiefe+1] = laenge[tiefe] + dist[i][belegung[1]]; } // System.out.println("tiefe "+tiefe+" laenge[tiefe] "+laenge[tiefe]); if ((tiefe < n) && (laenge[tiefe] < opti)) { BBsolver(dist,belegung,frei,tiefe,n,laenge); } else { if ((tiefe == n) && (laenge[tiefe+1] < opti)) // tiefe+1 { opti = laenge[tiefe+1]; // tiefe+1 System.out.print("// opti "+opti); for (int j = 1; j <= n; j++) { optbelegung[j-1] = belegung[j]; } } } frei[i] = 1; } } tiefe = tiefe - 1; } } \showoff \showon Java TSPBBMain.java // import java.util.*; public class TSPBBMain { int opti2; int[] optbelegung2 = new int[97]; public void solver(int problem,int nn,int BBTeil,int bound) { double[][] lage = new double[97][2]; int[][] dist = new int[97][97]; int[] belegung = new int[97]; // int[] optbelegung = new int[97]; int[] laenge = new int[97]; int[] frei = new int[97]; int staedte,bsp,erg,nr,n; int opti,tiefe; int ug1,ug2,ug3,ug4,og1,og2,og3,og4; double[] ort1 = new double[2]; double[] ort2 = new double[2]; double phi1,phi2,tht1,tht2,pi; double angularDistCos,angularDist; double Erdradius,distanz,avg,std; TSPBB TSPBBZeiger = new TSPBB(); int n1 = 82; double[][] a1 = { {0.0,0.0}, {52.28,13.36}, { 53.567,10.033}, { 48.133,11.567}, {50.950,6.950}, {50.117,8.683}, {48.783,9.183}, {51.517,7.467}, {51.467,7.017}, {51.233,6.783}, {53.083,8.817}, {52.383,9.733}, {51.339,12.377}, {51.050,13.739}, {49.450,11.083}, {51.433,6.767}, {51.483,7.217}, {51.267,7.200}, {52.017,8.533}, {50.733,7.100}, {49.483,8.467}, {49.017,8.400}, {50.100,8.233}, {49.933,8.867}, {51.550,7.100}, {48.367,10.900}, {51.200,6.433}, {50.783,6.083}, {52.267,10.533}, {50.830,12.917}, {54.333,10.133}, {51.333,6.567}, {51.479,11.978}, {52.122,11.619}, {48.000,7.850}, {47.783,11.133}, {53.867,10.683}, {50.986,11.022}, {54.089,12.125}, {50.000,8.267}, {51.317,9.500}, {51.367,7.467}, {49.733,8.433}, {49.233,7.000}, {51.426,6.887}, {51.550,7.217}, {49.467,8.450}, {52.283,8.050}, {51.167,7.083}, {51.033,7.000}, {53.150,8.217}, {51.200,6.683}, {52.401,13.049}, {49.400,8.683}, {51.717,8.750}, {49.867,8.650}, {49.800,9.933}, {49.017,12.100}, {48.767,11.433}, {49.150,9.217}, {51.533,9.933}, {48.400,9.983}, {51.617,7.200}, {52.417,10.783}, {48.883,8.700}, {51.533,6.933}, {50.103,8.764}, {53.550,8.583}, {49.483,10.983}, {51.183,7.183}, {48.500,9.217}, {51.450,6.633}, {50.350,7.600}, {50.983,7.133}, {52.117,10.417}, {50.883,8.033}, {49.600,11.000}, {49.750,6.650}, {52.150,9.950}, {51.766,14.335}, {50.933,11.591}, {50.878,12.076}}; // System.out.println(a1[80][1]); int n2 = 97; double[][] a2 = { {0.0, 0.0}, {46.2000, 5.2330}, { 49.5660, 3.6160}, { 46.5660, 3.3330}, { 44.1000, 6.2330}, { 44.5660, 6.0830}, { 43.7000, 7.2660}, { 44.7330, 4.6000}, { 49.7660, 4.7160}, { 42.9660, 1.6000}, { 48.3000, 4.0830}, { 43.2160, 2.3500}, { 44.3500, 2.5660}, { 43.3000, 5.3830}, { 49.1830, -0.3660}, { 44.9330, 2.4330}, { 45.6500, 0.1660}, { 46.1660, -1.1500}, { 47.0830, 2.4000}, { 45.2660, 1.7660}, { 41.9330, 8.7330}, { 47.3160, 5.0500}, { 48.5160, -2.7660}, { 46.1660, 1.8660}, { 45.1830, 0.7160}, { 47.2500, 6.0160}, { 44.9330, 4.8830}, { 49.0160, 1.1500}, { 48.4500, 1.4830}, { 48.0000, -4.1000}, { 43.8330, 4.3660}, { 43.6000, 1.4500}, { 43.6500, 0.5830}, { 44.8330, -0.5830}, { 43.6160, 3.8830}, { 48.1160, -1.6830}, { 46.8160, 1.6830}, { 47.4000, 0.6830}, { 45.1830, 5.7330}, { 46.6660, 5.5500}, { 43.8830, -0.5000}, { 47.6000, 1.3330}, { 45.4330, 4.3830}, { 45.0500, 3.8830}, { 47.2160, -1.5500}, { 47.9000, 1.9000}, { 44.4500, 1.4330}, { 44.2000, 0.6160}, { 44.5160, 3.5000}, { 47.4660, -0.5500}, { 49.1160, -1.1000}, { 48.9500, 4.3660}, { 48.1160, 5.1330}, { 48.0660, -0.7660}, { 48.7000, 6.1830}, { 48.7660, 5.1660}, { 47.6500, -2.7660}, { 49.1160, 6.1830}, { 47.0000, 3.1500}, { 50.6330, 3.0500}, { 49.4330, 2.0830}, { 48.4330, 0.1000}, { 50.2830, 2.7830}, { 45.7830, 3.0830}, { 43.3000, -0.3660}, { 43.2330, 0.0660}, { 42.7000, 2.9000}, { 48.5830, 7.7500}, { 48.0830, 7.3500}, { 45.7660, 4.8330}, { 47.6160, 6.1500}, { 46.3000, 4.8330}, { 48.0000, 0.2000}, { 45.5660, 5.9160}, { 45.9000, 6.1330}, { 48.8500, 2.3500}, { 49.4500, 1.1000}, { 48.5330, 2.6660}, { 48.8000, 2.1330}, { 46.3330, -0.4660}, { 49.9000, 2.3000}, { 43.9330, 2.1500}, { 44.0160, 1.3500}, { 43.1330, 5.9330}, { 43.9500, 4.8000}, { 46.6660, -1.4330}, { 46.5830, 0.3330}, { 45.8330, 1.2660}, { 48.1660, 6.4500}, { 47.8000, 3.5660}, { 47.6330, 6.8500}, { 48.6330, 2.4500}, { 48.8830, 2.2000}, { 48.9160, 2.4330}, { 48.7830, 2.4660}, { 49.0330, 2.0660}, { 42.7000, 9.4500} }; // System.out.println(a2[95][1]); if (problem == 1) { n = n1; lage = a1; } else { n = n2; lage = a2; } pi = 3.14159265; for(int i = 1; i < n-1; i++) { for (int j = i+1; j < n; j++) { // System.out.println("j "+j); ort1[0] = lage[i][0]; ort1[1] = lage[i][1]; ort2[0] = lage[j][0]; ort2[1] = lage[j][1]; phi1 = ort1[0]*pi/180.0; tht1 = ort1[1]*pi/180.0+pi/4.0; phi2 = ort2[0]*pi/180.0; tht2 = ort2[1]*pi/180.0+pi/4.0; angularDistCos=Math.sin(phi1)*Math.sin(phi2) +Math.cos(phi1)*Math.cos(phi2)*Math.cos(tht1-tht2); angularDist=Math.acos(angularDistCos)*180/pi; Erdradius=6350.0; distanz=(angularDist*pi/180.0)*Erdradius; dist[i][j] = (int) Math.floor(distanz+0.5); dist[j][i] = dist[i][j]; // System.out.println("dist "+dist[5][6]); } } for (int i = 1; i <= nn; i++) { belegung[i] = i; // optbelegung[i] = i; TSPBBZeiger.optbelegung[i] = i; frei[i] = 1; laenge[i] = 0; }; double nnd = (double) nn; ug1 = 1; og1 = (int) Math.ceil(nnd/4.0); ug2 = (int) Math.floor(nnd/4.0)+1; og2 = (int) Math.ceil(2.0*nnd/4.0); ug3 = (int) Math.floor(2.0*nnd/4.0)+1; og3 = (int) Math.ceil(3.0*nnd/4.0); ug4 = (int) Math.floor(3.0*nnd/4.0)+1; og4 = (int) nnd; if (ug2 == og1) {ug2 = ug2 + 1; } if (ug3 == og2) {ug3 = ug3 + 1; } if (ug4 == og3) {ug4 = ug4 + 1; } if (BBTeil == 1) { TSPBBZeiger.opti = bound; for(int i = ug1; i <= og1; i++) { if (i != 1) { System.out.println(" "); System.out.println("(a) i = "+i); belegung[1] = 1; frei[1] = 0; laenge[1] = 0; belegung[2] = i; frei[i] = 0; laenge[2] = dist[1][i]; tiefe = 2; TSPBBZeiger.BBsolver(dist,belegung,frei,tiefe,nn,laenge); frei[i] = 1; System.out.println("opti "+TSPBBZeiger.opti); for (int ii = 0; ii < nn; ii++) { optbelegung2[ii] = TSPBBZeiger.optbelegung[ii]; } opti2 = TSPBBZeiger.opti; } } } if (BBTeil == 2) { TSPBBZeiger.opti = bound; for(int i = ug2; i <= og2; i++) { if (i != 1) { System.out.println(" "); System.out.println("(b) i = "+i); belegung[1] = 1; frei[1] = 0; laenge[1] = 0; belegung[2] = i; frei[i] = 0; laenge[2] = dist[1][i]; tiefe = 2; TSPBBZeiger.BBsolver(dist,belegung,frei,tiefe,nn,laenge); frei[i] = 1; System.out.println("opti "+TSPBBZeiger.opti); for (int ii = 0; ii < nn; ii++) { optbelegung2[ii] = TSPBBZeiger.optbelegung[ii]; } opti2 = TSPBBZeiger.opti; } } } if (BBTeil == 3) { TSPBBZeiger.opti = bound; for(int i = ug3; i <= og3; i++) { if (i != 1) { System.out.println(" "); System.out.println("(c) i = "+i); belegung[1] = 1; frei[1] = 0; laenge[1] = 0; belegung[2] = i; frei[i] = 0; laenge[2] = dist[1][i]; tiefe = 2; TSPBBZeiger.BBsolver(dist,belegung,frei,tiefe,nn,laenge); frei[i] = 1; System.out.println("opti "+TSPBBZeiger.opti); for (int ii = 0; ii < nn; ii++) { optbelegung2[ii] = TSPBBZeiger.optbelegung[ii]; } opti2 = TSPBBZeiger.opti; } } } if (BBTeil == 4) { TSPBBZeiger.opti = bound; for(int i = ug4; i <= og4; i++) { if (i != 1) { System.out.println(" "); System.out.println("(d) i = "+i); belegung[1] = 1; frei[1] = 0; laenge[1] = 0; belegung[2] = i; frei[i] = 0; laenge[2] = dist[1][i]; tiefe = 2; TSPBBZeiger.BBsolver(dist,belegung,frei,tiefe,nn,laenge); frei[i] = 1; System.out.println("opti "+TSPBBZeiger.opti); for (int ii = 0; ii < nn; ii++) { optbelegung2[ii] = TSPBBZeiger.optbelegung[ii]; } opti2 = TSPBBZeiger.opti; } } } } } \showoff \showon java TSPBBParallel.java // Oechsle: "Parallele und verteilte Anwendungen in Java" (2011) // 81er opt=3785 // 96er opt=6748 public class TSPBBParallel extends Thread { private String myName; private String[] arg; private int BBTeil; public TSPBBParallel (String name, String[] args, int kkk) { myName = name; arg = args; BBTeil = kkk; } public void run() { TSPBBMain TSPBBMainZeiger = new TSPBBMain(); NuStopWatch nuStopWatchZeiger = new NuStopWatch(); int[] out = new int[97]; int bound,problem,bigsteps,dim,k,n; problem = 1; try { problem = Integer.parseInt(arg[0]); n = Integer.parseInt(arg[1]); bound = Integer.parseInt(arg[2]); System.out.println("n "+n); } catch(Exception e) { problem = 1; n = 10; bound = 999999; System.out.println("Programm ohne Parameter aufgerufen"); System.out.println("n(default) = " + n); } nuStopWatchZeiger.start(); System.out.println("BBTeil "+BBTeil); TSPBBMainZeiger.solver( problem,n,BBTeil,bound); if (problem == 1) { dim = 82; } else { dim = 96; } // dim = 20; int[] belegung= new int[97]; int ff; for (int i = 0; i < n; i++) { belegung[i] = TSPBBMainZeiger.optbelegung2[i]; System.out.print(" "+belegung[i]); } ff = TSPBBMainZeiger.opti2; System.out.println("\nNr: "+myName+" ff "+ff); nuStopWatchZeiger.stop(); System.out.println("// Zeit = " + nuStopWatchZeiger.getElapsedTime()); System.out.println(" "); } public static void main(String[] args) { int kkk; kkk = 1; TSPBBParallel t1 = new TSPBBParallel("Thread 1",args,kkk); kkk = 2; TSPBBParallel t2 = new TSPBBParallel("Thread 2",args,kkk); kkk = 3; TSPBBParallel t3 = new TSPBBParallel("Thread 3",args,kkk); kkk = 4; TSPBBParallel t4 = new TSPBBParallel("Thread 4",args,kkk); t1.start(); t2.start(); t3.start(); t4.start(); } } \showoff Aufruf mittels: java TSPBBParallel Problem n bound mit Problem = 1: Deutschland 81 oder 2: Frankreich 96 n = Anzahl der Städte bound = Schranke für Branch&Bound \showon java TSPBBParallel 1 20 1912 n 20 BBTeil 3 n 20 n 20 n 20 BBTeil 2 BBTeil 4 BBTeil 1 (d) i = 16 (b) i = 6 (c) i = 11 (a) i = 2 opti 1912 (b) i = 7 opti 1912 (d) i = 17 // opti 1911opti 1912 (d) i = 18 opti 1912 (b) i = 8 opti 1912 (b) i = 9 opti 1912 (b) i = 10 opti 1912 (d) i = 19 opti 1911 (a) i = 3 opti 1912 (d) i = 20 opti 1911 (a) i = 4 opti 1912 (c) i = 12 opti 1912 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 Nr: Thread 4 ff 1912 // Zeit = 3845343 opti 1911 (a) i = 5 opti 1912 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 Nr: Thread 2 ff 1912 // Zeit = 4160463 opti 1911 1 2 10 11 18 7 16 8 15 9 17 4 19 5 20 6 3 14 12 13 Nr: Thread 1 ff 1911 // Zeit = 4521120 opti 1912 (c) i = 13 // opti 1911opti 1911 (c) i = 14 opti 1911 (c) i = 15 opti 1911 1 13 12 14 3 6 20 5 19 4 17 9 15 8 16 7 18 11 10 2 Nr: Thread 3 ff 1911 // Zeit = 13399314 \showoff Prozess 3 brauchte hier am längsten mit 13399 Sekunden. Bemerkungen: - java benutzt hier Rekursion - java benutzt hier bis zu 4 Prozessoren parallel - die Programme basieren zum Teil auf Fortran Programmen und zählen ab 1 statt 0 - die 1.Belegung ist immer 1 - die 2.Belegung wird in 4 Teile aufgeteilt, die dann von den 4 Prozessoren bearbeitet werden - NuSTopWatch ist für die Zeitmessung - TSPBB ist für Branch&Bound - TSPBBMain erstellt die Distanzmatrix und ist das Rahmenprogramm - TSPBBParallel ist das äußerste Programm und startet 4 Prozesse Viele Grüße Ronald Edit: https://www.matheplanet.de/matheplanet/nuke/html/uploads/b/15578_TSP_Problem2_n20_ff3142_10004Sek.gif (Problem2 // Fra96 // n20 // bis zu 10004 Sekunden Branch&Bound)


   Profil
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1996
  Beitrag No.24, eingetragen 2022-02-25

Hallo, 3Opt läuft bei mir inzwischen auch (mit Fortran und 96 Städten). Siehe: https://www.matheplanet.de/matheplanet/nuke/html/viewtopic.php?topic=256193&start=0&lps=1871232#v1871232 Viele Grüße Ronald


   Profil
CSharper wird per Mail über neue Antworten informiert.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]