Algoritmo de Gale-Shapley. Variaciones y alternativas
Fecha
2015-04-01Autor
Mínguez Martínez Juan Pablo
Metadatos
Mostrar el registro completo del ítemResumen
En esta memoria se trata el problema de encontrar un algoritmo que construya
un emparejamiento entre dos grupos, entendiendo por emparejamiento
la asignacion a cada individuo, de cada grupo, otro individuo. La situaci on
inicial de la que parte el problema es la siguiente:
Dos grupos, los proponentes y los propuestos, que est an formados por
n individuos cada uno, siendo n la dimensi on del problema.
El grupo de los proponentes es el encargado de hacer las propuestas
a la hora de construir el emparejamiento.
El grupo de los propuestos es el encargado de recibir y gestionar
las propuestas a la hora de construir el emparejamiento.
Cada individuo de cada grupo ordena en una lista, de manera decreciente,
a individuos del otro grupo atendiendo a su preferencia a la
hora de ser emparejado, a esta lista la llamaremos lista de preferencia
del individuo, considerando el quedarse solo la opci on menos preferida
de entre las aceptables.
El objetivo del problema es crear un emparejamiento en el que cada pareja
sea satisfactoria para los individuos que la crean en base a las preferencias
de cada uno.