Ich habe vor ein paar Tagen eine Frage gestellt, wie man ein Uni-Stundenplanungsproblem in ein Boolesches Erfüllungsproblem umwandelt.

(Class Scheduling to Boolean satisfiability [Polynomial-time reduction])

Ich habe eine Antwort von @Amit erhalten, der sehr elegant und einfach zu codieren war. Im Grunde war seine Antwort so: Anstatt Kurse in Betracht zu ziehen, berücksichtigte er Zeitintervalle.

So für den i-ten Kurs, er hat gerade alle möglichen Intervalle für diesen Kurs angezeigt. Und wir erhalten eine Lösung, wenn es für jeden Kurs mindestens ein wahres Intervall gibt und sich kein Intervall mit dem anderen überschneidet.

Diese Methode funktioniert sehr gut, wenn wir nur Kurse und sonst nichts berücksichtigen. Ich verallgemeinere es, indem ich den Raum innerhalb des Intervalls codiere.

zum Beispiel, anstatt [8-10] zu sagen, dass ein Kurs zwischen 8:00 und 10:00 Uhr stattfinden kann

Ich habe [0.00801 - 0.01001] verwendet, um zu sagen, dass ein Kurs in Raum 1 zwischen 8:00 und 10:00 Uhr stattfinden kann.

Ich bin mir sicher, dass du gerade wanderst "Warum double verwenden?" naja, da kommt hier mein problem:

Um diese Methode weiter zu verallgemeinern, codiere ich in diesem Intervall auch die Nr. Des Lehrers.

Ich habe [1.00801 - 1.01001] verwendet, um zu sagen, dass ein Kurs zwischen 8:00 und 10:00 Uhr in Raum 1 stattfinden kann und vom Lehrer Nr. 1 unterrichtet werden kann.

Hier ist was ich jetzt habe:

wie dies [1.008XX - 1.010XX] gleichzeitig mit [2.008YY - 2.010YY] geschehen kann, was zutrifft, wenn der Lehrer 1 zwischen 8.00 und 10.00 Uhr im Raum X unterrichtet, kann der Lehrer 2 auch unterrichten in Y zwischen 8 und 10 Uhr, wenn das Zimmer frei ist.

Das Problem ist: Mit dieser Methode kann ich nicht garantieren, dass XX und YY unterschiedlich sind und dass YY verfügbar sein wird, da [1.008XX - 1.010XX] [2.008XX - 2.010XX] nicht überlappt Solver halten dies für möglich.

Und ich habe immer noch keine Ahnung, wie ich dies mithilfe dieser Intervallmethode sicherstellen kann ... Ich benötige eine Möglichkeit, {Intervall, Raum und Lehrer-ID} zu codieren, damit:

Ein Lehrer kann sich nicht an zwei Stellen in demselben Intervall befinden.es können nicht 2 Lehrer im selben Raum für dasselbe Intervall sein.Es gibt mindestens 1 Intervall, das natürlich wahr ist.

Vielen Dank im Voraus für Ihre Hilfe, Mit freundlichen Grüßen!

Zusatzfrage Class Scheduling to Boolean satisfiability [Polynomial-time reduction] Letzter Teil