4. Implementierung des Stundenplanproblems in CLP


[ Constraint Logic Programming Seminar ] ... [ Thema Stundenplangenerierung mit CLP ] ... [ 5. Louml&sungssuche ]

Übersicht


4.1. Implementierung eines PCSP's in CLP

Ein CLP-Programm zum Lösen eines PCSP's besteht aus folgenden Komponenten:

4.2. Hinterlegung von Informationen in der Wissensbasis

Die Wissensbasis enthält die statischen Informationen über den Stundenplan, besteht also aus den in 2.2.1. beschriebenen Informationen über die drei Mengen Veranstaltungen, Räume und Zeitfenster, zusammen mit ihren bereits beschriebenen Eigenschaften. Diese Informationen werden in Form von Prolog-Fakten hinterlegt.
Informationen über Veranstaltungen müssen eindeutig identifiziert werden können und bestehen wie bereits beschrieben aus Teilnehmern und benötigten Ressourcen. Das Prologfakt veranstaltung/3 hat also die Form veranstaltung(VeranstaltungsID, TeilnehmerListe, Ressourcenliste)
Beispiel:
veranstaltung(analysis1_1, [ha, ii1, wi1], [tafel]).
Eine Information, die zusätzlich noch für die Raumbelegung notwendig ist, ist die Anzahl an Plätzen, welche die Teilnehmer beanspruchen. Diese Information kann in Form des Prologfakts anzteilnehmer/2 in der Form anzteilnehmer(Teilnehmer, Anzahl) hinterlegt werden. Die Anzahl an Plätzen ergibt sich dabei aus der Anzahl an realen Personen, die dieser Teilnehmer repräsentiert. Teilnehmer, die Dozenten repräsentieren, nehmen 0 Plätze in Anspruch, da der von ihnen besetzte Platz im Raum immer zur Verfügung steht, unabhängig davon, wieviele Teilnehmer die Veranstaltung besuchen.

Beispiel:
anzteilnehmer(ii1, 10).
anzteilnehmer(ha, 0).

Auch Informationen über Räume müssen eindeutig identifiziert werden und bestehen aus der Anzahl an Plätzen und der Menge der Ressourcen, die sie zur Verfügung stellen. Wie später noch deutlich wird, benötigen wir 2 Arten der Identifikation, eine numerische mit der man rechnen kann, sowie einen Namen den man ausgeben kann. Diese Informationen werden durch das Fakt raum/4 der Form raum(NumerischeId, AnzahlPlätze, RessourcenListe, Name) beschrieben.

Beispiel:
raum(1, 60, [tafel, beamer], hs1).

Eine weitere Information, die durch dieses Fakt hinterlegt wird ist die Anzahl der dem Problem zur Verfügung stehenden Räume. Diese ergibt sich aus der Anzahl der raum-Fakten in der Wissensbasis.
Die einzigen Informationen, die man über Zeitfenster hinterlegen muss, sind die Anzahl der zur Verfügung stehenden Zeitfenster und eine Möglichkeit unterschiedliche Zeitfenster eindeutig zu identifizieren. Die Identifikation sollte aus einer numerischen ID für Berechnungen und aus einem Namen für eine Ausgabe bestehen. Es gibt zwei Möglichkeiten, die Zeitfenster zu beschreiben: Beide Möglichkeiten unterscheiden sich nur in der Formulierung darauf aufbauender Einschränkungen. Der Lesbarkeit halber, wird hier die Unterteilung in Tag und Zeitblock pro Tag vorgenommen. Ein Tag wird somit durch das Fakt tag/2 der Form tag(NumerischeID, Name) und ein Zeitblock durch das Fakt zeit(NumerischeID, Name) beschrieben.

Beispiel:
tag(1, montag).
tag(5, freitag).
zeit(1, '8:00-9:15').
zeit(5, '17:00-18:15).

Die Anzahl der insgesamt zur Verfügung stehenden Zeitfenster ergibt sich aus der Anzahl der tag-Fakten multipliziert mit der Anzahl der zeit-Fakten.

Beispiel Wissensbasis

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. Constrain-Phase

4.4.1. Allgemein

Alle harten Constraints werden auf die Problemvariablen angewendet, indem die Wertebereiche der Domainvariablen Raum, Tag und Zeit, aus denen die Problemvariablen bestehen, eingeschränkt werden. Die harten Constraints repräsentieren die in 2.2.2.2. beschriebenen drei notwendigen Nebenbedingungen des Stundenplanproblems.

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).


Vollständiges Programm

Das Ausgabeprädikat schreibt das Ergebnis in Form von Prologfakten loesung/4 der Form loesung(VeranstaltungsID, Raum, Tag, Zeit) in eine Datei. Diese Datei kann als Wissensbasis für weitere Prologprogramme (oder auch andere Programme) dienen um entweder weitere Berechnungen anzustellen oder das Ergebnis in graphischer Form auszugeben. Ein Beispiel für letzteres ist das Prologprogramm ausgabe, das aus dem Ergebnis eine HTML-Seite generiert.

Ausgabeprogramm


[ Constraint Logic Programming Seminar ] ... [ Thema Stundenplangenerierung mit CLP ] ... [ 5. Louml&sunsgssuche ]