Der Algorithmus ist extrem aufwändig, weil dazu alle(!) möglichen Wegkombinationen durchgespielt werden.
Unter zwei Aspekten ist diese Situation sehr spannend:
Zum einen ist es eine der wichtigsten offenen Fragen der Informatik, bekannt unter dem Namen P/PN-Problem,
ob für die optimale Tour wirklich alle Möglichkeiten durchgerechnet werden müssen, oder ob es ein effizienteres Verfahren gibt.
Momentan sind wir daher für die optimale Lösung auf das Durchspielen aller Möglichkeiten angewiesen. Dies erfordert bei 18 Städten so viel Rechenzeit,
dass wir unseren Kooperationspartner, die Firma Mauve, gefragt haben, ob wir dazu deren Rechner benutzen dürfen. Wir durften – und warten seit nunmehr vielen Wochen gespannt auf das Ergebnis.
Das Programm rechnet sogar schon so lange, dass wir noch Düsseldorf und Paderborn unter den Bundesligastädten haben 🙂
Nur gut, dass Alex zusätzlich einen Algorithmus entwickelt hat, der bereits innerhalb einer halben Stunde zu einem recht guten Ergebnis kommt:
Wir starten natürlich in Dortmund und reisen erst einmal zum Niederrhein; unsere von Alex berechnete Route wird insgesamt genau 3347 Kilometer lang werden und führt uns der Reihe nach in folgende Stadien:
Borussia Dortmund
Borussia Mönchengladbach
FC Schalke 04
Fortuna Düsseldorf
1. FC Köln
1. FC Union Berlin
FC Bayern München
TSG 1899 Hoffenheim
Eintracht Frankfurt
1. FSV Mainz 05
Sport-Club Freiburg
FC Augsburg
RB Leipzig
Hertha BSC
VfL Wolfsburg
SV Werder Bremen
Bayer 04 Leverkusen
SC Paderborn 07
Borussia Dortmund
Aus informatischer Sicht bleibt jetzt noch abzuwarten, wie weit diese 3347 Kilomter von der optimalen Route abweichen.
Aus sportlicher Sicht ist es vielleicht sogar noch spannender, wann Düsseldorf und Paderborn wieder erstklassig sein werden.
Aus Sicht eines Informatiklehrers bin ich auf jeden Fall mit dem Projekt und meinen Schülern mehr als zufrieden.
Text und Bild: Zagorski
