Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


34. Paarung



Problem der stabilen Ehe

Das zu Beginn dieses Kapitels angeführte Beispiel, in dem es um Medizinstudenten und Krankenhäuser ging, wird offenbar von den Beteiligten sehr ernst genommen. Doch das Verfahren, das wir für die Realisierung der Paarung betrachten wollen, läßt sich vielleicht anhand eines etwas heiteren Modells der Situation besser verstehen. Wir nehmen an, daß N Herren und N Damen gegeben sind, die ihre gegenseitigen Präferenzen zum Ausdruck gebracht haben (jeder Herr muß genau sagen, wie er zu jeder der N Damen steht und umgekehrt). Das Problem besteht darin, eine Menge von N Ehen zu finden, bei der die Präferenzen aller Beteiligten berücksichtigt werden.

Wie sollten die Präferenzen ausgedrückt werden? Eine Methode wäre, die Skala »1-10« zu benutzen, wobei jede Seite einigen Personen des anderen Geschlechts eine absolute Bewertung zuordnet. Dies bewirkt, daß das Eheproblem dem Problem der gewichteten Paarung, dessen Lösung relativ kompliziert ist, entspricht. Außerdem kann die Verwendung von absoluten Skalen selbst zu Ungenauigkeiten führen, da die Skalen der Personen nicht übereinstimmen würden (die 10 einer Dame könnte der 7 einer anderen Dame entsprechen). Eine natürlichere Methode, die Präferenzen zum Ausdruck zu bringen, besteht darin, daß man jede Person alle Personen des anderen Geschlechts entsprechend der Reihenfolge ihrer Präferenz aufführen läßt. Abbildung 34.4 zeigt eine Menge von Präferenzlisten, wie sie innerhalb einer Menge von fünf Damen und fünf Herren existieren könnte. Wie üblich (und aus Gründen der Diskretion!) setzen wir voraus, daß Hashing oder irgendein anderes Verfahren angewandt wurde, um die wahren Namen in einzelne Ziffern für Damen und einzelne Buchstaben für Herren umzuwandeln.

Es ist klar, daß diese Präferenzen oft kollidieren: Zum Beispiel geben sowohl A als auch C die Dame 2 als ihre erste Wahl an, und niemand scheint 4 sehr zu mögen (doch einer muß sie bekommen). Die Aufgabe besteht darin, alle Damen mit allen Herren so zu verloben, daß sämtliche Präferenzen in möglichst hohem Grade berücksichtigt werden, und dann in einer großen Zeremonie N Hochzeiten zu feiern. Bei der Entwicklung einer Lösung müssen wir davon ausgehen, daß jeder, der nicht seiner ersten Wahl zugeordnet wurde, enttäuscht ist und immer jemanden bevorzugen wird, der in seiner Liste weiter oben steht. Eine Menge von Ehen wird instabil genannt, wenn zwei nicht miteinander verheiratete Personen einander ihren Ehegatten gegenüber bevorzugen. Zum Beispiel ist die Zuordnung A1 B3 C2 D4 E5 instabil, denn A zieht 2 gegenüber 1 vor, und 2 bevorzugt A gegenüber C. Daher würde A, wenn die Personen ihren Präferenzen entsprechend handeln, 1 wegen 2 verlassen, und 2 würde C wegen A verlassen (womit 1 und C kaum eine andere Wahl hätten, als sich zusammenzutun).

Abbildung 34.4
Abbildung 34.4 Präferenzlisten für das Problem der stabilen Ehe.

Die Bestimmung einer stabilen Konfiguration scheint auf den ersten Blick ein kompliziertes Problem zu sein, da es so viele mögliche Zuordnungen gibt. Selbst die Bestimmung, ob eine Konfiguration stabil ist, ist nicht einfach, wovon sich der Leser überzeugen kann, indem er (vor dem Lesen des folgenden Absatzes) in dem obigen Beispiel das instabile Paar nach der Bildung der neuen Paare A2 und C1 sucht. Im allgemeinen gibt es für eine gegebene Menge von Präferenzlisten viele verschiedene stabile Zuordnungen, und wir brauchen nur eine zu finden. (Die Bestimmung aller stabilen Zuordnungen ist ein viel komplizierteres Problem.)

Ein möglicher Algorithmus zur Bestimmung einer stabilen Konfiguration könnte darin bestehen, ein instabiles Paar nach dem anderen zu entfernen. Dieser Prozeß ist jedoch nicht aufgrund der für die Feststellung der Stabilität benötigten Zeit nur langsam, sondern er ist nicht einmal notwendigerweise endlich! Nachdem zum Beispiel A2 und C1 in dem obigen Beispiel als Paare gebildet wurden, stellen B und 2 jeweils ein instabiles Paar dar, was zu der Konfiguration A3 B2 C1 D4 E5 führt. Bei dieser Zuordnung bilden B und 1 jeweils ein instabiles Paar, was zu der Konfiguration A3 B1 C2 D4 E5 führt. Schließlich bilden A und 1 jeweils eine instabile Konfiguration, die zurück zu der ursprünglichen Konfiguration führt. Ein Algorithmus, der versucht, das Problem der stabilen Ehe zu lösen, indem er ein instabiles Paar nach dem anderen entfernt, gerät notwendigerweise in diese Art von Schleifen.

