3. Stundenplanproblem als Constraint Satisfaction Problem

[ Constraint Logic Programming Seminar ] ... [ Thema Stundenplangenerierung mit CLP ] ... [ 4. Implementierung in CLP ]

Übersicht

3.1. Allgemein

Bevor man einen Lösungsalgorithmus für das Stundenplanproblem in CLP implementiert, empfiehlt es sich, dass Problem zunächst programmiersprachenunabhängig zu modellieren. Diese Handlungsweise erhöht das Problemverständnis, erleichtert die Implementation und eröffnet die Möglichkeit, das fertige Modell auch durch andere Sprachen als CLP zu implementieren. (vgl. [3])

3.2. Definition CSP

Ein CSP besteht aus

Einer Menge von Variablen X = {x₁, x₂, ..., x_n}.
Diese Variablen nennt man Problemvariablen.
Einer Menge von Wertebereichen(Domains) D={d₁, d₂, ..., d_n}
für die Elemente aus X, so dass d_i die Domain der Problemvariablen x_i ist:
d_i = d(x_i)
Einer Menge von Constraints C, die für die Problemvariablen einschränkt, welche Werte sie aus ihren Wertebereichen annehmen können.

Die Lösung des CSPs ist die Zuweisung eines Wertes aus d_i zur Variable x_i für alle i=1..n, so dass alle Constraints aus C erfüllt werden. In Hinblick auf den in 2.3. vorgestellten Suchraum, lässt sich ein CLP wie folgt beschreiben:
Die Problemvariablen mit ihren Domains spannen den Suchraum auf. Durch die Constraints wird der Suchraum eingeschränkt, also verkleinert. Die Lösungssuche besteht darin, in dem eingeschränkten (und somit nicht mehr so grossen) Suchraum nach einer Lösung für das Problem zu suchen. Die Constraints lassen sich in einer ersten Klassifikation nach ihrem Wirkungsbereich in lokale und globale Constraints klassifizieren. Lokale Constraints sind Constraints, die nur die Domain einer Variable beeinflussen. Globale Constraints sind Constraints, welche die Domains mehrerer Variablen gleichzeitig beeinflussen. Der Unterschied ist am deutlichsten bei der Lösungsuche: Die Auswirkung lokaler Constraints ist in der Domain einer Variablen deutlich durch die Reduktion der entsprechenden Domain sichtbar, während die Auswirkung von globalen Constraints nicht in den Domains sichtbar ist, sondern nur die Belegung von Werten steuert.
Ein Beispiel für die Modellierung eines Problems als CSP ist das bekannte und im ersten Vortrag dieser Seminarreihe behandelte n-Damenproblem. Modelliert als CSP, besteht die Menge der Problemvariablen X aus den n Damen. Der Wertebereich einer Problemvariablen ist in diesem Fall die Menge der Felder auf dem n X n Schachbrett. Die Menge der Constraints besteht aus den Bedingungen, die beschreiben, wann n Damen auf einem n X n Schachbrett sich schlagen können.

3.3. Partial Constraint Satisfaction Problem (PCSP)

Mit dem oben beschriebenen CSP-Ansatz lässt sich jedoch das Stundenplanproblem noch nicht vollständig modellieren, da dieses auch aus Einschränkungen besteht, welche nicht unbedingt erfüllt werden müssen, um eine Lösung zu generieren (das sind hier die erstrebenswerten Nebenbedingungen). Daraus folgt eine zweite Klassifikation der Constraints in harte und weiche Constraints: Harte Constraints müssen erfüllt werden, um eine Lösung zu generieren. Weiche Constraints sind in eine Prioritätenhierachie aufgeteilt und es sollten so viele wie möglich unter Berücksichtigung ihrer Position innerhalb der Prioritätenhierachie erfüllt werden. Probleme, die sowohl aus notwendigen Einschränkungen als auch aus erstrebeneswerten Einschränkungen bestehen, werden als PCSP modelliert. Ein PCSP besteht aus den gleichen Komponenten wie ein CSP, bis auf die Tatsache, dass die Menge C der Constraints aus zwei Submengen besteht, nämlich aus der Menge der harten Constraints und der Menge der weichen Constraints. Jedes weiche Constraints beeinhaltet eine Priorität, die den Beitrag des Constraints zur Güte der Lösung beschreibt.

3.4. Stundenplanproblem als PCSP

In einem als PCSP modellierten Stundenplanproblem, repräsentiert die Menge der Problemvariablen die Menge der Veranstaltungen
X = V
Der Wertebereich (domain) für jede Problemvariable besteht aus einem Paar, bestehend aus der Menge der vorhandenen Räume und der Menge der vorhandenen Zeitfenster
d_i = (1..Anzahl der Räume, 1..Anzahl der Zeitfenster). Die Menge der Constraints beeinhaltet die schon in 2.2.2. beschriebenen Nebenbedingungen des Stundenplanproblems. Dabei werden die notwendigen Nebenbedingungen auf die harten Constraints und die erstrebenswerten Nebenbedingungen auf die weichen Constrainst abgebildet. Gemäss des PCSP-Ansatzes erhalten die weichen Constraints unterschiedliche Prioritäten, welche die Relevanz für die Güte einer Stundenplanlösung repräsentieren.

[ Constraint Logic Programming Seminar ] ... [ Thema Stundenplangenerierung mit CLP ] ... [ 4. Implementierung in CLP ]