Skip to content. | Skip to navigation

Personal tools

Sections
You are here: Home / Publikationen / Informatik / Theorie und Praxis der automatischen Stundenplanerstellung / Diplomarbeit / html / Die interaktive Unterstützung

Die interaktive Unterstützung

next up previous contents
Next: Besonderheiten Up: Implementierung des Rahmenprogrammes Previous: Funktionalität und Implementierung des

Die interaktive Unterstützung

  Die Unterstützung beruht auf tiefenbeschränktem Backtracking. Es wird jeweils versucht, die nächste Stunde aus dem Zwischenspeicher in eines der aktuellen Tabellenfelder einzufügen und dann eine bestimmte Anzahl weiterer Stunden aus dem Zwischenspeicher zu verteilen. Hierbei werden Gruppen, die bereits Zeitstunden enthalten diesen direkt zugeteilt.gif Für die übrigen werden alle möglichen Zeitstunden durchprobiert. Wurde dies für alle Felder der momentanen Tabelle versucht, so wird das Level um 1 erhöht und der Vorgang erneut begonnen, wobei nun aber nur Felder betrachtet werden, die bei den niedrigeren Ebenen nicht aussortiert wurden.
Da sich die Qualität der Ratschläge mit der Dauer der Wartezeit verbessern soll, wird die interaktive Unterstützung immer dann aufgerufen, wenn der Benutzer gerade nichts tut. Das Visual C++-Framework bietet hierzu eine spezielle Funktion, die immer dann aufgerufen wird, wenn die Ereignisliste des Frameworks leer ist. Bei jedem Aufruf der Funktion wird ein weiteres Blatt des aktuellen Suchbaums überprüft, was mit sich bringt, daß dessen Position bis zum nächsten Aufruf gespeichert bleiben muß. Eine derartig feine Unterbrechung ist hier aber unumgänglich, damit die Reaktionszeit auf parallel ablaufende Benutzeraktivitäten nicht zu groß wird. Dies machte es ebenfalls notwendig, die Initialisierungsphase des Hilfssystems in zwei Schritte zu zerlegen.
Da die Zahl der möglichen Verteilungen weniger Schulstunden meist sehr groß ist, mußte darauf verzichtet werden, die gültigen Lösungen des jeweils vorangegangenen Levels zwischenzuspeichern, so daß die Suche jedesmal von neuem beginnen muß. Genauer gesagt bedeutet dies, daß beim Untersuchen eines Blattes der Tiefe k zwar bekannt ist, daß der zugehörige Knoten auf Ebene k-1 erreicht werden konnte, aber nicht auf welche Weise. Das folgende (kleine) Beispiel zeigt, wie die Funktion vor dem Einfügen der nächsten Gruppe in die linke Zeitstunde warnt, wobei dieses zwar keinen unmittelbaren Widerspruch auslöst, aber das Einfügen der folgenden Stunde unmöglich macht.

tex2html_wrap7166


next up previous contents
Next: Besonderheiten Up: Implementierung des Rahmenprogrammes Previous: Funktionalität und Implementierung des

(c) Martin Loehnertz 1999