PROBLEMA DEL MATRIMONIO PERFECTO

Concepto


Se caracteriza por tener una gran cantidad de aplicaciones . Consiste en la idea de tener un grupo de hombres y otro de mujeres con y cada uno de ellos tiene una lista de preferencia sobre las personas pertenecientes al sexo opuesto. El objetivo es encontrar parejas estables entre estos dos grupos según sus preferencias.

aplicación

En realidad tiene aplicaciones en diversos campos como por ejemplo:
Ingenierias – informatica, robotica – ingenieria genetica
Educación :Argentina lo esta utilizando para el emparejamiento de universitarios para diferentes universidades .
En nuestro campo funciona como un decisor.

Estabilidad en emparejamientos
Se atiende a las preferencias de las parejas.
Objetivo: “estabilidad”
{X,Y,Z,W} {A,B,C,D}

X A B C D A Z X Y W
Y A C B D B Y W X Z
Z C D A B C W X Y Z
W C B A D D X Y Z W
Listados de preferencias
El emparejamiento M={XA, YC, ZD, WB} no es estable
W y C se “divorciarán”

verificación

Dado un emparejamiento M, es estable?
Para cada chica, verificar que no haya parejas que bloqueen: es decir, todos los chicos en su preferencia, esta con el que mas prefiere.
boolean Estabilidad(M)
for g ∈ G{
for b ∈ B ∋ g prefiere b a pM(g){
if (b prefiere a g en vez de pM(b))
return false;
}
}
return true;

Encontrar el chico que g prefiere sobre su pareja puede ser hecho usando una lista o una matriz de preferencias.
¿Como verificar si un chico prefiere una chica en vez de otra?
Puede usar matriz de preferencia o matriz de ranking

ALGORITMO DE GALE - SHAPLEY

Dado el problema anterior es un Algoritmo simple para encontrar un emparejamiento estable(trataremos el caso orientado a las chicas):
Las chicas sucesivamente van proponiendose a los chicos (los cuales pueden estar o no comprometidos)
Si una chica se propone a un chico que esta libre (aun no esta con pareja), entonces el chico “acepta” la propuesta
Si la chica se declara a un chico que ya tiene pareja, entonces:
Si la propuesta es mejor desde el punto de vista del chico, entonces el chico rompe su antiguo compromiso y acepta el nuevo, sin embargo, si la propuesta no es mejor, el chico rechaza la propuesta

PASOS  : MAS ORDENADOS

Paso 1: Cada mujer propone su primera elección.
Paso 2: Los hombres con dos o más propuestas responden rechazando a todas menos a la más favorable.
Paso 3: Las mujeres rechazadas proponen su segunda elección.
Las que no fueron rechazadas continúan con su propuesta.
Paso 4: Se repiten los pasos 2 y 3 hasta que ninguna propuesta sea rechazada.

asignar cada persona libre;
while( alguna chica g esta libre)
Sea b el primer chico en la lista de g al cual g no se ha declarado;
si b esta libre
emparejar b y g;
en caso contrario
si b prefiere g a su novia g'
hacer g' sea libre
emparejar b y g
en caso contrario
b rechaza a g;

Para mejorar el algoritmo podemos hacer :

Un array p que mantenga a los novios y novias que hallan sido encontrados.
Cuando el algoritmo termina este almacenara el emparejamiento
Dos conjuntos ChicosLibres y ChicasLibres que registren a los chicos y chicas sin pareja
Un arreglo sigpropuesta con una entrada para cada chica
Mantener, para cada chica g, el indice de la lista de preferencia de g del primero chico al cual ella no se ha declarado
Inicialmente, sigpropuesta esta inicializado a ceros

EmpareamientoEstable
ChicosLibres ← B; ChicasLibres ← G;
sigpropuesta ← {0,0,...,0};
while ChicasLibres = 0{
escoger g ∈ ChicasLibres;
b <- gp[g][sigpropuesta[g]];
sigpropuesta[g]++;
if (b ∈ ChicosLibre){
p[g] ← b; ChicasLibres ← ChicasLibres - {g}
p[b] ← g; ChicosLibres ← ChicosLibres - {b}
else
if (br[b][g] < br[b][p[b]]{
ChicasLibres ← ChicasLibres U {p[b]} - {g};
p[g] ← b; p[b] ← g;