Traveling salesman problem ZIP-Methode Kombinatorischer Ansatz einer optimalen Lösung symmetrischer...

traveling salesman problem

ZIP-Methode

Kombinatorischer Ansatz

einer optimalen Lösung

symmetrischer Rundreiseprobleme

• Ziel:– Vorstellung eines kombinatorischen

Lösungsansatzes des Rundreiseproblems

• Voraussetzungen:– Kenntnisse der vier Grundrechenarten– etwas Geduld mit dem Vortragenden ....

Anlass:Fachschullehrbuch: Mathematik für Wirtschaftswissenschaften Verlag die Wirtschaft, Berlin (DDR), 1983

- darin: Rundreiseproblem S. 418ff.

Agenda

– das Rundreiseproblem– bisherige Lösungen– neue Überlegungen– Beispiel mit 6 Knoten– Beispiel mit 10 Knoten– Beispiel mit 26 Knoten (Ergebnisse)– Schlussfolgerungen und Ausblick

das Rundreiseproblem

Formulierung des Rundreiseproblems:

Gesucht wird die kürzeste Entfernung zwischen n verschiedenen Orten.

Dabei soll jeder Ort nur einmal aufgesucht werden und die Rundreise wieder im Ausgangsort enden.

• graphentheoretische Beschreibung:

• Graph G– Knoten xi

– Kante u(xi,xj) bzw. u<xi,xj>

– Knotengrad– Komponenten eines Graphs– Teilgraph eines Graphs (Kantenteilgraph)– Graphfamilie und Mächtigkeit

• Laufindexe:– i = Laufindex des Anfangsknoten xi

– j = Laufindex des Endknoten xj

– k = Laufindex des Platzes einer Kante innerhalb eines Graphen

• Kurz-Schreibweise einer Kante:– u(ij) i-j (Beispiel: u(2;4) 2-4)

– f(i-j) = Ausprägung der Kante; (z.B.: Länge)

• kleinster Graph:Problem ist nicht die Berechnung des einzelnen Graphen, sondern die mit wachsenden n Knoten um je eine Fakultät ansteigenden Zahl der Graphen.

|G| = n ! bei beliebigem Anfangsknoten

|G| = (n-1)! , wenn Anfangsknoten x1 ist.

|G| = (n-1)! /2 bei Symmetrie

bisherige Lösungen

• bisherige allgemeine optimale Lösungen:

(grundsätzlich: Überprüfung aller Lösungen)

– Voll-Enumeration– begrenzte Enumeration– branch and bound– weitere ....

alle allgemeinen optimalen Lösungen nur für kleine n

bisherige Lösungen

• bisherige suboptimale Lösungen:

– viele ...

– viele gute ...

– viele gute, für die Praxis völlig ausreichend ...

bisherige Lösungen

• Fazit zu den bisherigen Lösungen:

Soweit erkennbar, liegt das wissenschaftliche

Interesse seit langem in der Entwicklung und

Verbesserung von suboptimalen Lösungen,

weil scheinbar optimale Lösungen erschöpfend

erforscht sind.

neue Überlegungen ...

• aber zuerst eine

Aufgabe für Sie:

• Bitte schreiben Sie in

beliebiger Reihenfolge

die Zahlen von 1 bis 6

• Verbindet man die Knoten, so entsteht:

• 1-komponentiger G• mit 6 Kanten • mit 6 Knoten • jeder Knoten hat den

Knotengrad 2

wir erinnern uns:

bei n = 6

n! = 720

(n-1)! = 120

(n-1)! / 2 = 60

wir addieren nun die Werte der Kanten:

dabei tritt jeder Knoten zweimal auf:

– als Anfangsknoten

einer Kante

– und als Endknoten

einer Kante.

Und das ist vom Übel !

wenn jeder Knoten nur einmal auftritt, so entsteht aus dem ganzen Graphen:

ein Teilgraph mit

allen 6 Knoten, aber nur mit 3 Kanten:

z.B. Kanten: 1-6, 5-3, 2-4

... übrig bleibt ein

