Tag Archives: algorithm

IT explained

What is a blockchain actually?

 

Well, looks like I wanted to publish this somewhere else:

https://medium.com/@mathias.c.frey/what-is-a-blockchain-actually-fcd7f9721bd1

hacks

Die Tetris-Maschine

Der innerste Kern meiner Tätigkeit als Softwareentwickler ist die Erschaffung von Algorithmen. Dass das deutlich spannender sein kann als es klingt, will ich anhand eines aktuellen Projekts zeigen.

Beginnen wir mit einer Aufgabe: Gegeben ist die dargestellte Auslastung von vier Hörsälen. Es soll nun eine weitere Veranstaltung zwischen 13:00 und 14:00 (blau markiert) gebucht werden – welcher Raum ist nicht nur verfügbar, sondern auch optimal passend?

In welchem Raum soll der gewünschte Termin (13:00 bis 14:00) untergebracht werden?

Als Algorithmen werden in der Informatik Handlungsanweisungen zur Lösung eines Problems verstanden. Algorithmen können so etwa als Kochrezepte für Computerprogramme verstanden werden. Sie berechnen Manager-Boni, kümmern sich bei Word um die Rechtschreibkorrektur, twittern Aktienkurse oder – wie in meinem Fall – verhelfen der WU künftig zu einer optimierten Ausnutzung der Ressource Raum.

Algorithmisches Denken ist die Umkehrung von Schul-Mathematik. Beim Programmieren ist die Lösung bekannt, aber es gilt den Weg dorthin zu entdecken.

Das Teaching Center am Campus WU: Stählerner Schauplatz für Raumbuchungs-Tetris im XXL-Format. Mathias, 2012.

Jedenfalls: Bei unserem Re-Write der Raumverwaltung für den Campus WU sind wir mit einigen, höchst spannenden Anforderungen konfrontiert: Raumbuchungen sollen künftig automatisch und optimal durchgeführt werden, den Administratoren bleibt allerdings jedwede Flexibilität erhalten. Die Software kümmert sich dabei um Studien- wie Stundenpläne, um Verfügbarkeit der Lehrenden und “Extrawürschteln” ebenso, wie um Minimierung von Buchungslücken oder Reduktion unnötigen Reinigungsaufwands aufgrund zu vieler, “angepatzter” Hörsäle. Die Ressourcen sollen flexibel verfügbar sein (Stichwort dynamische Lagerhaltung), ein allzu häufiger Ortswechsel macht Studierende wie Lehrende aber wohl kaum glücklich.

Wir benötigen daher wieder einmal den “Do what I want“-Button:

       +-----------------+
       |                 |
       | DO WHAT I WANT  |
       |                 |
       +-----------------+
Button, der in jeder Software genau 
das tut, was der User will. 
(Grobkonzept)

Von der Idee zum Algorithmus

Die Aufgabenstellung lautet demnach:

  • Liefere für eine Serie von Terminen (z.B.: ein ganzes Semester) Buchungsvorschläge
  • innerhalb der angefragten Raumkategorie,
  • versuche dabei die gewünschten Zeiten zu erfüllen,
  • d.h. immer dieselbe Beginnzeit zu ermöglichen,
  • vermeide außerdem Raumwechsel,
  • aber vermeide noch viel mehr den Wechsel von Gebäuden.
  • Beachte, dass Buchungen nahtlos aufeinanderfolgen sollten.
  • Entstehen dennoch Lücken, so sind z.B.: 30 Minuten sehr schlecht, weil dieser Zeitraum sicher verloren ist,
  • 90 Minuten hingegen sind gar nicht so schlimm, weil ja noch etwas reinpassen könnte.
  • Bereits “angepatzte” Räume sind leeren vorzuziehen, weil dadurch der Reinigungsaufwand verkleinert wird.
ggg
Geistreiche Bilder vom Entstehungsprozess des Algorithmus. (…)

 

Die Grenzen der Berechenbarkeit

Ein naiver Lösungsansatz wäre nun, alle Möglichkeiten zu versuchen und die beste zu wählen. (Tatsächlich funktionieren viele Algorithmen nach diesem Prinzip.) In diesem Fall bekommen wir aber ein Problem mit der Dimension der Aufgabe:

Will etwa jemand an acht Montagen irgendwann zwischen 9:00 und 12:00 eine zweistündige Lehrveranstaltung abhalten, so ergeben sich (zu) viele Buchungsmöglichkeiten. Entlang eines 15-minütigen Rasters erhalten wir zunächst fünf mögliche Beginnzeiten (9:00, 9:15, 9:30, 9:45, 10:00). Diese fünf Beginnzeiten über rund 50 gleichwertige Seminarräume an acht Montagen ergeben acht mal fünf mal 50 – also zweitausend – Einzelmöglichkeiten. Die Berechnung der Kombinationsmöglichkeiten ergibt 15 Quintillionen [sic – 250hoch8 – eine 15 mit 18 Nullen]!

