Bearbeiten von „Jahr der Mathematik/Graph“

Aus KIF
Warnung: Du bist nicht angemeldet. Deine IP-Adresse wird bei Bearbeitungen öffentlich sichtbar. Melde dich an oder erstelle ein Benutzerkonto, damit Bearbeitungen deinem Benutzernamen zugeordnet werden. Ein eigenes Benutzerkonto hat eine ganze Reihe von Vorteilen.

Die Bearbeitung kann rückgängig gemacht werden. Bitte prüfe den Vergleich unten, um sicherzustellen, dass du dies tun möchtest, und veröffentliche dann unten deine Änderungen, um die Bearbeitung rückgängig zu machen.

Aktuelle Version Dein Text
Zeile 1: Zeile 1:
= Der Graph für das TSP =
= Der Graph für das TSP =


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.
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.


[[Kategorie:KOMA]]
== Lösungsvorgehen ==
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
Bitte kopiere keine Webseiten, die nicht deine eigenen sind, benutze keine urheberrechtlich geschützten Werke ohne Erlaubnis des Urhebers!
Du gibst uns hiermit deine Zusage, dass du den Text selbst verfasst hast, dass der Text Allgemeingut (public domain) ist oder dass der Urheber seine Zustimmung gegeben hat. Falls dieser Text bereits woanders veröffentlicht wurde, weise bitte auf der Diskussionsseite darauf hin. Bitte beachte, dass alle KIF-Beiträge automatisch unter der „Namensnennung-Weitergabe unter gleichen Bedingungen 2.5 “ stehen (siehe KIF:Urheberrechte für Einzelheiten). Falls du nicht möchtest, dass deine Arbeit hier von anderen verändert und verbreitet wird, dann klicke nicht auf „Seite speichern“.
Abbrechen Bearbeitungshilfe (wird in einem neuen Fenster geöffnet)
Abgerufen von „https://wiki.kif.rocks/wiki/Jahr_der_Mathematik/Graph“