5. Lösungssuche

5.1. Allgemein

• in welcher Reihenfolge die Problemvariablen beim labeling verarbeitet werden, also in welcher Reihenfolge die Veranstaltungen in den Stundenplan gelegt werden.
• in welcher Reihenfolge die möglichen Werte eines Wertebereiches für die Zuweisung zu den Domainvariablen Raum, Tag und Zeit ausprobiert werden, also wohin die Veranstaltungen zuerst in den Stundenplan gelegt werden.

5.2. Steuerung der Reihenfolge der Problemvariablen

• Genereierung eines Tupels für jede Veranstaltung, das aus den, durch Prologausdrücke ausgedrückten, Sortierkriterien besteht und aus der VeranstaltungsID.
  (kriterium₁, kriterium₂, ..., kriterium_n, VeranstaltungsID)
  Diese Tupel können dann in einer Liste verwaltet werden.
  
• Die Liste aus Tupeln wird mit dem vorgegebenen Prädikat sort sortiert. Da die VeranstaltungsIDs in den Tupeln in letzter Position stehen, spielen sie für die Sortierug keine Rolle. Stattdessen wird die Liste nach den Ausdrücken sortiert, welche die Sortierkriterien abbilden.
• Anhand der Reihenfolge, in der die VeranstaltungsIDs in der SortierListe jetzt vorliegen, kann die Liste der Problemvariablen, in deren Tupeln ja ebenfalls die VeranstaltungsIDs enthalten sind, sortiert werden.
• Die sortierte Liste der Problemvariablen wird nun an das labeling Prädikat übergeben

main :-
  ...
  findall([TeilnehmerAnz0, RaumAnz, VeranstaltungsID], 

    (veranstaltung(VeranstaltungsID, Teilnehmer, BenRessourcen), 

    zaehleTeilnehmer(Teilnehmer, TeilnehmerAnz), 

    TeilnehmerAnz0 is TeilnehmerAnz * (-1),
    findall(RaumID, raum(RaumID, _, _, _), RaumListe), 

    holeGueltigeRaeume(RaumListe, VeranstaltungsID, GueltigeRaeume), 

    length(GueltigeRaeume, RaumAnz) 

    ), 

    SortKriteriumsListe 

  ), 

  sort(SortKriteriumsListe, SortListe), 

  mkVerIDListe(SortListe, SortVerIDListe),
  sortiere(ProblemVars, SortVerIDListe, SortiertePVars), 

  labeling(SortiertePVars), 

  ...

mkVerIDListe([], []).
mkVerIDListe([SortElement|SortRest], [VerID|VerIDRest]) :-
  letztes(VerID, SortElement)
  mkVerIDListe(SortRest, VerIDRest). 

letztes(LetztesEle, [LetztesEle]).
letztes(LetztesEle, [_|Rest]) :- letztes(LetztesEle, Rest).

sortiere(_, [], []).
sortiere(PVars, [VerID|VIDRest], [Element|ErgebnisListe]) :-
  suchen(PVars, VerID, Element),
  sortiere(PVars, VIDRest, ErgebnisListe).

suchen([raumTagZeit(Raum, Tag, Zeit, VerID)|PRest], VerID, raumTagZeit(Raum, Tag, Zeit, VerID)). 
suchen([PVar|PRest], VerID, Element) :- suchen(PRest, VerID, Element).

5.3. Steuerung der Reihenfolge der Wertebelegung

labeling([ProblemVar|Rest]) :-
  ProblemVar = raumTagZeit(Raum, _, _, VeranstaltungsID),
  veranstaltung(VeranstaltungsID, Teilnehmer, _),
  zaehleTeilnehmer(Teilnehmer, TeilnehmerAnzahl),
  dom(Raum, RaumListe),
  mkRaumKriteriumsListe(RaumListe, TeilnehmerAnzahl, KriteriumsListe),
  indomain(Raum, KriteriumsListe),
  indomain(Tag),
  indomain(Zeit),
  labeling(Rest).


mkRaumKriteriumsListe([], _, []).
mkRaumKriteriumsListe([RaumID|RRest], TeilnehmerAnzahl, [Kriterium|KRest]) :-
  raum(RaumID, Platz, _, _),
  KriteriumsInhalt is Platz - TeilnehmerAnzahl,
  Kriterium = [KriteriumsInhalt],
  mkRaumKriteriumsListe(RRest, TeilnehmerAnzahl, KRest).  


indomain(DomainVar, _) :-
  nonvar(DomainVar).
indomain(DomainVar, KriteriumsListe) :-
  var(DomainVar),
  dom(DomainVar, Wertebereichsliste),
  sortiereWerte(Wertebereichsliste, KriteriumsListe, SortierteWertebereichsListe),
  member(DomainVar, SortierteWertebereichsListe).


sortiereWerte(Wertebereichsliste, KriteriumsListe, SortierteWertebereichsListe) :-
  mkKombiListe(Wertebereichsliste, KriteriumsListe, KombiListe),
  sort(KombiListe, SortierteKombiListe),
  mkWerteListe(SortierteKombiListe, SortierteWertebereichsListe).


mkKombiListe([], [], []).
mkKombiListe([Wert|WRest], [Kriterium|KRest], [KombiEle|KombiRest]) :-
  append([Wert], Kriterium, KombiElement),
  mkKombiListe(WRest, KRest, KombiRest).


mkWerteListe([], []).
mkWerteListe([Kriterium|SKRest], [Wert|SWRest]) :-
  letztes(Wert, Kriterium),
  mkWerteListe(SKReste, SWRest).

5.4. Häufig benutzte Heuristiken

• beliebige Reihenfolge (so wie aus Wissenbasis in Liste - evtl. alphabetisch)
• general purpose variable selection heuristik
  • first fail prinzip: die Veranstaltung mit den kleinsten Domänen (hier kann noch mal zwischen Raum und Zeit differenziert werden - je nach Domäne) wird zuerst in den Stundenplan gelegt
  • largest degree first: schedule die Veranstaltung mit den grössten Konflikten zuerst (vgl. [4]), d.h. möglichst grosse Schnittmenge an Teilnehmern/Hörsaalressourcen/...
  • largest color degree first: Schedule zuerst die Veranstaltung, die am meisten mit den bereits gelabelten Veranstaltungen in Konflikt steht
• mit Random Element ([2]):
  • tournament selection: bilde eine Zufallsteilmenge aller Problemvariablen und aus denen wähle anhand einer ausgewählten Statistik
  • bias selection: Bilde eine Reihenfolge anhand einer Heuristik und dann wähle ein Zufallselement aus den besten n Veranstaltungen
• problem specific heuristic: nach Teilnehmern (Studgruppen/Dozenten) geordnet

• naiv: gehe die Elemente des Wertebereichs numerisch geordnet durch -> Weg = indomain
• first fit: plaziere die Veranstaltungen an dem Tag, an dem am wenigsten Veranstaltungen mit den gleichen Teilnehmern liegen
• random: wähle zufällige Werte aus den Wertebereichen für Raum, Tag und Zeit
• Ausnutzung der räumlichen Kapazität: plaziere die Veranstaltungen in Räume, deren Kapazität möglichst nah an Teilnehmeranzahl der Veranstaltung ist