Wir reden allerdings nicht nur von einer Veranstaltung, sondern von knapp 4000 jährlich mit rund 35000 Einzelterminen – Tendenz Dank erweiterter Buchungsmöglichkeit für Mitarbeiter und Studierende stark steigend. Selbst wenn ein leistungsfähiger Rechner eine Milliarde Kombinationen pro Sekunde ausprobieren würde, wäre die erste Raumbuchung erst nach knapp 500 Jahren fertig…

Tetris

Glücklicherweise gibt es Tetris! Ähnlich wie bei den von oben fallenden Steinen kommen auch die Buchungswünsche Schritt für Schritt herein. Jede Buchung muss auf die jeweils aktuelle Belegung Rücksicht nehmen, kümmert sich aber nicht um das, was noch kommt. Genauso wie bei Tetris ist es auch bei Raumbuchungen sinnvoll, Lücken bestmöglich zu füllen, oder doch für passgenaue Steine in naher Zukunft frei zu halten.

Tetris-Klon von Nintendo: Dr. Mario. Aufgrund unseres akademischen Kontexts an der WU die wohl bessere Analogie.

Die Matrix

Tetris-Analogie hin oder her, noch besteht das Problem der zu vielen Lösungen. Manchmal hilft es, die Aufgabenstellung in kleine Teile zu trennen, das Problem zu abstrahieren, sich typische Situationen aber vor allem auch Grenzfälle (corner cases) zu überlegen.

Eine Terminserie zu unterschiedlichen Beginnzeiten, in Gebäuden und darin enthaltenen Räumen entspricht einer vierdimensionalen Matrix, so einer Art Excel-Tabelle, wo in jeder Zelle nochmal eine Tabelle enthalten ist. (Keine Sorge, so etwas kann auch ich mir nicht wirklich vorstellen.)

Die Einträge in dieser Matrix sind jedenfalls:

  • pro Termin
  • pro Beginnzeit
  • pro Gebäude
  • jede verfügbare Raumnummer
  • mit Bewertung der Passgenauigkeit

Die Passgenauigkeit beträgt 1, wenn der Raum einfach frei ist, 0 wenn er gebucht ist. Sollte ein Termin nahtlos reinpassen, erhöht sich der Wert über 1, bleiben Lücken, so bekommt der Raum Strafabzüge. Die Datenstruktur sieht früher oder später so aus:

{Termin1: {'12:00': {Gebaeude1: {Raum1: 0.47250000000000003, Raum2: 1.6}}},
 Termin2: {'12:00': {Gebaeude2: {Raum5: 1},
               Gebaeude1: {Raum1: 1,
                           Raum2: 1,
                           Raum3: 1,
                           Raum4: 1}}},
 Termin3: {'12:00': {Gebaeude1: {Raum1: 2, Raum2: 2}}},
 Termin4: {'12:00': {Gebaeude2: {Raum5: 1},
               Gebaeude1: {Raum1: 2,
                           Raum2: 2,
                           Raum3: 1,
                           Raum4: 1}}},
 Termin5: {'12:00': {Gebaeude2: {Raum5: 1},
               Gebaeude1: {Raum1: 0.45,
                           Raum2: 0.3375,
                           Raum3: 1,
                           Raum4: 1}}},
 Termin6: {'12:00': {Gebaeude1: {Raum2: 0.45, Raum3: 1, Raum4: 1}}},
 Termin7: {'12:00': {Gebaeude2: {Raum5: 1},
               Gebaeude1: {Raum1: 1, Raum3: 1, Raum4: 1}}}}

Die optimale Buchung

Die beste Lösung findet man nun nicht durch stumpfsinniges Ausprobieren, sondern durch geschicktes Durchschreiten der Datenstruktur. Der Lösungsweg lautet:

FÜR jede Terminanfrage    
  FÜR jede Beginnzeit gereiht nach Häufigkeit terminunabhängig
    FÜR jedes Gebäude gereiht nach Häufigkeit in Beginnzeit
       FÜR jeden Raum gereiht nach Passgenauigkeit in Beginnzeit
         VERSUCHE zu buchen
         ODER gehe weiter

Die Lösung der eingangs gestellten Aufgabe lautet übrigens “Raum B”. Oder wenn Sie zufällig ein Algorithmus sind:

{1: {'12:00': {123456789: {66778801: 0.47250000000000003, 66778802: 1.6}}}}

Übrigens: Geschafft in 0.7 Sekunden anstatt von 500 Jahren.

tltr;

Raumbuchen ist wie Tetris-Spielen; Excel kennt zum Glück keine Tabellen in Zellen.