Komplement-Teilgraph mit

derselben Struktur

wie der Teilgraph !

Kanten: 1-4, 2-3, 5-6

• Der Graph setzt sich

also zusammen:

• aus dem Teilgraphen

mit Kanten:1-6,5-3,2-4

• und dem Teilgraphen

mit Kanten:1-4,2-3,5-6

Wegen derselben Struktur

der Teilgraphen muss

die Zahl der Knoten

gradzahlig sein.

(ggf. ist ein Pseudo-

Knoten einzufügen.)

• Symmetrie-Regel:

• Der Anfangsknoten

einer Kante hat den

kleineren Laufindex als

der Endknoten i < j:

f(1-6) + f(5-3) + f(2-4)

= f(1-6) + f(3-5) + f(2-4)

• Sortier-Regel:

• die Kanten werden nach

dem Laufindex ihres

Anfangsknoten sortiert. • 1. Kante 2. Kante 3. Kante

f(1-6) + f(3-5) + f(2-4)

= f(1-6) + f(2-4) + f(3-5)

wir erinnern uns:

Bei n = 6 gibt es insgesamt

120 Graphen bzw.

60 symmetrische Graphen

wieviele Teilgraphen

gibt es eigentlich ?

1. Teilgraph 1 - 2 3 - 4 5 - 6

2. Teilgraph 1 - 2 3 - 5 4 - 6

3. Teilgraph 1 - 2 3 - 6 4 - 5 4. Teilgraph 1 - 3 2 - 4 5 - 6

5. Teilgraph 1 - 3 2 - 5 4 - 6

6. Teilgraph 1 - 3 2 - 6 4 - 5

7. Teilgraph 1 - 4 2 - 3 5 - 6

8. Teilgraph 1 - 4 2 - 5 3 - 6

9. Teilgraph 1 - 4 2 - 6 3 - 5

10. Teilgraph 1 - 5 2 - 3 4 - 6

11. Teilgraph 1 - 5 2 - 4 3 - 6

12. Teilgraph 1 - 5 2 - 6 3 - 4

13. Teilgraph 1 - 6 2 - 3 4 - 5

14. Teilgraph 1 - 6 2 - 4 3 - 5

15. Teilgraph 1 - 6 2 - 5 3 - 4

mehr nicht !

Bei Anwendung der

Symmetrieregel und der

Sortierregel

läßt sich jeder der

120 Graphen in 2 der

15 Teilgraphen

zerlegen.

1. Teilgraph 1 - 2 3 - 4 5 - 6

2. Teilgraph 1 - 2 3 - 5 4 - 6

3. Teilgraph 1 - 2 3 - 6 4 - 5

4. Teilgraph 1 - 3 2 - 4 5 - 6

5. Teilgraph 1 - 3 2 - 5 4 - 6

6. Teilgraph 1 - 3 2 - 6 4 - 5

7. Teilgraph 1 - 4 2 - 3 5 - 6

8. Teilgraph 1 - 4 2 - 5 3 - 6

9. Teilgraph 1 - 4 2 - 6 3 - 5

10. Teilgraph 1 - 5 2 - 3 4 - 6

11. Teilgraph 1 - 5 2 - 4 3 - 6

12. Teilgraph 1 - 5 2 - 6 3 - 4

13. Teilgraph 1 - 6 2 - 3 4 - 5

14. Teilgraph 1 - 6 2 - 4 3 - 5

15. Teilgraph 1 - 6 2 - 5 3 - 4

Probieren Sie es bitte an Ihrem eigenen Beispiel aus.

• Wie viele Teilgraphen „passen“ zu einem Teilgraphen, d.h. bilden zusammen wieder einen Gesamt-Graphen ?

• Beispiel: 1-2, 3-4, 5-6

Nr.5, 6, 8, 9, 10, 11, 13, 14insgesamt 8 (= 2 x 4)

1. Teilgraph 1 - 2 3 - 4 5 - 6

2. Teilgraph 1 - 2 3 - 5 4 - 6

3. Teilgraph 1 - 2 3 - 6 4 - 5

