Moin!
Hier also die Lösung zur LAN-Party.
Das grundlegende Problem wird in der Literatur als "Das Problem der stabilen Ehe" ("
stable marriage problem" oder "stable match") bezeichnet. Es existiert eine sehr effiziente Referenzlösung von Gale und Shapley aus dem Jahre 1962, die einen
linearen Aufwand hat.
Aus diesem Grund haben wir die Basis-Lösung für kombinatorische Probleme - Backtracking (=exponentieller Aufwand!) - ausgeschlossen.
Das ist hier schließlich eine Paranuss...
Die Idee besteht darin, jeden Wichtel der Reihe nach einen »Bewerber« werden und ein Engelchen suchen zu lassen. Offensichtlich besteht der erste Schritt der Suche darin, dem ersten Engelchen auf seiner Liste einen Antrag zu machen. Falls dieses bereits mit einem Wichtel im Team ist, den es bevorzugt, muß unser Wichtel das nächste Engelchen auf seiner Liste ansprechen und damit fortfahren, bis er ein Engelchen findet, das nicht im Team ist oder ihn ihrem gegenwärtigen Teampartner vorzieht. Falls dieses Engelchen nicht in einem Team ist, so bildet es mit dem Bewerber ein Team, und der nächste Wichtel wird Bewerber. Falls das Engelchen bereits im Team ist, so löst es das Team auf und bildet ein Neues mit dem Bewerber (den es bevorzugt). Dadurch bleibt dem alten Teampartner-Wichtel nichts weiter übrig, als nochmals Bewerber zu werden, wobei er in seiner Liste wieder dort beginnt, wo er aufgehört hatte. Eventuell findet er einen neuen Teampartner, doch dazu muß vielleicht ein anderes Team aufgelöst werden. Wir fahren in dieser Weise fort, wobei wir, wenn nötig, Teams auflösen, bis ein Bewerber ein Engelchen findet, das noch nicht im Team ist.
Die Wichtel gehen ihre Präferenzlisten einfach der Reihe nach durch, so daß jede Implementation linearer Listen verwendet werden kann. Da die Präferenzlisten alle die gleiche Länge haben, ist es am besten, eine einfache Implementation als zweidimensionales Feld zu benutzen. Zum Beispiel bezeichnet
prefer[m,w] das w-te Engelchen auf der Präferenzliste des m-ten Wichtels. Außerdem müssen wir registrieren, wie weit jeder Wichtel auf seiner Liste gekommen ist. Dies kann mit einem eindimensionalen Feld
next realisiert werden, das mit 0 initialisiert wird, wobei
next[m]+1 der Index des nächsten Engelchens auf der Präferenzliste des m-ten Wichtels ist; der Bezeichner ist in
prefer[m,next[m]+1] zu finden.
Für jedes Engelchen müssen wir den Teampartner registrieren (
fiancee[w] bezeichnet den Wichtel, der mit Engelchen w im Team ist), und wir müssen in der Lage sein, die Frage »Ist Wichtel
s dem Wichtel
fiancee[w] vorzuziehen?« zu beantworten. Dies könnte getan werden, indem die Präferenzliste sequentiell durchsucht wird, bis entweder
s oder
fiancee[w] gefunden wird, doch diese Methode wäre sehr ineffizient, wenn sich beide nahe dem Ende befinden. Was benötigt wird, ist die zur Präferenzliste »inverse« Liste:
rank[w,s] ist der Index des Wichtel
s auf der Präferenzliste des Engelchens
w.
Die Eignung des Bewerbers
s kann sehr schnell bestimmt werden, indem geprüft wird, ob
rank[w,s] kleiner als
rank[w,fiancee[w]] ist. Diese Felder lassen sich leicht unmittelbar aus den Präferenzlisten erzeugen. Abschließend benötigen wir noch einen als »Marke« dienenden Wichtel 0 als anfänglichen Bewerber und setzen diesen an das Ende der Präferenzlisten aller Engelchen.
Mit den in dieser Weise initialisierten Datenstrukturen ist die Implementation, so wie sie oben beschrieben wurde, sehr einfach:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
| for m := 1 to N do begin
s := m;
repeat
next[s] := next[s] +1;
w := prefer[s,next[s]];
if (rank[w,s] < rank[w,fiancee[w]]) then begin
t := fiancee[w];
fiancee[w] := s;
s := t;
end;
until (s = 0);
end; |
Jede Iteration beginnt mit einem Wichtel, der nicht im Team ist, und endet mit einem nicht im Team befindlichen Engelchen. Die repeat-Schleife muß abbrechen, da die Liste jedes Wichtels jedes Engelchen enthält und jede Iteration der Schleife die Liste irgendeines Wichtels inkrementiert; dazu muss folglich ein nicht im Team befindliches Engelchen gefunden werden, ehe die Liste aller Wichtel abgearbeitet ist. Die durch den Algorithmus erzeugte Menge der Teams ist stabil, da jedes Engelchen, das irgendeinen Wichtel gegenüber seinem Team-Partner bevorzugt, mit jemandem im Team ist, den es ihm gegenüber bevorzugt.
Im Anhang befindet sich eine Musterlösung, die nach diesem Ansatz arbeitet. Eine sehr ausführliche, deutsche Beschreibung findet sich in: Sedgewick, Robert: Algorithmen, Addison Wesley (1992), ISBN-10: 3893194029, ISBN-13: 978-3893194025
Wir wünschen allen Mitspielern viel Glück bei der Auswertung!
cu
Narses
Narses
