In diesem Abschnitt finden Sie Informationen zu den, in der Schulverwaltung
verwendeten Stundenplanalgorithmen.
Spezielle Informationen zur Version 1.2BETA2 befinden sich im Abschnitt
2 dieser Dokumentation.
4.1. Allgemeines
- Im Folgenden stelle ich die Algorithmen mit ihren Vor- und Nachteilen
im einzelnen vor. Dabei gehe ich von meinen eigenen Erfahrungswerten aus.
Als Grundlage dienten dabei 5 Klassen.
- Die genaue Arbeitsweise der Algorithmen werde ich in der nächsten
Zeit auf meine Homepage stellen.
- Bei den randomisierten Algorithmen habe ich die, von Borland implementierte
Funktion, übernommen. Leider liefert diese zum einen nicht besonders
gute Zufallswerte und zum anderen gibt sie nach jedem Start des Programms
genau dieselben Werte, wie schon nach dem letzten Programmstart aus. Kurioser
Weise sorgt dieses Verhalten für teilweise erstaunlich gute - und
sogar reproduzierbare - Ergebnisse (auf meinen Testdaten wohlgemerkt).
Möchten Sie ein anderes Ergebnis erhalten, sollten Sie die Algorithmen
direkt nacheinander starten und dabei die Schulverwaltung nicht beenden.
4.2. Backtracking-Algorithmus
Vorteile:
+ schnell
+ relativ gute Ergebnisse
+ übernimmt bereits vorgegebene Dauertermine
Nachteile:
- liefert kein optimales Ergebnis
- Freistunden können im Ergebnis vorkommen
Beschreibung:
Der Backtracking-Algorithmus geht "Greedy" vor, d.h. er verteilt nacheinander
für jede Klasse die jeweiligen Stunden, genau in der Reihenfolge,
wie sie im Curriculum angegeben wurden.
4.3. Randomisierter-Tetris-Algorithmus
Vorteile:
+ relativ gute Ergebnisse (teilweise besser als Backtracking)
+ schnell
+ übernimmt bereits vorgegebene Dauertermine
Nachteile:
- (zu diesem Zeitpunkt) keine Beachtung von Doppelstunden, bzw. das
mehrfache Vorkommen von Terminen an einem Tag bleibt unberücksichtigt
- gibt in einigen Fällen keine Lösung aus (ist aber endlich)
Beschreibung:
Dieser Algorithmus sollte einmal zur Probe gestartet werden. Entweder
ist das Ergebnis gut oder man kann es verwerfen. Sollte der Algorithmus
keine Lösung ausgeben, sollten Sie ihn erneut starten.
Insbesondere dieser Algorithmus hat, was die Qualität der Ausgabe
betrifft, noch Verbesserungspotential.
4.4. Brettspiel-Algorithmus (ohne Bedingungen)
Vorteile:
+ Geschwindigkeit liegt im Mittelfeld
+ Gute Ergebnisse
Nachteile:
- liefert Lücken und berücksichtigt keine "Doppelstunden"
- berücksichtigt keine vorgegebenen Termine
- es gibt Situationen, in denen der Algorithmus nicht endlich ist
Beschreibung:
Die Brettspielalgorithmen gehen ungefähr so vor, wie es der "Mensch"
machen würde: er "sucht" einfach eine Lösung.
Bei dieser Variante gelten keine Bedingungen (sie sollte daher nur
dann eingesetzt werden, wenn Letztere nicht benötigt werden).
Da diese Algorithmen nicht besonders effizient von mir implementiert
wurden (aus Zeitmangel), haben die Brettspielalgorithmen eine ziemlich
hohe Laufzeit. So benötigt dieser Algorithmus auf einem Athlon 500
ca. 5 Sekunden bei 5 Klassen.
Ein weiteres Problem ist die, in einigen Fällen "unendlich" lange
Laufzeit. Aus diesem Grund ist es jederzeit möglich, den Algorithmus
mit einem Klick auf "Abbrechen" anzuhalten. Der aktuelle "Berechnungstand"
wird dann ausgegeben.
4.5. Brettspiel-Algorithmus (keine Freistunden)
Vorteile:
+ sehr gute Ergebnisse
Nachteile:
- (zur Zeit) relativ lange Laufzeit
- keine Berücksichtigung von vorgegebenen Terminen
- keine Beachtung von Doppelstunden
- es gibt Situationen, in denen der Algorithmus nicht endlich ist
Beschreibung:
Dieser Algorithmus arbeitet analog zu 4.4., nur dass nun keine Freistunden
mehr erlaubt werden. Dies erhöht die Laufzeit noch einmal erheblich.
Auf einem Athlon 500 benötigt der Algorithmus bei 5 Klassen ca. 30
Sekunden. Ich möchte betonen, dass diese Laufzeit zu 50% von meiner
schlechten Implementierung abhängt - dort ist also noch Verbesserungspotential
vorhanden.
Erstaunlicherweise liefert dieser Algorithmus, obwohl er nicht auf
irgendwelche Doppelstunden-Konstellationen achtet, Stundenpläne, die
dies berücksichtigen (dies gilt für meine Test-Daten - wie dies
in der Praxis aussieht, kann ich leider nicht sagen - hier wäre ich
für Informationen dankbar).
4.6. Brettspiel-Algorithmus (alle Bedingungen)
Vorteile:
+ sehr gute Ergebnisse
+ achtet auch auf Doppelstunden
Nachteile:
- (zur Zeit) relativ monströse Laufzeit
- keine Berücksichtigung von vorgegebenen Terminen
- es gibt Situationen, in denen der Algorithmus nicht endlich ist
Beschreibung:
Der Algorithmus arbeitet analog zu 4.5., mit dem Unteschied, dass nun
auch auf Doppelstunden geachtet wird. Dadurch erhöht sich die Laufzeit
noch einmal: Auf einem Athlon 500 bei 5 Klassen benötigte der Algorithmus
im günstigsten Fall 5 Minuten. Allerdings sollte ich nicht verschweigen,
dass das Ergebnis die anderen
Algorithmen geschlagen hat.
4.7. Bemerkungen zu den Brettspielalgorithmen:
Während die Berechnung der Stundenpläne läuft, werden Informationen angezeigt. Auch wenn hier scheinbar für alle Klassen angezeigt wird, dass die noch einzuordnende Fächeranzahl 0 ist, so stimmt dies nicht immer. Die Berechnungen sind erst beendet, wenn dies ausdrücklich angezeigt wird, bzw. sich das Fenster automatisch schließt.
4.8. Schlussbemerkung
Falls Sie andere Stundenplan-Algorithmen kennen, greife ich diese gerne
auf (sofern sie nicht durch ein Patent o.ä. geschützt sind).
Die Arbeitsweise meiner Algorithmen werde ich in der nächsten Zeit
auf meine Homepage stellen.