4. Teilgraph 1 - 3 2 - 4 5 - 6

5. Teilgraph 1 - 3 2 - 5 4 - 6

6. Teilgraph 1 - 3 2 - 6 4 - 5

7. Teilgraph 1 - 4 2 - 3 5 - 6

8. Teilgraph 1 - 4 2 - 5 3 - 6

9. Teilgraph 1 - 4 2 - 6 3 - 5

10. Teilgraph 1 - 5 2 - 3 4 - 6

11. Teilgraph 1 - 5 2 - 4 3 - 6

12. Teilgraph 1 - 5 2 - 6 3 - 4

13. Teilgraph 1 - 6 2 - 3 4 - 5

14. Teilgraph 1 - 6 2 - 4 3 - 5

15. Teilgraph 1 - 6 2 - 5 3 - 4

• Wie erhält man den kleinsten Graphen ?

• 1. Schritt: man ermittelt den kleinsten Teilgraphen

• 2. Schritt: man ermittelt den zugehörigen kleinsten Kompl.-Teilgraphen.

1. Teilgraph 1 - 2 3 - 4 5 - 6

2. Teilgraph 1 - 2 3 - 5 4 - 6

3. Teilgraph 1 - 2 3 - 6 4 - 5

4. Teilgraph 1 - 3 2 - 4 5 - 6

5. Teilgraph 1 - 3 2 - 5 4 - 6

6. Teilgraph 1 - 3 2 - 6 4 - 5

7. Teilgraph 1 - 4 2 - 3 5 - 6

8. Teilgraph 1 - 4 2 - 5 3 - 6

9. Teilgraph 1 - 4 2 - 6 3 - 5

10. Teilgraph 1 - 5 2 - 3 4 - 6

11. Teilgraph 1 - 5 2 - 4 3 - 6

12. Teilgraph 1 - 5 2 - 6 3 - 4

13. Teilgraph 1 - 6 2 - 3 4 - 5

14. Teilgraph 1 - 6 2 - 4 3 - 5

15. Teilgraph 1 - 6 2 - 5 3 - 4

Damit ist vielleicht der kleinste Graph gefunden !

aber nur: vielleicht!

Weitere Überlegungen:

Der kleinste (Gesamt-)Graph setzt sich zusammen:

entweder: aus den beiden gefundenen Teilgraphen (kleinster Teilgraph mit zugehörigem kleinsten Kompl.-Teilgraph)

oder: aus zwei dazwischen liegenden Teilgraphen.

Zahlenbeispiel:• kleinster Teilgraph hat die Kantenlänge: 20• der kleinste zugehörige Kompl.-Teilgraph: 40• ergibt einen Gesamtgraphen: 60

interessant sind damit nur noch die Teilgraphen

mit Kantenlängen zwischen 20 und 40.

Außerdem:• ein Gesamtgraph mit einer Kantenlänge < 60

muß mindestens aus einem Teilgraphen mit einer Kantenlänge < 30 zusammengesetzt sein.

d.h., • nur Teilgraphen (und zugehörige Kompl.-Teilgraphen)

mit Kantenlängen zwischen 20 und < 30 sind zu prüfen.

• (a+b) < c a und/oder b < (c/2)

und a < b oder a = b a < (c/2)

Weitere Iterationsschritte:(bis zur halben Kantenlänge des bisher kleinsten gefundenen Gesamt-Graphen)

• ausgehend vom kleinsten Teilgraphen wird jeweils der nächst größere Teilgraph mit seinem Komplement-Teilgraph überprüft, ob daraus ein kleinerer Gesamt-Graph zusammengesetzt werden kann.

• wenn ja, ist der neue Gesamt-Graph Ausgangswert für weitere Iterationsschritte.

• wenn nein, ist der kleinste Graph bereits gefunden.

Beispiel mit 6 Knoten:

Gegeben seien 6 Knoten mit den zugehörigen Entfernungen:

• nach 1 nach 2 nach 3 nach 4 nach 5 nach 6

von 1 - 12 25 30 28 22

