Wichteln mit einem Constraint-Solving-Algorithmus in Prolog

viadee News, Künstliche Intelligenz, Data Science

Die ersten Türchen im Adventskalender sind geöffnet und auch die Kerzen auf dem Adventskranz brennen bereits. Die Weihnachtszeit hat begonnen. Bei vielen Leuten gehört das sogenannte Wichteln, in manchen Regionen auch Julklapp, Engerl oder Bengerl genannt, zur vorweihnachtlichen Tradition. Gerade in größeren Gruppen ist diese Art des Schenkens sehr praktisch, da nicht jeder jeden beschenken muss (...räusper) darf, sondern jede Person zufällig eine andere zu beschenkende Person zugelost bekommt.

Traditionelles Zettelziehen

Dies funktioniert traditionell so, dass jede Person seinen/ihren Namen auf einen Zettel schreibt und diesen zusammenfaltet. Danach werden alle Zettel eingesammelt, gemischt und anschließend zieht jede*r der Reihe nach einen davon. Grundsätzlich gibt es bei diesem Losverfahren nur eine Regel: Keine Person darf seinen/ihren eigenen Namen ziehen. Passiert dies, werden die Zettel wieder komplett eingesammelt und der Prozess beginnt von vorne.

Wie dieser Vorgang optimiert und auch aus Sicht der Stochastik „verbessert“ werden kann, zeigt dieses Video sehr anschaulich.

Komplizierter wird der Prozess, wenn noch weitere Ausnahmen, wie beispielsweise „keine Pärchen“, „keine Freundesgruppen“, „Eltern sollen nicht ihre Kinder ziehen“ hinzukommen sollen. Da wir im 21. Jahrhundert leben und dazu noch eine IT-Firma sind, liegt es nahe, das Problem mit einem Algorithmus zu lösen. Und genau dies werden wir jetzt angehen.

Moderner Zettelziehalgorithmus

Grundsätzlich sind mir drei Lösungswege in den Sinn gekommen, als ich mich mit der Thematik näher beschäftigt habe:

Brute force: Einfach alle Namen mischen, zuordnen und schauen, ob das Ergebnis valide ist und alle Ausnahmen berücksichtigt werden. Vorteil: wenig komplex. Nachteil: kann ewig dauern, es wird nicht erkannt, ob es bei vielen Ausnahmen überhaupt eine Lösung gibt, erfüllt nicht meinen eigenen Anspruch, das Problem gelöst zu haben.
Graphbasiert: Für mich ein sehr naheliegender Ansatz. Einen Graphen mit gerichteten Kanten zwischen allen Namen erstellen. Solche Kanten löschen, die gegen Ausnahmen verstoßen und dann eine valide Zuordnung erstellen. Vorteil: Man erkennt, wenn es durch zu viele Ausnahmen keine Lösung gibt. Das erfüllt schon eher meinen Anspruch, eine „Lösung“ gefunden zu haben. Nachteil: Graphtheorie ist nicht mein Fachgebiet.
Constraint-Solving: Man beginnt mit einer zufälligen Ziehung. Wenn diese valide ist, zieht man ein weiteres Mal. Dies wiederholt man, bis man entweder alle Namen gezogen hat oder eine Ziehung eine Ausnahme verletzt. Dann wird die letzte Ziehung rückgängig gemacht und neu gezogen. Wenn nicht mehr gezogen werden kann, wird die Ziehung vor der Ziehung rückgängig gemacht („Backtracking “). Vorteil: endliche Laufzeit, Anspruch einer Lösung ist gegeben (auf diesem Wege ließen sich auch alle Lösungen gleichzeitig ermitteln). Künstliche Intelligenz (KI) und regelbasierte Lösungsfindung sind schon eher meine Fachgebiete. Nachteil: Laufzeitverhalten bei größerem Input, rekursiv geht bekanntlich schief.