Wir wollen stattdessen einen Algorithmus betrachten, der versucht, systematisch stabile Paarungen zu erzeugen. Dabei benutzt er eine Methode, die darauf beruht, was in der ein wenig idealisierten »realen« Variante des Problems geschehen könnte. Die Idee besteht darin, jeden der Herren der Reihe nach einen »Bewerber« werden und eine Braut suchen zu lassen. Offensichtlich besteht der erste Schritt seiner Suche darin, der ersten Dame auf seiner Liste einen Antrag zu machen. Falls diese bereits mit einem Herrn verlobt ist, den sie bevorzugt, muß unser Bewerber die nächste Dame auf seiner Liste ansprechen und damit fortfahren, bis er eine Dame findet, die nicht verlobt ist oder ihn ihrem gegenwärtigen Bräutigam vorzieht. Falls diese Dame nicht verlobt ist, so verlobt sie sich mit dem Bewerber, und der nächste Herr wird Bewerber. Falls sie bereits verlobt ist, so löst sie die Verlobung und verlobt sich mit dem Bewerber (den sie bevorzugt). Dadurch bleibt ihrem alten Bräutigam nichts weiter übrig, als nochmals Bewerber zu werden, wobei er in seiner Liste wieder dort beginnt, wo er aufgehört hatte. Eventuell findet er eine neue Braut, doch dazu muß vielleicht eine andere Verlobung gelöst werden. Wir fahren in dieser Weise fort, wobei wir, wenn nötig, Verlobungen lösen, bis ein Bewerber eine Dame findet, die noch nicht verlobt war.

Dieses Verfahren mag vielleich das Geschehen mancher Romane des 19. Jahrhunderts modellieren, doch es ist eine sorgfältige Untersuchung notwendig, um zu zeigen, daß dadurch eine stabile Menge von Zuordnungen erzeugt wird. Abbildung 34.5 zeigt die Folge von Ereignissen für die Anfangsetappen des Prozesses für unser Beispiel. Zuerst macht A der Dame 2 (seiner ersten Wahl) einen Antrag und wird erhört; danach macht B der Dame 1 (seiner ersten Wahl) einen Antrag und wird erhört; dann macht C der Dame 2 einen Antrag, wird abgewiesen, macht 3 einen Antrag und wird erhört, wie es in der dritten Skizze schematisch dargestellt ist.

Abbildung 34.5
Abbildung 34.5 Lösung des Problems der stabilen Ehe.

Jede Skizze zeigt die Folge von Ereignissen, die eintreten, wenn ein neuer Herr als Bewerber auszieht, um eine Braut zu suchen. Jede Linie gibt die »verwendete« Präferenzliste für den betreffenden Herrn an, und jedes Kettenglied ist mit einer ganzen Zahl markiert, die angibt, wann dieses Kettenglied durch diesen Herrn benutzt wurde, um dieser Dame einen Antrag zu machen. Diese zusätzliche Information ist von Nutzen, um die Folge von Anträgen zu verfolgen, wenn D und E Bewerber werden: Wenn D der Dame 1 einen Antrag macht, kommt es zu unserer ersten gelösten Verlobung, da 1 den Herrn D gegenüber Herrn B vorzieht. Daraufhin wird B Bewerber und macht 2 einen Antrag; dies führt zu unserer zweiten gelösten Verlobung, da 2 den Herrn B gegenüber A bevorzugt. Danach wird A Bewerber und macht 5 einen Antrag, was eine stabile Situation ergibt. Doch diese Stabilität ist nur von zeitweiliger Natur! Der Leser kann die Folge der Anträge verfolgen, die gemacht werden, wenn E zum Bewerber wird: Die Situation stabilisiert sich erst, nachdem acht Anträge gemacht worden sind. Wir bemerken, daß E in diesem Prozeß zweimal die Rolle des Bewerbers übernimmt.

Der erste Schritt bei der Implementation besteht in der Festlegung der Datenstrukturen, die für die Präferenzlisten benutzt werden sollen. Diese sind als abstrakte Datenstrukturen einfache lineare Listen, doch wie wir von den Beispielen in Kapitel 3 und anderen Stellen wissen, kann die richtige Wahl der Darstellung die Leistungsfähigkeit unmittelbar beeinflussen. Auch in diesem Falle sind für die Herren und die Damen unterschiedliche Strukturen geeignet, da sie die Präferenzlisten auf unterschiedliche Weise benutzen.