von 2 - 16 20 22 10

von 3 - 23 26 21

von 4 - 31 18

von 5 - 14

von 6 -

Kleinster Teilgraph: Nr. 1 mit Kantenlänge = 49

Nr. 1.K. 2.K. 3.K. K.-Länge 1. 1 - 2 3 - 4 5 - 6 49 2. 1 - 2 3 - 5 4 - 6 56 3. 1 - 2 3 - 6 4 - 5 64 4. 1 - 3 2 - 4 5 - 6 59 5. 1 - 3 2 - 5 4 - 6 65 6. 1 - 3 2 - 6 4 - 5 66 7. 1 - 4 2 - 3 5 - 6 60 8. 1 - 4 2 - 5 3 - 6 73 9. 1 - 4 2 - 6 3 - 5 6610. 1 - 5 2 - 3 4 - 6 6211. 1 - 5 2 - 4 3 - 6 6912. 1 - 5 2 - 6 3 - 4 6113. 1 - 6 2 - 3 4 - 5 6914. 1 - 6 2 - 4 3 - 5 6815. 1 - 6 2 - 5 3 - 4 67

Komp.-Teilgraphen:Nr. 5, 6, 8, 9, 10, 11, 13 u.14

davon der kleinste: Nr. 10 mit Kantenlänge = 62

Länge des Graphen: 111

(49 + 62) : 2 = 55,5

kleinster Graph

– das Rundreiseproblem - Fragestellung– Problem und bisherige Lösungen– neue Überlegungen– Beispiel mit 6 Knoten– Beispiel mit 10 Knoten– Beispiel mit 26 Knoten (Ergebnisse)– Schlussfolgerungen und Ausblick

Beispiel mit 10 Knoten: Entwicklung der ZIP-Formel bei n = 10:

1 · 3 · 5 · 7 · 9 =

9! ————————————— = (1 · 2) · (2 · 2) · (3 · 2) · (4 · 2)

9! ————————————— = ( 1 · 2 · 3 · 4 ) · ( 2 · 2 · 2 · 2 )

1 · 2 · 3 · 4 · 5 · 6 · 7 · 8 · 9————————————— = 2 · 4 · 6 · 8

9! ————————————— = 4! · 24

(n – 1)! —————————

( n/2 – 1 ) ! · 2 n/2 - 1

davon:

{ ( n/2 – 1 ) ! } (Sortierregel)

Teilgraph: — — — — —(Kantenzahl =n/2)

1 x 2 x 2 x 2 x 2 (Symmetrie)

Anfangsknoten = x1

Beispiel mit 10 Knoten:nachvon

1 2 3 4 5 6 7 8 9 10

1 - 16 44 93 1 30 30 5 78 42

2 - 68 61 42 77 41 79 22 32

3 - 39 48 21 36 28 40 80

4 - 43 8 66 46 30 35

5 - 67 69 11 84 91

6 - 97 43 63 67

7 - 85 89 18

8 - 2 85

lfd.Nr. K.-Länge 1. Kante 2.Kante 3.Kante 4.Kante 5.Kante Bemerk.1 76 1 - 2 3 - 7 4 - 6 5 - 8 9 -102 77 1 - 5 2 - 9 3 - 8 4 - 6 7 -103 79 1 - 5 2 -10 3 - 7 4 - 6 8 - 94 83 1 - 5 2 - 7 3 - 8 4 - 6 9 -105 92 1 - 2 3 - 5 4 - 6 7 -10 8 - 96 93 1 - 2 3 - 9 4 - 6 5 - 8 7 -107 96 1 - 2 3 - 6 4 - 9 5 - 8 7 -108 96 1 - 8 2 - 5 3 - 7 4 - 6 9 -109 97 1 - 5 2 - 3 4 - 6 7 -10 8 - 9

10 100 1 - 2 3 - 6 4 - 5 7 -10 8 - 911 100 1 - 5 2 - 7 3 - 6 4 -10 8 - 9 min.TGkomp

