Nach knapp drei Monaten Arbeit ist es vollbracht. Zusammen mit zwei Kommilitonen (Kai und Matthias) und einem Studenten von der FH Regensburg habe ich am informatiCup der Gesellschaft für Informatik teilgenommen. Wir haben uns für die Aufgabe “ATM” entschieden, bei der es darum ging, in einer gegebenen Stadt, die aus verschieden gewichteten Stadtteilen besteht, Geldautomaten so zu verteilen, dass wir eine möglichst hohe Gewichtung erreichen. Das Gewicht errechnet sich aus der jeweils von einem Automaten abgedeckten Fläche, die kreisförmig ist und einen festen Radius hat und dem Gewicht der überdeckten Stadtteile. Es ist nicht erlaubt, dass sich Automaten überdecken.

Visualisierung der Gewichtung.

Um das Problem (welches wahrscheinlich NP-Hart ist) zu lösen, haben wir verschiedene Algorithmen verwendet, die wir in zwei Gruppen aufgeteilt haben. Diese beiden Gruppen waren Eröffnungsalgorithmen und Optimierungsalgorithmen. Die Eröffnungsalgorithmen sollten erst einmal  eine möglichst gute Anfangsaufstellung finden, die dann verbessert werden kann. Dafür haben wir den Greedyalgorithmus und die Erstellung verteilter Positionen ohne Determinismus (weithin bekannt als Zufall) verwendet. Für die Optimierung haben wir dann mit simulierter Abkühlung und Tabusuche verwendet. Unsere Algorithemen sind sehr effektiv, schnell, präzise, flexibel und liefern sehr gute Ergebnisse. Wir waren manchmal selber erstaunt, welche Lösungen gefunden wurden.

Das Programm inklusive der Algorithmen und der Oberfläche haben wir in Java geschrieben. Das Programm, alle Quellen und Beispielrechnungen gibt’s auf der Website der GI.

Unser Code und Beispiele sind auf GitHub.

UPDATE: Gerade kam die E-mail rein, dass wir nach Bonn eingeladen wurden. Zur entscheidenden Endauswahl! Damit sind wir unter den besten 6 Teams. Und das, obwohl wir erst im 1. Semester sind. Wahnsinn… Überraschend…