|
|
|
\require{AMSmath}
Slechtste partner in Gale Shapley
Beste,
Gegeven is het stable marriage algoritme van Gale Shapley. Claim: Het algoritme matcht elke vrouw met haar slechtst mogelijk partner. In slide 24 van https://ocw.tudelft.nl/wp-content/uploads/Algoritmiek_Stable_Matching__continued_.pdf staat in de tweede regel van het bewijs dat er een matching S' bestaat met een eigenschap. Hoe weten we zo zeker dat S' moet bestaan met die eigenschap? Ik zie niet uit welke aanname dat volgt.
Vriendelijke groet,
Nico
Nico
Student universiteit - vrijdag 11 februari 2022
Antwoord
Dat volgt uit de definitie van "valid partner" eerder op de slides.
Op slide 25 staat een verwijzing naar het cursusboek (links onderaan). Dat boek is online te bekijken, zie hieronder, en dus in het bijzonder pagina's 11 en 12.
Het boek geeft wat meer uitleg dan de slides.
Zie Boek: Algorithm Design
kphart
|
Vragen naar aanleiding van dit antwoord? Klik rechts..!
vrijdag 11 februari 2022
|
|
home |
vandaag |
bijzonder |
gastenboek |
statistieken |
wie is wie? |
verhalen |
colofon
©2001-2024 WisFaq - versie 3
|
Re: Slechtste partner in Gale Shapley