12 101 1 - 8 2 - 9 3 - 5 4 - 6 7 -1013 103 1 - 3 2 - 9 4 - 6 5 - 8 7 -10

....bis 945

min. TG

min. TG + min.Tgkomp = 176; 176 / 2 = 88Sortierung der 945 Teilgraphen nach Kantenlänge

10 100 1 - 2 3 - 6 4 - 5 7 -10 8 - 911 100 1 - 5 2 - 7 3 - 6 4 -10 8 - 912 101 1 - 8 2 - 9 3 - 5 4 - 6 7 -1013 103 1 - 3 2 - 9 4 - 6 5 - 8 7 -10

....bis 945

10 100 1 - 2 3 - 6 4 - 5 7 -10 8 - 911 100 1 - 5 2 - 7 3 - 6 4 -10 8 - 912 101 1 - 8 2 - 9 3 - 5 4 - 6 7 -1013 103 1 - 3 2 - 9 4 - 6 5 - 8 7 -10

....bis 945

10 100 1 - 2 3 - 6 4 - 5 7 -10 8 - 911 100 1 - 5 2 - 7 3 - 6 4 -10 8 - 9

min.TGkomp

12 101 1 - 8 2 - 9 3 - 5 4 - 6 7 -1013 103 1 - 3 2 - 9 4 - 6 5 - 8 7 -10

....bis 945

min. TG

min. TG + min.Tgkomp = 175; 175 / 2 = 87,5

10 100 1 - 2 3 - 6 4 - 5 7 -10 8 - 911 100 1 - 5 2 - 7 3 - 6 4 -10 8 - 912 101 1 - 8 2 - 9 3 - 5 4 - 6 7 -1013 103 1 - 3 2 - 9 4 - 6 5 - 8 7 -10

....bis 945

opt. TG

opt.TGkomp

101-120

141-160

181-200

221-240

261-280

301-320

341-360

381-400

421-440

Summe der Kantenlängen nach dem 1.Durchlauf: nur noch 11 von 945 Teilgraphen bei insgesamt 181.440 Gesamt-Graphen

• Von insgesamt 945 Teilgraphen scheiden beim back tracking der begrenzten Enumeration aus:

• Abbruch nach der 5. Kante: 0

möglichst frühzeitiger Abbruch !!

Beziehung zwischen Anfangsknoten und Kantenplatz:

1. Kante 2. Kante 3. Kante 4. Kante 5. Kante

1-2...1-10 2-3...2-10 3-4...3-10 4-5...4-10 5-6...5-10oder oder oder oder

3-4...3-10 4-5...4-10 5-6...5-10 6-7...6-10oder oder oder

5-6...5-10 6-7...6-10 7-8...7-10oder oder oder

7-8...7-10 8-9...8-10oder

i = k für k = 1 9-10.

i = k, k + 1 , ... , 2k -1 für k > 1

Anfangs-Knoten

1.Kante 2.Kante 3.Kante 4.Kante 5.KanteSumme je

KnotenNr.1 945 - - - - 945Nr.2 - 840 - - - 840Nr.3 - 105 630 - - 735Nr.4 - - 270 360 - 630Nr.5 - - 45 360 120 525Nr.6 - - - 180 240 420Nr.7 - - - 45 270 315Nr.8 - - - - 210 210Nr.9 - - - - 105 105

Nr.10 - - - - 0 0Summe

derKanten

945 945 945 945 945

weitere Überlegungen:• Numerierungsregel

(die größten Abweichungen nach vorn)

• Minimalkantenregel

(Berechnung der noch ausstehenden kleinsten Kante für jeden einzelnen Kantenplatz; nicht mehr für alle)

0 10 20 30 40 50 60 70 80 90

1. Kante

2. Kante

3. Kante

4. Kante

5. Kante

Beispiel: Knoten xi mit seinen 5 Kanten

NumerierungsregelMinimalkantenregel

Weihnachtsrätsel:• Das Institut für Rechnergestützte Wissenverarbeitung

(KBS) der Universität Hannover hat 1996 als „Weihnachtsrätsel“ die Aufgabe gestellt, für 26 europäische Hauptstädte die kürzeste Rundreise zu finden.

