Klassenplanung zur booleschen Erfüllbarkeit [Polynomial-time reduction]

Lesezeit: 7 Minuten

Benutzeravatar von Valentin Montmirail
Valentin Montmirail

Ich habe ein theoretisches/praktisches Problem und habe im Moment keine Ahnung, wie ich damit umgehen soll. Hier ist es:

Ich erstelle eine SAT-Löser in der Lage, ein Modell zu finden, wenn eines existiert, und den Widerspruch zu beweisen, wenn dies nicht der Fall ist CNF Probleme in C mit Genetik-Algorithmen.

Ein SAT-Problem sieht im Grunde wie folgt aus:
Geben Sie hier die Bildbeschreibung ein
Mein Ziel ist es, diesen Löser zu verwenden, um Lösungen in vielen verschiedenen Bereichen zu finden NP-vervollständigt Probleme. Grundsätzlich übersetze ich verschiedene Probleme in SAT, löse SAT mit meinem Löser und transformiere dann die Lösung in eine für das ursprüngliche Problem akzeptable Lösung.

Ich habe bereits Erfolg beim N*N-Sudoku und auch bei den N-Damen-Problemen, aber hier ist mein neues Ziel: das Klassenplanungsproblem auf SAT zu reduzieren, aber ich habe keine Ahnung, wie ich ein Klassenplanungsproblem formalisieren soll, um es leicht zu transformieren es in SAT nach.

Das Ziel ist offensichtlich, in wenigen Monaten ein Bild von einem Zeitplan wie diesem zu erstellen:

Geben Sie hier die Bildbeschreibung ein

ich habe das gefunden Quellcode wer kann die Stundenplanung lösen, aber leider ohne Abstriche bei SAT :/

