Studenplan-Algorithmus
-
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?