• Die Aufgabe mit Lösungen finden Sie leider nicht mehr im Internet

Zahl aller Graphen (25!): 15.511.210.043.330.985.984.000.000

Zahl der symm. Graphen: 7.755.605.021.665.492.992.000.000

Zahl aller Teilgraphen : 7.905.853.580.625

• Ergebnisse: kl.Teilgraph + kl.Komp.-Teilgraph: 6.845 km + 9.912 km = 16.757 km heuristisch gefundener kl. Graph: 7.331 km + 8.858 km = 16.189 km davon die Hälfte : 16.189 km / 2 = 8.094 km

Beispiel mit 26 Knoten:heuristisch gefundener kl. Graph: 7.331 km + 8.858 km = 16.189 km

davon die Hälfte: (abgerundet:) 8.094 km

kl. Teilgraph + kl. Komp.-Teilgraph: 6.845 km + 9.912 km = 16.757 km

kleinster Teilgraph bei 6.845 km: 1

Zahl der Teilgraphen bis 7.331 km: 40

Zahl der Teilgraphen bis 8.094 km: 2.725

Zahl der Teilgraphen bis 8.858 km: 57.200

Zahl der Teilgraphen bis 9.912 km: 1.568.529

Anzahl aller Teilgraphen: 7.905.853.580.625

Geographische Darstellung des opimalen Graphen

1. Amsterdam 2. Athen 3. Barcelona 4. Belgrad 5. Berlin 6. Brüssel 7. Bucarest 8. Budapest 9. Frankfurt/M10. Genf11. Helsinki12. Istanbul13. Kopenhagen14. Lissabon15. London16. Madrid17. Mailand18. Oslo19. Paris20. Prag 21. Rom22. Sofia23. Stockholm ...

1. Lissabon 2. Helsinki 3. Madrid 4. Istanbul 5. Athen 6. Bucarest 7. Sofia 8. Stockholm 9. Oslo10. Belgrad11. Budapest12. Kopenhagen13. Rom14. Warschau15. Wien16. Berlin17. Amsterdam18. London19. Brüssel20. Prag 21. Mailand22. Zürich 23. Barcelona ...

Schlussfolgerungen und Ausblick

Schlussfolgerungen

– diese algebraische Lösung ist offensichtlich neu– das Weihnachtsrätsel mit 26 Orten ist optimal gelöst– es kann gesagt werden,

ob eine optimale Lösung gefunden wurde.– Symmetrie wird voll ausgenutzt ..... – und ...

Schlussfolgerungen

– bis ca. 10 Knoten (ggf. mehr) lassen sich symmetrische Graphen mit der Voll-Enumeration optimal lösen.

– bis ca. 30 Knoten (ggf. mehr) lassen sich symmetrische Graphen mit der begrenzten Enumeration optimal lösen.

Für alle TSP-Verfahren gilt:

Können bekannte Lösungen nicht nur auf Graphen sondern auch auf Teilgraphen angewandt werden, so bringt die ZIP-Methode den entscheidenden Quantensprung der rechentechnischen Vereinfachung.

Ausblick

– es bleibt zu prüfen, ob der neue Lösungsansatz auch auf andere Optimierungsprobleme angewandt werden kann.

– Alle Aspekte des neuen Lösungsansatzes sind sicherlich noch nicht geklärt und sollten weiter untersucht werden.

Vielen Dank für Ihre Aufmerksamkeit

Traveling salesman problem ZIP-Methode Kombinatorischer Ansatz einer optimalen Lösung symmetrischer...

Documents

Schülerinfotage KombiBA, 22. Januar 2013 DIE BERGISCHE UNIVERSITÄT WUPPERTAL 22. Januar 2013 Schülerinfotage Kombinatorischer Studiengang Bachelor of Arts

Finite-amplitude gravity waves in the atmosphere ... · atmosphere: traveling wave solutions Mark Schlutow 1 y, R. Klein 1 and U. Achatz 2 1 Institut fur Mathematik, Freie Universit

