Studenplan-Algorithmus
-
hmmmmmm schrieb:
Mit welchen Algorithmen arbeiten Programme, die Stundenpläne (für Schulen) erstellen?
Wie Sepp schon gesagt hat, gibt es sehr viele Ansätze.
Was im Umkehrschluss heißt, dass es keinen Algorithmus im engeren Sinne gibt, den man in der Praxis einsetzen könnte.
Die Algorithmen, die die optimale Lösung liefern, versagen bei der Problemgröße uns -komplexität, die in der Praxis relevant ist.
Für Zuordnungsprobleme gibt es nur wenige Algorithmen mit erträglichem Laufzeitverhalten, aber die sind dann nur für Zwergschulen tauglich.Entsprechend werden Heuristiken eingesetzt, deren Lösungen erfahrungsgemäß nicht schlecht sind, ohne dass sie dabei wirklich beste Lösung finden.
Bei der Stundenplanermittlung kommt als Schwierigkeit hinzu, dass es konkurrierende Teilziele (wenig Freistunden für Schüler, wenig Freistunden für Lehrer, wenig Raumwechsel, wenig Nachmittagsunterricht) gibt, die man gewichtigen muss.
Von daher gibt es bei der Disposition eigentlich weniger Unterstützung durch Intelligenz sondern durch Darstellung und Prüfung.
Ciao, Allesquatsch
-
Allesquatsch schrieb:
hmmmmmm schrieb:
Mit welchen Algorithmen arbeiten Programme, die Stundenpläne (für Schulen) erstellen?
Wie Sepp schon gesagt hat, gibt es sehr viele Ansätze.
Was im Umkehrschluss heißt, dass es keinen Algorithmus im engeren Sinne gibt, den man in der Praxis einsetzen könnte.
Die Algorithmen, die die optimale Lösung liefern, versagen bei der Problemgröße uns -komplexität, die in der Praxis relevant ist.
Für Zuordnungsprobleme gibt es nur wenige Algorithmen mit erträglichem Laufzeitverhalten, aber die sind dann nur für Zwergschulen tauglich.Entsprechend werden Heuristiken eingesetzt, deren Lösungen erfahrungsgemäß nicht schlecht sind, ohne dass sie dabei wirklich beste Lösung finden.
Bei der Stundenplanermittlung kommt als Schwierigkeit hinzu, dass es konkurrierende Teilziele (wenig Freistunden für Schüler, wenig Freistunden für Lehrer, wenig Raumwechsel, wenig Nachmittagsunterricht) gibt, die man gewichtigen muss.
Von daher gibt es bei der Disposition eigentlich weniger Unterstützung durch Intelligenz sondern durch Darstellung und Prüfung.
Ciao, Allesquatsch
Habe ich das richtig verstanden?? In Zeiten, wo man das Klima über Jahrzehnte vorausberechnen kann, kann man kein Stundenplanprogramm erstellen, das, sagen wir einmal für ein Gymnasium mit 50 Klasseneinheiten, einen Stundenplan erstellen kann....
-
Richtig. Keinen optimalen Stundenplan. Nur gute Stundenpläne.
-
Ein Beispiel mit Code.
-
Bin erstaunt schrieb:
In Zeiten, wo man das Klima über Jahrzehnte vorausberechnen kann,
Na, jeder weiß, wie viel Tage eine Wettervorhersage reicht.
Auch hier hatte man früher die Vorstellung, dass noch mehr Messwerte und schnellere Rechner dazu führen werden, dass man die Wettervorhersage perfektioniert.
Tatsächlich waren die Verbesserungen marginal.Bin erstaunt schrieb:
kann man kein Stundenplanprogramm erstellen, das, sagen wir einmal für ein Gymnasium mit 50 Klasseneinheiten, einen Stundenplan erstellen kann....
Nun, die Herausforderung besteht darin, dass man nicht "einen" Stundenplan sucht, sondern gleich noch einen Rattenschwanz von Randbedingungen und Optimierungszielen einhalten will.
Und damit steigt die Komplexität des Problems halt so stark, dass die Optimierungsalgorithmen von Laufzeit- oder Speicherbedarf nicht zu den technischen Möglichkeiten passen.
Bei Wetter- und Klimaprognosen werden deshalb auch gigantische Rechenkapazitäten eingesetzt.
Für Stundenpläne ist Optimalität in der Praxis nicht notwendig.Bei solchen Problemen setzt man meistens eine prioritätsregelgestützte Heuristik für zulässige Ausgangssituationen ein und versucht dann durch kleinere Veränderungen noch etwas besser zu werden.
Der Vorteil des Computers ist halt die schnelle Prüfung aller Randbedingungen und Bewertung der Zielfaktoren.
Ciao, Allesquatsch
-
hmmmmmm schrieb:
Mit welchen Algorithmen arbeiten Programme, die Stundenpläne (für Schulen) erstellen?
Mit Progol, das eignet sich dafür hervorragend.
-
While(nicht_fertig()) basteln.next();
-
B4ndit schrieb:
While(nicht_fertig()) basteln.next();... als der Vorschlag mit PROLOG kam.
-
... als der Vorschlag mit PROLOG kam.
Und ich habe mich schon gewundert: http://en.wikipedia.org/wiki/PROGOL . Lernen aus Beispielen?
-
Also brute force?
-
hmmmmmmmmmmm schrieb:
Also brute force?
Wäre die normale Lösungsstrategie von PROLOG, einfach im Backtracking durch den Lösungsbaum zu klettern. Allerdings wird in der Praxis dann die Suchtiefe beschränkt und schlecht abgeschätzte Teilbäume ausgelassen.
Ciao, Allesquatsch
-
knivil schrieb:
... als der Vorschlag mit PROLOG kam.
Und ich habe mich schon gewundert: http://en.wikipedia.org/wiki/PROGOL . Lernen aus Beispielen?