| |
| Autor |
 TSP - Christofides ... Schritt 5 unklar. Muss hier optimiert werden? |
|
CSharper
Junior 
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 
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
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
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 
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
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
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 
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
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
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
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
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
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 
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
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
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
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
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
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
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
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
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
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
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
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. |
|
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]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