Wo machen die Deutschen gern Urlaub? Thema der Woche: Urlaub/ Ferien/ Reisen “Germans see traveling as a kind of fundamental right” Tourism Expert Born

Subtour Elimination Constraints - Foswiki · Subtour Elimination Constraints Problem: Traveling Salesman Input: Ein Graph G= (V;E) mit einer Distanzfunktion d: E!Q 0. Aufgabe: Finde

Bachelor of Education Informatik Master of Education ... · Digitale Abstraktion Kombinatorischer Logischer Entwurf Sequentieller Logischer Entwurf ... 5 Vorlesung und Übung 3 2

InfoMails verschicken wir auf Wunsch an alle, deren E-Mail ...€¦ · 25/11/2018 · THE TRAVELINBG WILBURYS: Picture-Vinyl-LP THE TRAVELING WILBURYS VOL. 1. 1. 2018er McCARTNEY-Wiederveröffentlichungen:

Traveling Salesman Problem (TSP) - Algorithm Engineeringls11- · 2009. 12. 16. · Traveling Salesman Problem (TSP) (Symmetrisches) Travelling Salesman Problem Gegeben: n Städte

MANAGEMENT DIScUSSIoN & ANALySIS REPoRT 1. ANALySIS oF …€¦ · Members can accrue points while traveling on select flightsof our code share partner airlines. Moratorium on expiry

Olesja Aleinikau & Timo Dahlbüdding Praktikum Parallele Programmierung Travelling Salesman Problem (TSP) von Ihar Aleinikau UNIVERSITÄT HAMBURG FACHBEREICH

Traveling Salesman Problem - THI · PDF filereise die – entsprechend den Möglichkeiten der Heuristik – so kurz wie möglich und dabei so lang wie nötig ist

Das Travelling-Salesman-Problem oder das Problem des ...meiler/Schuelerseiten.dir/TBlaszkiewitz/TBlasz... · Bibliographische Beschreibung der Arbeit und Referat Thomas Blaßkiewitz

SchnelleRundreisen: Das Travelling-Salesman-Problem · 94 Martin Grötschel zeste Rundreisen zu ﬁnden. Wählen Siesich einige Städte aus und versuchen Sie, eine kürzeste Tourdurch

Entwurf kombinatorischer Schaltungen - ti.uni-due.de · Grundlagen der Technische Informatik Wintersemester 2018/19 Vorlesender: Dr. Ing. Frank Sill Torres 2. Review - Karnaugh-Veich

Kapitel 4 Traveling Salesman Problem (TSP) (Wiederholung aus Produktion und Logistik II) Vehicle Routing Problem (VRP)

• times@fcpotawatomi-nsn.gov • …Jul 08, 2016 · 4 | Potawatomi Traveling Times • July 15, 2016 Departments On Tuesday, June 28, 2016, the . Forest County Potawatomi (FCP)

V9 – 9 Variationen zum Travelling Salesman Problem · Sogenannte Kohonen-Karten über- tragen diese Modellvorstellung in die Rechnerwelt und können insbeson- dere Lösungen für

Two solvable cases of the Traveling Salesman …page.mi.fu-berlin.de/rote/Papers/pdf/Two+solvable+cases...Two solvable cases of the Traveling Salesman Problem G¨unter Rothe Dissertation

˘ ˇ ˆ˙˙˝origins.sese.asu.edu/ses405/Failure Reports/NEAR_Rendezvous_Burn… · The Near Earth Asteroid Rendezvous (NEAR) space-craft, after traveling for nearly 3 years, initiated

Digitaltechnikknmat/V/Alt/Dr%20K%94...4. Entwurf zweistufiger kombinatorischer Logik 5. Zieltechnologien und Technologieanpassung 6. Zeitliches Verhalten kombinatorischer Schaltnetze

Lösung des Travelling Salesman Problem mit Zeitfenstern ...tschnepp/Bachelor Thesis Schnepper.pdf · Lösung des Travelling Salesman Problem mit Zeitfenstern mittels Heuristiken