Ich habe auch einige Artikel über Planung im Allgemeinen gefunden (http://www.cs.rochester.edu/users/faculty/kautz/papers/kautz-satplan06.pdf zum Beispiel).

Aber die Definitionssprache für Planungsdomänen Der in diesem Artikel verwendete Begriff scheint mir zu allgemein zu sein, um ein Klassenplanungsproblem darzustellen. :/

Hat jemand eine Idee, wie man eine Klassenplanung effizient formalisiert, um sie auf SAT zu reduzieren und danach die SAT-Lösung (falls vorhanden ^^) in eine Klassenplanung umzuwandeln?

Ich bin grundsätzlich für alle Vorschläge offen, habe im Moment keine Ahnung, wie man das darstellt, wie man das Problem reduziert, wie man die SAT-Lösung in einen Fahrplan umwandelt…


Zusatzfrage: Klassenplanung zu boolescher Erfüllbarkeit [Polynomial-time reduction] Teil 2

  • Bitte formalisieren Sie zuerst die Eingabe und die erwartete Ausgabe Ihrer Klassenplanung (oder verlinken Sie auf eine Stelle, die sie formalisiert).

    – amit

    11. März 2015 um 10:52 Uhr

  • es kann alles sein, das ist das Problem: Ich suche die beste Formalisierung für das Klassenplanungsproblem, und am besten bedeutet für mich “am einfachsten in SAT umzuwandeln” 🙂 Ich habe im Moment keinen formalisierten Input und mein Problem ist es, einen zu finden :/

    – Valentin Montmirail

    11. März 2015 um 10:55 Uhr

Benutzeravatar von amit
zustimmen

Ich werde versuchen, das Problem zuerst zu formalisieren und dann versuchen, es auf SAT zu reduzieren.

Definieren Sie das Klassenplanungsproblem als:

Input = { S1,S2,....,Sn | Si = {(x_i1, y_i1), (x_i2, y_i2) , ... , (x_ik, y_ik) | 0 <= x_ij < y_ij <= M } } 

Informell: Die Eingabe ist eine Menge von Klassen, jede Klasse ist eine Menge von (offenen) Intervallen in der Form (x,y)

(M ist eine Konstante, die das “Ende der Woche” beschreibt)

Ausgabe: Wahr, wenn und nur wenn ein Satz existiert:

R = { (x_1j1, y_1j1) , ..., (x_njn, y_njn) | for each a,b: (x_aja,y_aja) INTERSECTION (x_bjb,y_bjb) = {} }

Informell: wahr, wenn und nur wenn es eine Zuordnung von Intervallen gibt, so dass die Schnittmenge zwischen jedem Paar von Intervallen leer ist.


Reduktion auf SAT:

Definieren Sie eine boolesche Variable für jedes Intervall, V_ij

Definieren Sie darauf basierend die Formel:

F1 = (V_11 OR V_12 OR ... OR V_1(k_1)) AND .... AND (V_n1 OR V_n2 OR ... OR V_n(k_n))

Informell ist F1 genau dann erfüllt, wenn mindestens eines der Intervalle für jede Klasse “zufrieden” ist.

Definieren Smaller(x,y) = true wenn und nur if x <= y1

Wir werden es verwenden, um sicherzustellen, dass sich die Intervalle nicht überschneiden.

Beachten Sie, dass wir Folgendes benötigen, wenn wir sicherstellen möchten, dass sich (x1,y1) und (x2,y2) nicht überschneiden:

x1 <= y1 <= x2 <= y2 OR  x2 <= y2 <= x1 <= y1

Da garantiert der Eingang x1<=y1, x2<=y2es reduziert sich auf:

y1<= x2 OR y2 <= x1

Und mit unseren kleineren und booleschen Klauseln:

Smaller(y1,x2) OR Smaller(y2,x1)

Lassen Sie uns nun neue Klauseln definieren, die damit behandelt werden sollen:

Für jedes Paar von Klassen a,b und Intervallen c,d in ihnen (c in a, d in b)

G_{c,d} = (Not(V_ac) OR Not(V_bd) OR Smaller(y_ac,x_bd) OR Smaller(y_bd,x_ac))

Wenn eines der Intervalle b oder d nicht verwendet wird, ist die Klausel erfüllt und wir sind fertig. Andernfalls werden beide verwendet, und wir müssen sicherstellen, dass sich die beiden Intervalle nicht überschneiden.

Dies garantiert, dass, wenn beide c, d “gewählt” werden, sie sich nicht überlappen, und dies gilt für jedes Paar von Intervallen.

Bilden Sie nun unsere endgültige Formel:

F = F1 AND {G_{c,d} | for each c,d}

Diese Formel sichert uns:

  1. Für jede Klasse wird mindestens ein Intervall ausgewählt
  2. Für jeweils zwei Intervalle c, d – wenn sowohl c als auch d gewählt werden, überlappen sie sich nicht.

Kleiner Hinweis: Diese Formel erlaubt es, mehr als 1 Intervall aus jeder Klasse auszuwählen, aber wenn es eine Lösung mit einigen t>1-Intervallen gibt, können Sie t-1 davon leicht entfernen, ohne die Korrektheit der Lösung zu ändern.

Am Ende sind die gewählten Intervalle die von uns definierten booleschen Variablen V_ij.


Beispiel:

Alebgra = {(1,3),(3,5),(4,6)} Calculus = {(1,4),(2,5)}

Definiere F:

F1 = (V1,1 OR V1,2 OR V1,3) AND (V2,1 OR V2,2)

Definiere Gs:

G{A1,C1} = Not(V1,1) OR Not(V2,1) OR  4 <= 1 OR 3 <= 1 //clause for A(1,3) C(1,4)
         = Not(V1,1) OR Not(V2,1) OR false = 
         = Not(V1,1) OR Not(V2,1)
G{A1,C2} = Not(V1,1) OR Not(V2,2) OR  3 <= 2 OR 5 <= 1 // clause for A(1,3) C(2,5)
         = Not(V1,1) OR Not(V2,2) OR false = 
         = Not(V1,1) OR Not(V2,2)
G{A2,C1} = Not(V1,2) OR Not(V2,1) OR  5 <= 1 OR 4 <= 3 //clause for A(3,5) C(1,4)
         = Not(V1,2) OR Not(V2,1) OR false = 
         = Not(V1,2) OR Not(V2,1)
G{A2,C2} = Not(V1,2) OR Not(V2,2) OR  5 <= 2 OR 5 <= 3 // clause for A(3,5) C(2,5)
         = Not(V1,2) OR Not(V2,2) OR false = 
         = Not(V1,2) OR Not(V2,2)
G{A3,C1} = Not(V1,3) OR Not(V2,1) OR  4 <= 4 OR 6 <= 1 //clause for A(4,6) C(1,4)
         = Not(V1,3) OR Not(V2,1) OR true= 
         = true
G{A3,C2} = Not(V1,3) OR Not(V2,2) OR  6 <= 2 OR 5 <= 4 // clause for A(4,6) C(2,5)
         = Not(V1,3) OR Not(V2,2) OR false = 
         = Not(V1,3) OR Not(V2,2)

Jetzt können wir unsere endgültige Formel zeigen:

    F = (V1,1 OR V1,2 OR V1,3) AND (V2,1 OR V2,2) 
        AND  Not(V1,1) OR Not(V2,1) AND Not(V1,1) OR Not(V2,2)
        AND  Not(V1,2) OR Not(V2,1) AND Not(V1,2) OR Not(V2,2)
        AND  true AND Not(V1,3) OR Not(V2,2)

Das Obige ist nur erfüllt, wenn:

V1,1 = false
V1,2 = false
V1,3 = true
V2,1 = true
V2,2 = false

Und das steht für den Zeitplan: Algebra=(4,6); Kalkül=(1,4), wie gewünscht.


(1) kann ziemlich einfach als Konstante der Formel berechnet werden, es gibt Polynomzahlen solcher Konstanten.

  • Ich hoffe wirklich, dass ich keinen Fehler gemacht habe, das war keine triviale Reduzierung, bitte kommentieren Sie, wenn Sie ein Problem sehen

    – amit

    11. März 2015 um 11:36 Uhr

  • Vielen Dank 🙂 aber ich muss zugeben, ich glaube nicht, dass ich alles verstehe, was du gesagt hast 😀 Deine Formalisierung ist in der Tat die einfachste und so besser in SAT umzuwandeln 🙂 Ich verstehe, wie man am Ende das bekommt Planung aus der SAT-Lösung. Aber können Sie ein kleines Beispiel geben, wie 2 Klassen und 3 Intervalle. Ich verstehe, dass es 2 * 3 = 6 boolesche Variablen geben wird; Aber wie sieht die CNF-Datei aus?

    – Valentin Montmirail

    11. März 2015 um 12:04 Uhr

  • @ValentinMontmirail Ich habe die Antwort mit einem einfachen Beispiel aktualisiert. mit 2 Klassen und 3,2 Intervallen. Beachten Sie, dass die Anzahl der Variablen in diesem Fall 3+2 ist. Die Anzahl der Klauseln ist fast O(#variables^2).

    – amit

    11. März 2015 um 12:49 Uhr

  • Nochmals vielen Dank 🙂 Ich habe zur gleichen Zeit an deinen Ideen gearbeitet und jetzt habe ich es verstanden ^^ (Ich antworte vielleicht zu schnell, bevor ich nachdenke ^^) Aber wirklich, ich bin total beeindruckt, deine Methode ist so elegant, einfach und funktioniert perfekt 🙂 Danke für dein Beispiel, es hat gezeigt, was ich verstanden habe 🙂 nur um ganz sicher zu gehen 🙂

    – Valentin Montmirail

    11. März 2015 um 12:58 Uhr

  • @ValentinMontmirail Ich würde nicht “einfach” sagen, es hat ziemlich viel Zeit gedauert, darüber nachzudenken, und noch mehr, um es zu formalisieren. Es ist aber einfach zu programmieren 🙂

    – amit

    11. März 2015 um 13:00 Uhr

1405240cookie-checkKlassenplanung zur booleschen Erfüllbarkeit [Polynomial-time reduction]

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy