Wettbewerb / Vergleich von Blockungsprogrammen
Moderator: wschrewe
- wschrewe
- Fachberater*in
- Beiträge: 1700
- Registriert: Dienstag 25. September 2018, 17:36
- Schulform: BK (Pensionär)
- Kontaktdaten:
Re: Wettbewerb / Vergleich von Blockungsprogrammen
Ich habe mal die Daten von Herrn Bartsch ergänzt und fehlerbereinigt. Mit den angehängten Textdateien kann eine funktionierende Blockung angelegt werden.
Ich habe mit dem neuen Algorithmus geblockt und nach 1 Min. 37 Sek. bei NV = 0 und KD = 4 abgebrochen. Die Vorgaben von Herrn Bartsch wurden dabei nicht ausgewertet.
Ich habe mit dem neuen Algorithmus geblockt und nach 1 Min. 37 Sek. bei NV = 0 und KD = 4 abgebrochen. Die Vorgaben von Herrn Bartsch wurden dabei nicht ausgewertet.
- Dateianhänge
-
- Blockung_Komplett.zip
- (10.92 KiB) 178-mal heruntergeladen
Mit freundlichen Grüßen
Walter Schrewe
"If all else fails, read the instructions" (Donald E. Knuth, letzter TeX - Hilfehinweis)
Walter Schrewe
"If all else fails, read the instructions" (Donald E. Knuth, letzter TeX - Hilfehinweis)
-
- Fachberater*in
- Beiträge: 321
- Registriert: Dienstag 4. Dezember 2018, 14:14
- Schulform: Gymnasium
Re: Wettbewerb / Vergleich von Blockungsprogrammen
... ich habe im ersten Beitrag die Datei "Wettbewerb.zip" hochgeladen. Diese werde ich in Zukunft mit den vorhandenen Testdaten ergänzen.
Die Datei enthält nun zusätzlich zum Ordner "EF_01" den Ordner "EF_02" (Blockung von Herrn Westphal) und den Ordner "EF_03" (Blockung von Herrn Friebe.
EF_01:
Ersetzt mit den korrigierten Daten von Herrn Schrewe. KD2 ist möglich bei NW0.
EF_02:
Mein Programm kommt in akzeptabler Zeit nur bis KD5. Vom Gefühl her müsste es viel besser gehen. Ggf. sind die Nebenbedingungen und die Schülerfixierungen aber nicht ganz ohne. (0 Nichtwähler)
EF_03:
Meiner Meinung nach ist das eine extrem schwere Blockung. Mein Algorithmus bleibt sehr oft bei KD8 bis KD14 hängen. Ganz selten findet das Programm dann doch noch KD5. (0 Nichtwähler)
Die Datei enthält nun zusätzlich zum Ordner "EF_01" den Ordner "EF_02" (Blockung von Herrn Westphal) und den Ordner "EF_03" (Blockung von Herrn Friebe.
EF_01:
Ersetzt mit den korrigierten Daten von Herrn Schrewe. KD2 ist möglich bei NW0.
EF_02:
Mein Programm kommt in akzeptabler Zeit nur bis KD5. Vom Gefühl her müsste es viel besser gehen. Ggf. sind die Nebenbedingungen und die Schülerfixierungen aber nicht ganz ohne. (0 Nichtwähler)
EF_03:
Meiner Meinung nach ist das eine extrem schwere Blockung. Mein Algorithmus bleibt sehr oft bei KD8 bis KD14 hängen. Ganz selten findet das Programm dann doch noch KD5. (0 Nichtwähler)
B. Bartsch
- wschrewe
- Fachberater*in
- Beiträge: 1700
- Registriert: Dienstag 25. September 2018, 17:36
- Schulform: BK (Pensionär)
- Kontaktdaten:
Re: Wettbewerb / Vergleich von Blockungsprogrammen
Bei EF_03 meldet mir Kurs, dass eine konfliktfreie Blockung nicht möglich ist, weil vier Schüler mehr als 12 Fächer gewählt haben:
Name23, Vorname23 (13 Fächer)
Name43, Vorname43 (13 Fächer)
Name47, Vorname47 (13 Fächer)
Name75, Vorname75 (13 Fächer)
??
Name23, Vorname23 (13 Fächer)
Name43, Vorname43 (13 Fächer)
Name47, Vorname47 (13 Fächer)
Name75, Vorname75 (13 Fächer)
??
Mit freundlichen Grüßen
Walter Schrewe
"If all else fails, read the instructions" (Donald E. Knuth, letzter TeX - Hilfehinweis)
Walter Schrewe
"If all else fails, read the instructions" (Donald E. Knuth, letzter TeX - Hilfehinweis)
-
- Fachberater*in
- Beiträge: 321
- Registriert: Dienstag 4. Dezember 2018, 14:14
- Schulform: Gymnasium
Re: Wettbewerb / Vergleich von Blockungsprogrammen
...es sollen ja auch 13 Schienen sein (s. A_VORGABEN.txt).
B. Bartsch
-
- Beiträge: 94
- Registriert: Sonntag 2. Dezember 2018, 19:55
- Schulform: Realschule
Re: Wettbewerb / Vergleich von Blockungsprogrammen
Danke.B. Bartsch hat geschrieben: ↑Freitag 12. Juni 2020, 23:15 EF_03:
Meiner Meinung nach ist das eine extrem schwere Blockung. Mein Algorithmus bleibt sehr oft bei KD8 bis KD14 hängen. Ganz selten findet das Programm dann doch noch KD5. (0 Nichtwähler)
Solche Datensätze können extrem hilfreich sein, insbesondere wenn man die Grund für so ein Verhalten versteht.
Daher wollte ich auch synthetische Tests machen, bei denen ich gezielt versuche bestimmte Besonderheiten einzubauen um auszumessen ob bzw. wie groß die Auswirkungen sind. Es hätte den Vorteil, dass man sofort den Grund weiß und besser abschätzen kann wie viel Einfluss die Besonderheit hat.
Aus dem Bereich Stundenplanung habe ich auch Datensätze, die extrem schwierig sind. Dort habe ich schon Datensätze mehrfach über 4 Wochen laufen lassen und keine Lösung gefunden. Interessanterweise habe ich denselben Datensatz in 1 von 1000 Fällen mit meiner CPU innerhalb von ~10 Minuten lösen können. Sprich: Es ist (zumindest bei meinem Algorithmus) effektiver nur kurz zu suchen.
Natürlich besteht die Gefahr, dass man bei zu kurzer Suchzeit nie eine Lösung finden wird, obwohl es Lösungen gibt. Daher kann ich nicht sagen genau sagen wie lange man mindestens bzw. höchstens suchen sollte. Das muss man etwas ausprobieren. Ich habe als Limit bei mir erstmal vorsichtige 15 Minuten vorgegeben. Wahrscheinlich muss/kann/sollte ich den Wert reduzieren.
Ich kann nicht in die Algorithmen von Kurs42, Kurs42_To_CNF, Untis, ... gucken (möchte ich auch nicht), aber ich habe anhand der grafischen Ausgabe dein Eindruck als wenn sie sogar deutlich schneller "neu starten". Oder täuscht das nur, weil ihre Algorithmen gelerntes Wissen mit in den Neustart nehmen?
-
- Fachberater*in
- Beiträge: 321
- Registriert: Dienstag 4. Dezember 2018, 14:14
- Schulform: Gymnasium
Re: Wettbewerb / Vergleich von Blockungsprogrammen
Der neue Algorithmus von Kurs42 startet oft neu, sieht man auch an der Prozentanzeige (für jeden Durchlauf).Ich kann nicht in die Algorithmen von Kurs42, Kurs42_To_CNF, Untis, ... gucken (möchte ich auch nicht), aber ich habe anhand der grafischen Ausgabe dein Eindruck als wenn sie sogar deutlich schneller "neu starten". Oder täuscht das nur, weil ihre Algorithmen gelerntes Wissen mit in den Neustart nehmen?
Kurs42_To_CNF kann beides. Ich berechne ohne Neustart zunächst KDs - ja nach Blockung - von 20 bis 10 (mit einem Thread). Danach wechsle ich zum Auto-Modus mit 8 Threads, diese starten nur dann neu, wenn ein UNSAT* (nicht lösbar) gefunden wurde, oder ein SAT (gelöst), dann mit der Vorgabe weniger KD zu versuchen.
*UNSAT heißt in meinem Auto-Modus nicht, dass das globale Problem unlösbar ist, denn im Auto-Modus fixiere ich zufällig entweder Kurse in Schienen oder Schüler in Kursen.
B. Bartsch
-
- Beiträge: 94
- Registriert: Sonntag 2. Dezember 2018, 19:55
- Schulform: Realschule
Re: Wettbewerb / Vergleich von Blockungsprogrammen
Ja, die Idee mit dem Übernehmen von Wissen in andere Threads hatte ich schon verstanden. Der Ansatz hat schon etwas. Probiere ich aus sobald ich auch mehrere Threads machen kann. Kann ich leider noch nicht effektiv selbst. Ich kann es nur "simulieren", indem ich das Programm einfach mehrfach öffne und parrallel laufen lassen. Das ist dann natülich ohne Übernahme von Wissen. Trotzdem empfehlenswert. (zumindest bei schweren Daten; bei (sehr) leichten Daten ist es unnötig.
Ich meinte die Frage bezogen auf einen einzigen Thread. Wenn man in Kurs42_To_CNF auf nur einem Thread rechnet, dann habe ich den Eindruck als wenn dort auch mehrfach neu gestartet wird. Ist das ein für den Algorithmus ein kompletter Neustart und der versucht das noch einmal von vorne oder nimmt der Wissen mit in den zweiten Durchgang? Oder verstehe ich die Anzeige falsch und es ist nur ein "Zwischenbericht" und der Algorithmus macht an genau der Stelle weiter wo er gerade ist, oder er geht nur X Schritte zurück (behält also Wissen).
Ich meinte die Frage bezogen auf einen einzigen Thread. Wenn man in Kurs42_To_CNF auf nur einem Thread rechnet, dann habe ich den Eindruck als wenn dort auch mehrfach neu gestartet wird. Ist das ein für den Algorithmus ein kompletter Neustart und der versucht das noch einmal von vorne oder nimmt der Wissen mit in den zweiten Durchgang? Oder verstehe ich die Anzeige falsch und es ist nur ein "Zwischenbericht" und der Algorithmus macht an genau der Stelle weiter wo er gerade ist, oder er geht nur X Schritte zurück (behält also Wissen).
-
- Fachberater*in
- Beiträge: 321
- Registriert: Dienstag 4. Dezember 2018, 14:14
- Schulform: Gymnasium
Re: Wettbewerb / Vergleich von Blockungsprogrammen
Es wird ja im Hintergrund der SAT Solver aufgerufen, dieser startet extrem oft die Berechnungen neu.
B. Bartsch
-
- Beiträge: 94
- Registriert: Sonntag 2. Dezember 2018, 19:55
- Schulform: Realschule
Re: Wettbewerb / Vergleich von Blockungsprogrammen
Kann ich bestätigen. Ist bei mir ähnlich.B. Bartsch hat geschrieben: ↑Freitag 12. Juni 2020, 23:15 EF_03:
[...] Mein Algorithmus bleibt sehr oft bei KD8 bis KD14 hängen. Ganz selten findet das Programm dann doch noch KD5. (0 Nichtwähler)
Ich habe es 10 mal mit KD9 gelöst und da scheint irgendetwas besonderes zu sein.
Mein schnellstes war in 8 Sekunden. Das langsamste in 532 Sekunden. Im Schnitt 165 Sekunden.
Das hängt dort ab und zu ganz deutlich.
Das ist intressant. Gucke ich mir in den Ferien in Ruhe an.
Ich vermute die fixierten Kurse mit den Extravorgaben für minimale und maximale Kursgrößen sind die Koop Kurse, oder?
Wäre es nicht sinnvoll, wenn man da wirklich die Koopschüler fixiert, damit die Kursdifferenzen über alle Kurse gleichmäßiger verteilt werden können?
Oder ist das Absicht und als Ausgleich für die Lehrer gedacht, weil die an zwei Konferenzen anwesend sein müssen?
-
- Fachberater*in
- Beiträge: 321
- Registriert: Dienstag 4. Dezember 2018, 14:14
- Schulform: Gymnasium
Re: Wettbewerb / Vergleich von Blockungsprogrammen
jaIch vermute die fixierten Kurse mit den Extravorgaben für minimale und maximale Kursgrößen sind die Koop Kurse, oder?
Man könnte Dummy Schüler in die Kurse einfügen UND fixieren, dann würde man max. SuS für den Kurs nicht benötigen.Wäre es nicht sinnvoll, wenn man da wirklich die Koopschüler fixiert, damit die Kursdifferenzen über alle Kurse gleichmäßiger verteilt werden können?
Das verstehe ich nicht.Oder ist das Absicht und als Ausgleich für die Lehrer gedacht, weil die an zwei Konferenzen anwesend sein müssen?
B. Bartsch