|
|
| (Eine dazwischenliegende Version von einem anderen Benutzer wird nicht angezeigt) |
| Zeile 1: |
Zeile 1: |
| = Der Graph für das TSP = | | = Der Graph für das TSP = |
|
| |
|
| Der Graph wird über die Entfernungen der einzelnen Städte bei Verwendung des Bahnstreckennetzes errechnet. Dieses bewirkt eine erheblich einfachere Struktur des Graphen. Da das TSP jedoch nur auf vollständigen Graphen definiert ist, muss aus einem Graphen des Streckennetzes ein vollständiger Graph berechnet werden auf dem TSP gelöst werden kann.
| | Diese Daten sind veraltet. Aktuellste Informationen sind unter www.jahrdermathe.de zu finden. Logins für den Internen Bereich sind für alle KoMatiker bei den Webadmins zu erhalten. |
|
| |
|
| == Lösungsvorgehen ==
| | [[Kategorie:KOMA]] |
| Der Graph wird als eine Entfernungmatrix erstellt. Dabei sind stehts die minimalen Entfernungen von zwei unmittelbar verbundenen Städten die Kanten und die Kantengewichte die Entfernungen.
| |
| | |
| Durch Anwendung des APSP (All Pairs Shortest Path) kann daraus ein vollständiger Graph erstellt werden (z.B. Lösung durch Floyd-Warshall oder Johnson).
| |
| | |
| Auf dem so entstandenen Graph kann dann das TSP gelöst werden. Zur Lösung verwenden wir das Programm Concorde von William Cook ([http://www.tsp.gatech.edu/index.html]).
| |
| | |
| == Lösungen für einfaches Modell mit euklidischen Entfernungen ==
| |
| Der Graph ist sehr einfach zu erstellen, wenn nur euklidische Entfernungen betrachtet werden. Natürlich kann und wird sich vermutlich auch noch diese Lösung verändern, wenn die Bahnentfernungen als Entfernungskriterien verwendet werden. Als Lösung ergibt sich hierbei:
| |
| | |
| # Chemnitz
| |
| # Jena
| |
| # Halle
| |
| # Leipzig
| |
| # Magdeburg
| |
| # Braunschweig
| |
| # Hannover
| |
| # Hildesheim
| |
| # Kassel
| |
| # Göttingen
| |
| # Clausthal
| |
| # Ilmenau
| |
| # Bayreuth
| |
| # Passau
| |
| # Regensburg
| |
| # Eichstädt-Ingolstadt
| |
| # München
| |
| # Augsburg
| |
| # Erlangen
| |
| # Würzburg
| |
| # Ulm
| |
| # Konstanz
| |
| # Stuttgart
| |
| # Tübingen
| |
| # Karlsruhe
| |
| # Mannheim
| |
| # Heidelberg
| |
| # Darmstadt
| |
| # Mainz
| |
| # Frankfurt/Main
| |
| # Gießen
| |
| # Marburg
| |
| # Siegen
| |
| # Koblenz
| |
| # Saarbrücken
| |
| # Freiburg
| |
| # Kaiserslautern
| |
| # Trier
| |
| # Aachen
| |
| # Bonn
| |
| # Köln
| |
| # Wuppertal
| |
| # Düsseldorf
| |
| # Duisburg
| |
| # Bochum
| |
| # Dortmund
| |
| # Münster
| |
| # Osnabrück
| |
| # Paderborn
| |
| # Bielefeld
| |
| # Oldenburg
| |
| # Bremen
| |
| # Hamburg
| |
| # Flensburg
| |
| # Kiel
| |
| # Rostock
| |
| # Greifwald
| |
| # Berlin
| |
| # Potsdam
| |
| # Cottbus
| |
| # Zittau/Goerlitz
| |
| # Dresden
| |
| # Freiberg
| |
| # Mittweida
| |
Aktuelle Version vom 28. Mai 2010, 17:03 Uhr
Der Graph für das TSP[Bearbeiten]
Diese Daten sind veraltet. Aktuellste Informationen sind unter www.jahrdermathe.de zu finden. Logins für den Internen Bereich sind für alle KoMatiker bei den Webadmins zu erhalten.
