Auswertung und Lösungen des Contests #04: "Reisekosten"

Zunächst einmal möchte ich allen Teilnehmern für ihre Einsendungen danken.
Sämtliche Einsendungen sowie das Testprogramm (inklusive Code::Blocks-Projekt) können hier heruntergeladen werden.

Lösungen

Generell kann man zwischen zwei verschiedenen Lösungen unterscheiden: unidirektionale Suche und bidirektionale Suche. Bei der unidirektionalen Suche wird nur versucht, vom Start zum Ziel zu kommen. Bei der bidirektionalen Suche wird gleichzeitig noch versucht, vom Ziel zum Start zu kommen, es werden also zwei Suchen nebeneinander durchgeführt. Sobald sie sich treffen, ist ein kürzester Weg gefunden. Die bidirektionale Suche ist ungefähr so schnell wie zwei unidirektionale Suchen mit der halben Suchtiefe, was besonders bei langen Wegen sehr viel schneller ist. Allerdings gehört ein gewisser Aufwand dazu, die beiden Suchen zu koordinieren und festzustellen, ob sie sich getroffen haben. Zudem ist das "*13"-Ticket nicht so einfach umzukehren, denn eine einfache Division durch 13 funktioniert nicht. Je nach Anzahl der Bahnhöfe und der aktuellen Bahnhofnummer kann ein Bahnhof 0, 1 oder 13 Vorgängerstationen haben. S.Seegel, TGGC und ich selbst verwenden eine bidirektionale Suche.

Um die als Nächstes zu besuchenden Bahnhöfe zu speichern, empfehlen sich 3 Vektoren. Darüber waren sich fast alle Teilnehmer einig. Jedoch findet man auch eine Lösung mit einer Prioritätswarteschlange und eine (nicht funktionierende) Lösung mit nur 2 Vektoren.

Weiterhin gibt es verschiedene Möglichkeiten, sich zu merken, welche Bahnhöfe man schon besucht hat. In Fällen mit einer großen Anzahl von Bahnhöfen und geringen Wegkosten wird nur ein kleiner Teil der Bahnhöfe besucht. Hier lohnt es sich, die besuchten Bahnhöfe in einer Menge (std::set) zu speichern oder jedem besuchten Bahnhof mittels einer Map (std::map) die Kosten bis dorthin zuzuordnen. Mit steigenden Wegkosten werden jedoch mehr Bahnhöfe besucht, so dass es sich lohnt, für jeden Bahnhof ein "besucht"-Flag zu speichern oder einen Eintrag in einem Kosten-Array. Einige haben für das "besucht"-Flag ein bool-Array verwendet, was jedoch nicht optimal ist, da ein bool-Wert im Normalfall 1 Byte einnimmt. Das anfängliche Leeren des Arrays beansprucht sowieso schon bereits eine nicht zu vernachlässigende Zeit (ich beschleunige das Leeren mittels SSE). Effektiver ist die Speicherung mittels eines Bitvektors, wo jedes Flag tatsächlich nur ein einziges Bit benötigt. TGGC kombiniert beide Varianten, indem er zunächst eine Map benutzt und dann an einem gewissen Punkt auf ein Array umsteigt.

Korrektheitstest

Beim Korrektheitstest wurden zunächst alle möglichen Kombinationen mit bis zu 100 Bahnhöfen getestet, anschließend noch 100 Zufallstests sowie 5 ausgewählte besonders teure Testfälle. Insgesamt sind das 338455 Tests.

Geschwindigkeitsmessung

Die Geschwindigkeitsmessung wurde auf dem AMD- und dem Intel-System durchgeführt. Dabei bekam jede Lösung mindestens 60 Sekunden Zeit, um einen "Testparcours" aus 1000 zufälligen Tests so oft wie möglich durchzuarbeiten. Daraus wurde dann die durchschnittlich benötigte Zeit sowie die Anzahl der Durchläufe pro Sekunde berechnet. Für beide Systeme wurden jeweils 100 Punkte entsprechend der Geschwindigkeit auf die Lösungen aufgeteilt.

Auswertung

AMD-System

Intel-System

Platzierung

Somit herzlichen Glückwunsch an S.Seegel, der nun schon zum zweiten Mal gewonnen hat (wie immer nehme ich außer Konkurrenz teil)!