4.3. Generierung der Problemvariablen und ihrer Domains
Die Menge der Problemvariablen repräsentiert, wie in 3.4. schon beschrieben, die
Menge der Veranstaltungen.
Die Domain einer Problemvariable ist, wie schon in 3.4. beschrieben, ein Tupel, bestehend aus den belegbaren
Räumen und den belegbaren Zeitfenstern.
Eine einzelne Problemvariable besteht dann aus einem Quadtupel (Raum, Tag, Zeit, VeranstaltungsID),
wobei Raum, Tag und Zeit Domainvariablen mit den Domains
Raum::1..Anzahl der Räume
Tag::1..Anzahl der Tage
Zeit::1..Anzahl der Zeitblöcke
sind und die VeranstaltungsID der Unterscheidung der Problemvariablen und der Identifikation der Veranstaltung, die
sie repräsentiert, dient.
Um die Menge der Problemvariablen in Prolog zu repräsentieren, gibt es
zwei Möglichkeiten: als Liste und als Baum. Die Repräsentation als Liste hat den
Vorteil, dass dieser Datentyp durch eine Vielzahl an vordefinierten
Prädikaten und durch einige Constraints aus der FD-Library, die
auf Listen arbeiten, unterstützt wird. Die Repräsentation als Baum hat den Vorteil,
dass die Problemvariablen, wie in 5. und 6. noch beschrieben wird, bei der Implementation von Heuristiken
und bei der Verarbeitung harter und weicher Constraints häufig nach
bestimmten Kriterien sortiert werden müssen, oder einzelne Veranstaltungen aus der Menge
der Problemvariablen extrahiert werden müssen.
Diese Such- und Sortieroperationen können in einer Suchbaum-Struktur
ökonomischer durchgeführt werden, als in einer Liste.
Um die Vorteile beider Repräsentationen zu vereinigen, sollte die Menge als
Baum repräsentiert werden, aus dessen Knotenelementen, dann im Laufe
der Constrain- und der Labeling-Phase nach unterschiedlichen Kriterien sortierte Listen
generiert werden. Im weiteren Verlauf dieser Arbeit wird jedoch
nur die Repräsentation als Liste besprochen.
Für die Repräsentation als Liste werden zunächst mit dem vordefinierten
Prädikat findall/3 eine Liste der VeranstaltungsIDs aller Veranstaltungen in der Wissensbasis
generiert.
findall(VerID, veranstaltung(VerID, _, _), VeranstaltungsIDListe)
Die dadurch gewonnene Liste VeranstaltungsIDListe wird dazu genutzt, um mit dem
Prädikat mkProblemVars eine Liste der oben beschriebenen Quadtupel zu
erstellen, indem für jedes Element der Veranstaltungsliste ein Quadtupel bestehend aus den
Domainvariablen Raum, Tag und Zeit erstellt wird, und die DomainVariablen mit ihren entsprechenden Wertebereichen initialisiert
werden.
main :-
...
findall(VerID, veranstaltung(VerID, _, _), Veranstaltungen),
mkProblemVars(Veranstaltungen, ProblemVars),
...
mkProblemVars([], []).
mkProblemVars([VerID|VRest], [ProblemVar|PRest]) :-
mkProbVar(VerID, ProblemVar),
mkProblemVars(VRest, PRest).
mkProbVar(VerID, ProblemVar) :-
ProblemVar=raumTagZeit(Raum, Tag, Zeit, VerID),
anzahlRaeume(AnzRaeume),
anzahlTage(AnzTage),
anzahlZeiten(AnzZeiten),
AnzRaeume0 is AnzRaeume-1,
AnzTage0 is AnzTage-1,
AnzZeiten0 is AnzZeiten-1,
Raum::0..AnzRaeume0,
Tag::0..AnzTage0,
Zeit::0..AnzZeiten0.
4.4.2. Raum Constraint
Für das Constraint, das festlegt, dass Veranstaltungen nur in Räumen
stattfinden sollen, die gross genug sind und alle benötigten Ressourcen bereitstellen, muss
für jede Problemvariable festgestellt werden, wieviele Platz alle
Teilnehmer verbrauchen, die an der Veranstaltung teilnehmen und welche
Ressourcen diese Veranstaltung benötigt.
Daraufhin müssen die Räume in der Wissensbais, die genug Platz anbieten, um alle
Teilnehmer aufzunehmen und deren Ressourcenmenge eine Obermenge der
Menge der benötigten Ressourcen ist, gesucht werden.
Der neue Wertebereich der Domainvariable Raum der Problemvariable ist dann die gefundene Menge der
gültigen Räume.
Das dazu erfordeliche Prädikat raumConstr/1 der Form raumConstr(+ProblemVarListe) generiert mit findall eine Liste der IDs aller Räume der Wissensbasis.
Aus dieser Liste wird dann mit dem Prädikat holeGueltigeRaeume die Liste, der für die aktuell verarbeitete Veranstaltung
gültigen Räume, extrahiert. Der Wertebereich der Domainvariable Raum der aktuell verarbeiteten Veranstaltung wird dann mit dem
Prädikat '::' auf die Liste der gueltigen Räume gesetzt.
raumConstr([]).
raumConstr([raumTagZeit(Raum, _, _, VerID)|PRest]) :-
findall(RaumID, raum(RaumID, _, _, _), RaumListe),
holeGueltigeRaeume(RaumListe, VerID, GueltigeRaeume),
Raum::GueltigeRaeume,
raumConstr(PRest).
Das Prädikat holeGueltigeRaeume/3 der Form
holeGueltigeRaeume(+RaumIDListe, +VeranstaltungsID, -GueltigeRaeume)
berechnet die Anzahl der Teilnehmer der aktuellen Veranstaltung
(mit dem Prädikat zaehleTeilnehmer/2) und vergleicht sie mit
der Grösse der Räume in der RaumIDListe.
Ausserdem bestimmt es, ob die Menge, der von der Veranstaltung benötigten Ressourcen,
Teilmenge der Menge der Ressourcen, die ein Raum zur Verfügung stellt
ist (mit dem Prädikat teilMenge/2). Räume für die das zutrifft und deren Grösse grösser
oder gleich der Teilnehmeranzahl ist, werden Element der Liste der gültigen Räume (GueltigeRaeume).
holeGueltigeRaeume([], _, []).
holeGueltigeRaeume([RaumID|RRest], VerID, GueltigeRaeume) :-
veranstaltung(VerID, Teilnehmer, _),
raum(RaumID, Groesse, _, _),
zaehleTeilnehmer(Teilnehmer, AnzTeilnehmer),
Groesse < AnzTeilnehmer,
holeGueltigeRaeume(RRest, VerID, GueltigeRaeume).
holeGueltigeRaeume([RaumID|RRest], VerID, GueltigeRaeume) :-
veranstaltung(VerID, Teilnehmer, VerRessourcen),
raum(RaumID, Groesse, RaumRessourcen, _),
zaehleTeilnehmer(Teilnehmer, AnzTeilnehmer),
Groesse >= AnzTeilnehmer,
not(teilMenge(VerRessourcen, RaumRessourcen)),
holeGueltigeRaeume(RRest, VerID, GueltigeRaeume).
holeGueltigeRaeume([RaumID|RRest], VerID, [RaumID0|GueltigeRaeume]) :-
veranstaltung(VerID, Teilnehmer, VerRessourcen),
raum(RaumID, Groesse, RaumRessourcen, _),
zaehleTeilnehmer(Teilnehmer, AnzTeilnehmer),
Groesse >= AnzTeilnehmer,
teilMenge(VerRessourcen, RaumRessourcen),
RaumID0 is RaumID - 1,
holeGueltigeRaeume(RRest, VerID, GueltigeRaeume).
Den Platz, den alle Teilnehmer einer Veranstaltung verbrauchen, ermittelt man mit dem
Prädikat zaehleTeilnehmer/2 der Form zaehleTeilnehmer(+TeilnehmerListe, -Anzahl).
zaehleTeilnehmer([], 0).
zaehleTeilnehmer([Teilnehmer|TRest], Anzahl) :-
teilnehmer(Teilnehmer, TeilnehmerAnz),
zaehleTeilnehmer(TRest, AnzRest),
Anzahl is TeilnehmerAnz + AnzRest.
Um Festzustellen, ob die Menge der Ressourcen, die eine Veranstaltung benötigt,
Teilmenge der Menge der Ressourcen ist, die ein Raum zur Verfügung stellt,
dient das Prädikat teilmenge/2 der Form teilmenge(?Submenge, ?Hauptmenge)
teilMenge([], Menge2).
teilMenge([Kopf1|Rest1], Menge2) :-
member(Kopf1, Menge2),
teilMenge(Rest1, Menge2).
Die Wirkung des Raumconstraints soll an einem Beispiel deutlich gemacht werden:
Gegeben sei folgende Wissenbasis:
veranstaltung(chemie1, [pl, di1, pi1], [tafel, chemielabor]).
teilnehmer(pl, 0).
teilnehmer(di1, 45).
teilnehmer(pi1, 5).
raum(1, 60, [tafel, beamer], hs1).
raum(2, 200, [tafel, beamer, chemielabor], hs2).
raum(3, 100, [tafel, beamer], hs3).
raum(4, 100, [tafel, beamer], hs4).
raum(5, 200, [tafel, beamer], hs5).
raum(6, 50, [tafel, chemielabor], chemielabor).
Nach der Erstellung der Problemvariablen sieht die Domain der Problemvariablen
noch so aus:
raumTagZeit(0..5, 0..4, 0..8, chemie1)
Nach Anwendung des Prädikats raumConstr wird die Domain so aussehen:
raumTagZeit([2,6], 0..4, 0..8, chemie1)
Der Wertebereich der Problemvariablen wurde sichtbar eingeschränkt. Es handelt sich also
gemäss der Klassifikation aus 3.2. um ein lokales Constraint.
4.4.3. Raum Clash Constraint
Um die Nebenbedingung zu implementieren, die aussagt, dass in einem Raum während eines
Zeitfensters maximal eine Veranstaltung stattfinden darf, muss man durchsetzen, dass allen Veranstaltungen
unterschiedliche Kombinationen aus Raum, Tag und Zeit zugeteilt werden:
(raumi, tagi, zeiti) <> (raumj, tagj,
zeitj) für i,j = 1..Anzahl der Veranstaltungen und i<>j.
Um diese Bedingung als Constraint zu modelieren, erstellt man eine Liste, die aus
den eindeutigen Kombinationen aus den Raum, Tag und Zeit Domainvariablen jeder
Problemvariable bestehen, und wendet auf diese Liste, das in der Finite Domain Library
enthaltene Constraint alldifferent/1 in der Form alldifferent(+Liste) an. Das Constraint
alldifferent erzwingt, das alle Elemente in der übergebenen Liste unterschiedlich sind.
Man kann alldifferent nicht direkt auf die Liste der Problemvariablen anwenden, da die Quadtupel
aus denen sie besteht schon aufgrund der unterschiedlichen VeranstaltungsIDs, die sie enthalten
unterschiedlich sind.
Diese Aufgabe, diese Bedingung durchzusetzen, übernimmt das Prädikat raumClashConstr/1
in der Form raumClashConstr(+ProblemVarListe)
raumClashConstr(ProblemVars) :-
mkDiffVars(ProblemVars, DiffVars),
alldistinct(DiffVars).
Um eine Liste der Raum/Tag/Zeit Kombinationen aller Problemvariablen
zu erstellen, wird das Prädikat mkDiffVars/2 der Form
mkDiffVars(+ProblemVarListe, -KombinationsListe)
verwendet das Kombinationen erstellt in dem die Kombination Anzahl_der_Tage * Anzahl_der_Zeiten * Raum + Anzahl_der Zeiten * Tag + Zeit mit einer
einzelnen numerischen Domainvariablen gleichgesetzt wird. Dazu wird das Constraint '#=' verwendet,
das die Gleichheit seiner beiden Parameter (von denen mind.
einer eine Domainvariable sein muss) erzwingt.
mkDiffVars([], []).
mkDiffVars([raumTagZeit(Raum, Tag, Zeit, _)|Rest], [DiffVar|DVRest]) :-
anzahlTage(AnzTage),
anzahlZeiten(AnzZeiten),
AnzTageUndZeiten is AnzTage * AnzZeiten,
(AnzTageUndZeiten * Raum + AnzZeiten * Tag + Zeit) #= DiffVar,
mkDiffVars(Rest, DVRest).
Nach der Klassifikation in den Wirkungskreis der Constraints handelt es sich bei
diesem Constraint um ein globales Constraint, da nicht der Wertebereich einer einzelnen
Domainvariable eingeschränkt wird, sondern die Wertebereiche mehrerer Domainvariablen
in Abhängigkeit voneinander. Globale Constraints bestimmen für die Menge der
Problemvariablen beim labeling, welche Werte gleichzeitig angenommen werden können.
4.4.4. Teilnehmer Clash Constraint
Die Nebenbedingung, die ausschliesst, dass ein Teilnehmer während eines Zeitfensters an mehr als an einer Veranstaltung teilnehmen muss,
wird implementiert, indem man durchsetzt, dass alle Veranstaltungen
deren Teilnehmermengen nicht disjunkt sind, in unterschiedlichen
Zeitfenstern stattfinden. D.h. die Kombinationen aus Tag und Zeit
dieser Veranstaltungen müssen unterschiedlich sein .
Diese Aufgabe übernimmt das Prädikat teilnehmerClashConstr/1
der Form teilnehmerClashConstr(+ProblemVarListe),
das zu einer Veranstaltung die Teilnehmermenge aus der Wissensbais sucht (Teilnehmer),
dann mit dem Prädikat holeSchnittVar/3 alle Veranstaltungen sucht,
deren Teilnehmermengen nicht disjunkt zu der Teilnehmermenge der aktuellen Veranstaltung sind
(SchnittVars) und dann mit dem Prädikat verhindereTeilnehmerClash/2
durchsetzt, dass die aktuelle Veranstaltungen und alle mit dem
Prädikat holeSchnittVar/3 gefundenen Veranstaltungen in
unterschiedlichen Zeitfenstern stattfinden.
teilnehmerClashConstr([]).
teilnehmerClashConstr([PVar|PRest]) :-
PVar = raumTagZeit(_, _, _, VerID),
veranstaltung(VerID, Teilnehmer, _),
holeSchnittVar(Teilnehmer, PRest, SchnittVars),
verhindereTeilnehmerClash(PVar, SchnittVars),
teilnehmerClashConstr(PRest).
Das Prädikat holeSchnittVar/3 der Form holeSchnittVar(+TeilnehmerListe, +ProblemVariablenListe, -SchnittVariablenListe),
testet für jede Veranstaltung mit dem Prädikat schnittMenge/2,
ob die Menge der Teilnehmer der Veranstaltung und die übergebene
Teilnehmermenge nicht disjunkt sind, ob sie also eine gemeinsame Schnittmenge
ungleich der leeren Menge haben. Trifft dies für eine Veranstaltung zu,
so wird sie Element der SchnittVar Liste.
holeSchnittVar(_, [], []).
holeSchnittVar(Teilnehmer, [PVar|PRest], SchnittVar) :-
PVar=raumTagZeit(Raum, Tag, Zeit, VerID),
veranstaltung(VerID, VerTeilnehmer, _),
not(schnittMenge(Teilnehmer, VerTeilnehmer)),
holeSchnittVar(Teilnehmer, PRest, SchnittVar).
holeSchnittVar(Teilnehmer, [PVar|PRest], [PVar|SchnittVar]) :-
PVar=raumTagZeit(Raum, Tag, Zeit, VerID),
veranstaltung(VerID, VerTeilnehmer, _),
schnittMenge(Teilnehmer, VerTeilnehmer),
holeSchnittVar(Teilnehmer, PRest, SchnittVar).
Um festzustellen, ob zwei als Listen repräsentierte Teilnehmermengen disjunkt sind,
mit anderen Worten, ob die Schnittstelle beider Mengen ungleich der leeren Menge ist,
verwendet man das Prädikat schnittmenge/2 der Form schnittmenge(+Menge1, +Menge2).
schnittMenge([], Menge2) :- fail.
schnittMenge([Kopf|Rest], Menge2) :-
member(Kopf, Menge2).
schnittMenge([Kopf|Rest], Menge2) :-
schnittMenge(Rest, Menge2).
Mit dem Prädikat verhindereTeilnehmerClash/2 der Form verhindereTeilnehmerClash(+ProblemVariable, +SchnittVarListe)
wird schliesslich durchgesetzt, dass die aktuelle ProblemVariable und die Problemvariablen in der übergebenen SchnittvarListe
in unterschiedlichen Zeitfenstern stattfinden.
Dabei wird das Constraint #\= verwendet, das erzwingt, dass seine zwei
Parameter (von denen mind. einer eine Domainvaraiable sein muss) unterschiedliche Werte erhalten.
verhindereTeilnehmerClash(_, []).
verhindereTeilnehmerClash(PVar, [SchnittVar|SVRest]) :-
PVar=raumTagZeit(_, Tagi, Zeiti, _),
SchnittVar=raumTagZeit(_, Tagj, Zeitj, _),
anzahlZeiten(AnzZeiten),
(AnzZeiten * Tagi + Zeiti) #\= (AnzZeiten * Tagj + Zeitj),
verhindereTeilnehmerClash(PVar, SVRest).
Genau wie das raumClashConstr gehört dieses Constraint zu der Klasse der globalen Constraints
und es gilt das bereits dazu Gesagte.
4.5. Ein erstes Stundenplanprogramm
Mit den hier vorgestellten Prädikaten und zusätzlich einem
primitiven Prädikat labeling/1 der Form labeling(+ProblemVarListe) für die
labeling-Phase, erhält man bereits ein vollständiges Programm zur Generierung von
gültigen (allerdings nicht optimalen) Stundenplänen. Das primitive labeling
Prädikat macht nichts anderes, als mit dem in der FiniteDomain Library enthaltenen
Prädikat indomain/1 den Domainvariablen Raum, Tag und Zeit aller Problemvariablen einen
Wert aus ihrer jeweiligen Domain zuzuweisen. Lokale Constraints müssen in dieser Phase nicht
mehr berücksichtigt werden, da sie die Domains der Problemvariablen bereits eingeschränkt
haben. Die globalen Constraints müssen jedoch berücksichtigt werden, d.h. wenn mit
indomain einer DomainVariable ein Wert aus ihrer Domain zugewiesen wird, wird auch überprüft,
ob diese Zuweisung ein globales Constraint verletzt. Es werden solange die Werte aus der domain als
Zuweisungsobjekte ausprobiert bis ein Wert gefunden worden ist, der kein globales Constraint mehr
verletzt. Es können, je nach der Reihenfolge, in der die Problemvariablen beim labeling
verarbeitet werden (also der Reihenfolge nach der die Veranstaltungen in den Stundenplan
gelegt werden) und der Reihenfolge nach der Werte aus den Domains der Domainvariablen ausprobiert
werden, Konflikte bzgl. der globalen Variablen entstehen.
Es können Situationen auftreten, in der eine Problemvariable nicht mehr verarbeitet werden
kann, ohne dass ein globales Constraint verletzt wird. Tritt so ein Konflikt auf, so wird Backtracking
ausgelöst. Beim Backtracking wird die zuletzt erfolgreich gemachte Zuweisung rückgängig
gemacht, und die nächstmögliche Zuweisung wird ausprobiert.
labeling([]).
labeling([PVar|PVRest]) :-
PVar = raumTagZeit(Raum, Tag, Zeit, VerID),
indomain(Raum),
indomain(Tag),
indomain(Zeit),
labeling(PVRest).
Diese Form der Lösungssuche arbeitet nach dem Depth-First-Ansatz:
Repräsentiert man den Suchraum als Baum, dann wandert man bei der Depth-First-Suche
von oben nach unten und von links nach rechts. Die Suche verläft also ungerichtet, wenn
auch in einem eingeschränkten Suchraum.
Das Hauptprädikat, also das Prädikat, das zur Lösung des Problems aufgerufen
wird, besteht aus den Phasen, die in 4.1. schon beschrieben wurden:
Zunächst wird die Wissensbasis geladen, dann wird die Menge der Problemvariablen
generiert. Anschliessend wird in der Constrainphase jedes harte Constraint auf die
Liste der Problemvariablen angewendet, bevor in der labeling-Phase nach einer gültigen
Lösung gesucht wird. Das letzte Prädikat das aufgerufen wird, dient der Ausgabe
der Lösung.
stundenplan(Wissensbasis, Ausgabe) :-
compile(Wissensbasis),
findall(VerID, veranstaltung(VerID, _, _), Veranstaltungen),
mkProblemVars(Veranstaltungen, ProblemVars),
raumConstr(ProblemVars),
raumClashConstr(ProblemVars),
teilnehmerClashConstr(ProblemVars),
labeling(ProblemVars),
ausgabe2(ProblemVars, Ausgabe).