Unter Abwägung der genannten Vor- und Nachteile habe ich mich für Lösung drei entschieden und einen Algorithmus in Prolog geschrieben, den ich nachfolgend erläutern werde. Prolog erlaubt es, Fakten und Regeln zu definieren, welche man als Wissensdatenbank bezeichnet, und danach Anfragen an diese zu formulieren. Prolog wertet dann diese Anfrage aus und gibt ein positives oder negatives Ergebnis zurück.

DIE Lösung

Für unser Problem sind die Namen und die Ausnahmen die Fakten. Ausnahmen sind dabei gerichtet im Sinne von „X nicht Y beschenken“. Das sieht in Prolog so aus (ein fiktives Beispiel):

person(fry).
person(leela).
person(bender).
person(farnsworth).
person(wong).

ausnahme(fry,farnsworth).
ausnahme(farnsworth,fry).
ausnahme(wong,leela).
ausnahme(wong,fry).

Jetzt folgen zwei Regeln. Die erste legt fest, wann eine Ziehung aus Personen valide ist. Das bedeutet, dass die Person auch eine Person aus unserer Menge ist, sich nicht selbst gezogen hat und es keine Ausnahme gibt.

valide(X,Y) :-
 person(X),
 person(Y),
 not(ausnahme(X,Y)),
 X \= Y.

Die zweite Regel prüft, ob eine Ziehung valide ist und aus den restlichen Personen noch Ziehungen möglich sind. Dies ist quasi schon der „Algorithmus“ - definiert wird nur der Zielzustand, nicht der Ablauf. Dafür definieren wir die Regel zweimal. Einmal mit einer leeren Liste als noch zu ziehende und ein mal mit bereits gezogenen Personen. Dies ist unser „Endpunkt“. Wenn wir diesen erreicht haben, haben wir eine mögliche valide Ziehung gefunden. Die zweite Definition greift, wenn die noch zu ziehende Personenliste nicht leer ist.

finde_paar([], Gezogen).

finde_paar([Person|Rest], Gezogen) :-
 valide(Person, X),
 not(member(X, Gezogen)),
 finde_paar(Rest, [X | Gezogen]),
 write(Person), write(' '), write(X), nl.

Das write schreibt ein Fakt in die Ausgabe und das nl ist eine neue Zeile (new line). Diese Regel nimmt eine Person aus der Liste ([Person|Rest]), prüft ob es eine beliebige Person X gibt, die valide ist (valide(Person, X)), nicht bereits gezogen wurde (not(member(X, Gezogen))) und mit der restlichen Liste noch bis zum Endkriterium gezogen werden kann (finde_paar(Rest, [X | Gezogen]),). Wenn alle Bedingungen erfüllt sind, werden die Namen in die Ausgabe geschrieben.

Um die Auswertung der Regeln zu starten, mischen wir alle Personen und starten mit der zufällig gewählten ersten Person.

do_it :- 
 findall(X,person(X),Z),
 random_permutation(Z, S),
 finde_paar(S, []).
:- do_it.

Das Ergebnis ist eine zufällige Ziehung unter Berücksichtigung aller Ausnahmen oder negativ, wenn es keine mögliche Ziehung mit dieser Startperson gibt. Ausprobieren und anpassen, kann man den Ansatz einfach online.

Fazit

Der Algorithmus ist recht allgemein gehalten und kann so oder so ähnlich für viele sogenannte Constraint-Satisfaction-Problems genutzt werden. Diese Probleme sind oft Aufgabenstellungen aus dem Bereich der klassischen Künstlichen Intelligenz und befassen sich damit, dass eine zulässige Belegung von Variablen gefunden wird, sodass bestimmte Bedingungen erfüllt sind. Bekannte Beispiele sind das Damenproblem, das Vier-Farben-Problem und Sudoku.

Da wir nun erfolgreich die Wichtel untereinander zulosen können, kann die entspannte Weihnachtszeit beginnen. Fröhliche Feiertage allerseits.

zurück zur Blogübersicht