Der Heiratsalgorithmus

AK der Algorithmik 5 – Übungsblatt 1 – SS 2004
Gruppe E
Sophie Schnabel, Daniel Abouakil
Aufgabe 1 - Der Heiratsalgorithmus
Der Heiratsalgorithmus in Pseudocode:
{M: Menge der Männer; F: Menge der Frauen; H: Menge der verlobten Paare}
H = leere Menge;
Solange m aus M nicht verlobt existiert:
m acht Antrag an oberste Frau auf seine List:
Wenn f noch nicht verlobt => Antrag annehmen
H = H + {m, f}
Sonst
Wenn m höhergereiht als Verlobter(f) Dann:
Verlobter(f) streicht f von seiner Liste;
H = H \ {Verlobter(f), f};
H = H + {m, f};
Sonst:
m streicht f von seiner Liste;
Massenhochzeit!
a.) Beweisen Sie, dass höchstens ein Mann seine letzte Wahl heirate muss.
Gedanken dazu:
Ein Mann endet nur dann mit seiner schlechtesten Wahl enden kann wenn er bereits alle
anderen Frauen einen Antrag gemacht hat und von ihnen abgewiesen wurde (da er nur unter
dieser Bedingung seine Letztgereihte fragen würde).
Wenn ein Mann alle anderen (n-1) Frauen bereits gefragt hat und von allen abgewiesen
wurde, so heißt dies dass n-1 Frauen bereits verlobt sind, da nur eine verlobte Frau eine
Abweisung erteilen kann. Fragt er nun seine Letztgereihte muss diese die letzte freie Frau sein
(alle anderen n-1 Frauen sind ja schon vergeben) und sie muss so seinen Antrag annehmen.
Endet er mit seiner Letztgereihten, so sind alle Frauen verlobt und der Algorithmus beendet.
Endet ein Mann mit seiner schlechtesten Frau heißt das also dass alle Frauen vergeben
sind und der Algorithmus somit terminiert. Es können somit nicht 2 Männer mit ihren
letztgereihten Frauen enden, da der Algorithmus ja auch nicht zweimal terminieren kann.
Äquivalente Begründung. Ein Mann kann nur dann mit seiner letztgereihten Frau verheiratet
werden, wenn sie die letzte ungebundene Frau ist und er der letzte Mann, der noch keine Frau
gefunden hat. Denn ein Mann fragt seine letztgereihte Frau nur dann, wenn er bereits alle
anderen Frauen gefragt hat und er von allen abgewiesen wurde (entweder direkt oder
indirekt). Das kann nur geschehen wenn alle anderen Frauen bereits vergeben sind. Da die
beiden Männer zwei verschiedene letztgereihte Frauen haben und nur eine Frau die letzte
noch ungebundene Frau sein kann, kann höchstens ein Mann am Ende des Algorithmus mit
seiner letztgereihten Frau verheiratet sein.
b.) Überlegen Sie sich ein Worst-Case-Beispiel, an dem mindestens 4 Paare beteiligt sind.
Schätzen Sie dann die Worst-Case-Laufzeit im allgemeinen Fall ab.
Um den Worst-Case zu erreichen müssen wir eine Konstellation bilden bei der es ein
Maximum an Verdrängungen gibt. (Verdrängung: Mann ist bereits mit Frau verlobt aber wird
durch einen anderen Mann verdrängt) Da wir n Männer haben und genausoviel Frauen ist mit
Sicherheit n-1 eine obere Schranke für die Verdrängungen pro Frau. Eine Frau kann ja nur
maximal n mal verlobt werden und der letzte Mann ist dann ihr fixer Gatte. Demnach kann es
nur n-1 Verdrängungen geben.
Frage:
gibt es eine Zusammenstellung dass jeder Mann sich mit n Frauen verlobt und es somit n-1
Verdrängungen pro Frau/Mann gibt?
Antwort:
Nein, es können ja nur maximal n-1 Frauen verlobt sein, dass der Algorithmus terminiert. Ein
Frau die einmal verlobt wurde, bleibt immer verlobt.
Lösungsansatz: wir schauen am Anfang, dass jeder Mann (bis auf den letzten) mit
verschiedenen Frauen zusammen ist.
A: a,_,_,_ B:b,_,_,_
C:c,_,_,_
D: _,_,_,_
a: _,_,_, A b:_,_,_,B
c:_,_,_,C
d: egal
AÆa
BÆb
CÆc
DÆfrei
Um eine Verdrängung zu erzeugen nimmt der übriggebliebene letzte Mann D einem bisher
verlobten Mann (z.b. A) die Frau weg:
A: a,_,_,_ B:b,_,_,_
C:c,_,_,_ D:a ,_,_,_
A:_,_,D,A b:_,_,_,B
c:_,_,_,C d: egal
AÆfrei
BÆb
CÆc
DÆa
Nun wir Mann A wieder frei und nimmt seine 2. Wahl, die Frau b
A: a,_,_,_ B:b,_,_,_
A:_,_,D,A b:_,_,A,B
AÆb
BÆfrei
C:c,_,_,_ D:a ,_,_,_
c:_,_,_,C d: egal
CÆc
DÆa
Dieser wiederum produziert mit seiner 2.Frau b wieder eine Verdrängung und ein anderer
Mann (B) wird frei.
Solange man die letzte Frau (die noch nie einen Antrag hatte) nicht fragt, läuft der
Algorithmus weiter. Dadurch dass immer ein Mann einen anderen verdrängt, geht das ganze
solange bis jeder Mann bereits n-1 Frauen hatten, da ja die letzte nicht gefragt werden darf.
Jetzt haben wir eine Situation dass der letzte freie Mann keine andere Wahl hat als seine letzte
Frau zu nehmen und der Algorithmus terminiert.
Vollständiges Beispiel:
Männer
A: a,b,c,d B: b,c,a,d
C: c,a,b,d
D: a,c,b,d
Frauen:
a: B,C,D,A b: D,C,A,B
c: A,D,B,C
d: egal
1. Runde:
2. Runde:
3. Runde:
4. Runde:
5. Runde:
6. Runde:
7. Runde:
8. Runde:
9. Runde:
10.Runde:
11.Runde:
CÆc , DÆf
CÆc , DÆa
CÆc , DÆa
CÆf , DÆa
CÆa , DÆf
CÆa , DÆc
CÆf , DÆc
CÆb, DÆc
CÆb, DÆf
CÆf, DÆb
CÆd, DÆb
AÆa , BÆb,
AÆf , BÆb,
AÆb , BÆf,
AÆb , BÆc,
AÆb , BÆc,
AÆb , BÆf,
AÆb , BÆa,
AÆf , BÆa,
AÆc , BÆa,
AÆc , BÆa,
AÆc , BÆa,
Die Traumpaare können nun heiraten
Somit haben wir (n-2) Verdrängungen pro Mann, insgesamt dann (n-2)*n+1 Verdrängungen
Jeder Mann macht (n-1) Anträge somit in Summe (n-1)*n+1 = (n-1)² + n Anträge
Es gibt 0 Abweisungen
Für jede Scheidung muss die äußerste Schleife des Algorithmus noch einmal
durchlaufen werden. Es gibt maximal (n-2)*n + 1 Scheidungen. Der Algorithmus hat
demnach ein O(n²).

Download Report