Die Herren gehen ihre Präferenzlisten einfach der Reihe nach durch, so daß jede Implementation linearer Listen verwendet werden könnte. 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] die w-te Dame auf der Präferenzliste des m-ten Herren. Außerdem müssen wir registrieren, wie weit jeder Herr 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 der nächsten Dame auf der Präferenzliste des m-ten Herren ist; ihr Bezeichner ist in prefer[m,next[m]+1] zu finden.

Für jede Dame müssen wir ihren Bräutigam registrieren (fiancée[w] bezeichnet den Herrn, der mit der Dame w verlobt ist), und wir müssen in der Lage sein, die Frage »Ist der Herr s dem Herrn fiancée[w] vorzuziehen?« zu beantworten. Dies könnte getan werden, indem die Präferenzliste sequentiell durchsucht wird, bis entweder s oder fiancée[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 Herrn s auf der Präferenzliste der Dame w. Für das obige Beispiel gilt, daß rank[1,1] gleich 2 ist, da A an zweiter Stelle auf der Präferenzliste von 1 steht, daß rank[5,4] gleich 1 ist, da D an erster Stelle auf der Präferenzliste von 5 steht usw.

Die Eignung des Bewerbers s kann sehr schnell bestimmt werden, indem geprüft wird, ob rank[w,s] kleiner als rank[w,fiancée[w]] ist. Diese Felder lassen sich leicht unmittelbar aus den Präferenzlisten erzeugen. Abschließend benötigen wir noch einen als »Marke« dienenden Herrn 0 als anfänglichen Bewerber und setzen diesen an das Ende der Präferenzlisten aller Damen.

Mit den in dieser Weise initialisierten Datenstrukturen ist die Implementation, so wie sie oben beschrieben wurde, sehr einfach:

    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 Herrn, der nicht verlobt ist, und endet mit einer nicht verlobten Dame. Die repeat-Schleife muß abbrechen, da die Liste jedes Herrn jede Dame enthält und jede Iteration der Schleife die Liste irgendeines Herrn inkrementiert; dazu muß folglich eine nicht verlobte Dame gefunden werden, ehe die Liste aller Herren abgearbeitet ist. Die durch den Algorithmus erzeugte Menge der Verlobungen ist stabil, da jede Dame, die irgendein Herr gegenüber seiner Braut bevorzugt, mit jemandem verlobt ist, den sie ihm gegenüber bevorzugt.

Eigenschaft 34.2 Das Problem der stabilen Ehe kann in linearer Zeit gelöst werden.

Wie soeben erwähnt wurde, inkrementiert jede Iteration der Schleife die Präferenzliste irgendeines Herrn. Im ungünstigsten Fall werden alle Einträge der Liste betrachtet (doch kein Eintrag wird zweimal betrachtet). In Wirklichkeit ist es möglich, daß der Algorithmus viel weniger Zeit als zur Erzeugung der Listen erforderlich benötigt, da eine stabile Konfiguration gefunden werden könnte, lange bevor alle Listen abgearbeitet sind. Diese Art von Überlegungen führt zu einer Anzahl interessanter analytischer Probleme. w.z.b.w.

Dieser Algorithmus ist offensichtlich in verschiedener Hinsicht unausgeglichen. Erstens gehen die Herren die Damen auf ihren Listen der Reihe nach durch, während die Damen warten müssen, bis der »richtige Mann« kommt. Diese Asymmetrie kann korrigiert werden (auf etwas einfachere Weise als im realen Leben), indem die Reihenfolge, in der die Präferenzlisten eingegeben werden, vertauscht wird. Dies erzeugt die stabile Konfiguration 1E 2D 3A 4C 5B, bei der jede Dame ihre »erste Wahl« bekommt, außer 5, die ihre zweite Wahl bekommt. Im allgemeinen können viele stabile Konfigurationen existieren; es läßt sich zeigen, daß diese »optimal« für die Damen ist, daß also keine andere stabile Konfiguration irgendeiner Dame eine bessere Wahl von ihrer Liste geben würde. (Natürlich ist die erste stabile Konfiguration für unser Beispiel optimal für die Herren.)

Eine anderes Merkmal des Algorithmus, das asymmetrisch zu sein scheint, ist die Reihenfolge, in der die Herren zum Bewerber werden: Ist es besser, der erste Herr zu sein, der einen Antrag macht (und daher wenigstens für kurze Zeit mit seiner ersten Wahl verlobt zu sein), oder der letzte (und daher weniger der Gefahr ausgesetzt zu sein, unter den Unannehmlichkeiten einer gelösten Verlobung leiden zu müssen)? Die Antwort lautet, daß dies keineswegs eine Asymmetrie ist; die Reihenfolge, in der die Herren zum Bewerber werden, spielt keine Rolle. Solange entsprechend den Listen jeder Herr Anträge macht und jede Dame Anträge annimmt, ergibt sich die gleiche stabile Konfiguration.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]