El llamado The Stable Marriage Problem o 'Problema de las Parejas Estables' fue planteado y resuelto mediante un algoritmo por David Gale y Lloyd Shapley en 1962. Su aplicación más conocida es la asignación de estudiantes de medicina recién graduados a los hospitales correspondientes.
Cada chico ordena a sus posibles compañeras según sus preferencias y viceversa. En el ejemplo de la tabla el VERDE indica si forman pareja y el ROJO si no pueden ser pareja por el rechazo de la chica.
Cada chico ordena a sus posibles compañeras según sus preferencias y viceversa. En el ejemplo de la tabla el VERDE indica si forman pareja y el ROJO si no pueden ser pareja por el rechazo de la chica.
- Cada chico invita a bailar a su primera opción.
- Cada chica evalúa las propuestas, escoge la mejor y desecha las demás.
- Cada chico rechazado invita a bailar a su segunda opción, aunque en ese momento esté con otro.
- Se itera el proceso hasta que todas las chicas tengan una única invitación.
(Diego,Elena), (Jorge,Paula), (Mateo,Julia) y (Pedro,Laura).
¡¡¡ Siempre hay un emparejamiento estable!!!
1 comentario:
Yo creo que donde dice: "Todos eligen a su chica preferida, pero como Julia prefiere a Mateo, rechaza a Pedro." debe decir Todos eligen a su chica preferida, pero como Julia prefiere a Mateo, rechaza a Diego". ¿no?
Publicar un comentario