- Platz 1: meilz381 (39,226 Punkte)
- Platz 2: zelosos (39,2062 Punkte)
- Platz 3: klux2 (38,8042 Punkte)
- Platz 4: Syndesi (14,9068 Punkte)
!!! Bitte konntaktiert mich per Mail, damit wir einen Termin für die Preisüberreichung vereinbaren können. !!! Die Mail-Addresse entnehmt ihr der Infomail vom 05.07.2018.
Die genauen Werte könnt ihr dem Bild entnehmen. Ihr findet dort genaue Angaben über die einzelnen Runden:
- genutzter Seed,
- Gesammtscore,
- verbleibende Zeit des 209-Städtetest und
- Länge der Route beim 209-Städtetest.
Das "traveler salesman problem" (Handelsreisender Problem) gehört in die Gruppe der NP-Problemen. Das heißt um die beste Lösung zu finden, müsste man alle Lösungen ausprobieren. Das ist aber aufgrund der immensen Größe an möglichen Lösungen schier unmöglich (mit derzeitiger Technik). Man kann jedoch annäherungsweise ein gutes, bzw. sehr gutes Ergebnis erzielen.
Stellt euch vor ihr wollt 10 Städte bereisen. In welcher Reihenfolge ihr die Städte besucht ist euch egal; Hauptsache ihr wart in jeder Stadt einmal. Um Sprittgeld zu sparen wollt ihr die kürzeste Strecke fahren und doch alle Städte besuchen. Welche Route müsst ihr dafür nehmen?
Die Städte werden im Programm durch zufällige Punkte repräsentiert. Die Route verfasst man durch einzelne Linien zwischen diesen Punkten. In der Klasse Reisender innerhalb der Funktion berechneRoute() wird die Route aufgestellt. Dort sollt ihr eure Lösung erstellen.
Damit der Vergleich zwischen den einzelnen Teilnehmern vergleichbar bleibt, werden Zufallszahlen mit einem Seed erzeugt. Damit werden 10 unterschiedliche Städtekonstellationen erzeugt. Diese sind wie folgt aufgeteilt:
- 6x 16 Städte
- 3x 40 Städte
- 1x 209 Städte
Für die Berechnung der Route existiert ein Zeitlimit. Dieses wird wie folgt berechnet:
Zeitlimit = Städteanzahl * Städteanzahl * 6 Millisekunden
Das Berechnen aller Routen darf somit maximal 5 Minuten dauern. Beim Überschreiten des Zeitlimits wird das Ergebnis nicht gezählt. Nach der Deadline werden alle eingereichten Lösungen auf dem gleichen Computer mit dem gleichen Startseed getestet. Sollten das Ergebnis knapp ausfallen, so wird mit weiteren Seeds ein Durchschnitt errechnet um den endgültigen Gewinner zu ermitteln.
Eure abgegebene Lösung wird mit einem Score bewertet. Der Score setzt sich aus zwei Faktoren zusammen:
- Wie gut ist euer gefundener Weg gegenüber einem zufällig Gewählten?
- Wie viel Zeit von eurer Rechenzeit ist übrig.
Generell gilt:
- Ein besserer Pfad wird besser bewertet, als wenig Rechenzeit verbraucht.
- Je mehr Städte eine Route beinhaltet, desto mehr Punkte können erreicht werden.
Die genaue Formel findet ihr im Source Code. Sollte nicht jede Stadt besucht, keine zusammenhängende Route gefunden oder eure Rechenzeit überschritten sein, so wird diese Route mit 0 bewertet. Der Score aller 10 Routen wird aufsummiert und bildet euren Endscore.
Lösungen können bis zum 30.09.2018 23:59:59.9999 abgegeben werden.
- Platz: Raspberry Pi Kit
- Platz: USB Stick 32GB
- Platz: USB Stick 8GB
und für Teilnehmer, die besser sind als der Zufall einen Sticker dieser Challenge.
Preise können nur an Studenten der HSMW vergeben werden.
Vielen Dank an die StuRa der HSMW für das Sponsoring der Preise.
- Bestehende Funktionen dürfen nicht verändert werden.
- Ausnahme von Regel 1 ist die Funktion berechneRoute() der Klasse Reisender.
- Funktionen und Klassen dürfen nach Belieben hinzugefügt werden.
- Die Abgabe erfolgt ausschließlich als Fork über github. Bitte erzeugt auch gleich eine jar-Datei.
- Strengt euch selber an. Eine Kopie einer bestehenden Lösung als Abgabe führt zwangsläufig zur Disqualifikation.
- Die Liste der Städte darf nicht verändert werden.
- Nutzt die euch zur Verfügung gestellte Zeit. Eine bessere Lösung erhöht den Score wesentlich stärker, als verbleibende freie Zeit.
- Die Testmaschine besitzt mehrere Prozessorkerne. Nutzt die Rechenleistung.
- Optimiert wo es geht. Vielleicht genügt eine grobe Approximation von sehr komplexen und häufig aufgerufenen Berechnungen. Oft hilft es auch häufig berechnete Ergebnisse zu speichern.
- Variiert den Startpunkt. Die Route muss nicht bei der ersten Stadt beginnen. Vielleicht ist eine andere Stadt als Startpunkt besser.
- Nutzt bereits existierendes Wissen. Wenn ihr nach Verbesserungen für eure Berechnung sucht findet ihr in der Literatur sicherlich Hilfe oder Algorithmen.
- Kommentiert schwer zu verstehende Source-Code-Passagen. Es hilft euch später.
- Berechnet mit weniger Städten die optimale Lösung und schaut, wie weit eure Lösung von dieser entfernt ist.
- Schaut euch die graphische Ausgabe eurer Route an. Wo stellt ihr Verbesserungsmöglichkeiten fest?
- Experimentiert. Neue Ideen kommen schnell zusammen. Probiert sie aus, passt sie an, optimiert sie, aber ärgert euch nicht, falls ihr gescheiterte Experimente verwerft. Das gewonnene Wissen bringt euch immer weiter an Ziel.