Problema de las parejas
De Wikipedia, la enciclopedia libre
Este artículo o sección necesita ser wikificado con un formato adecuado a las convenciones de estilo de Wikipedia.
Por favor, edítalo para cumplir con ellas. No elimines este aviso hasta que lo hayas hecho. ¡Colabora wikificando!
Este artículo debería estar en Wikilibros ya que es una guía o manual en vez de un verdadero artículo enciclopédico.
Si modificas este artículo dándole una orientación enciclopédica, elimina por favor esta plantilla.
El problema de las parejas es un problema de programación que se resuelve mediante la técnica de vuelta atrás o backtracking.
Tabla de contenidos |
[editar] Descripción del problema
El problema de las parejas plantea que, dado un conjunto de n hombres y n mujeres y la información necesaria sobre la preferencia de cada hombre por cada mujer y viceversa, el problema consiste en encontrar un algoritmo que encuentre todos los emparejamientos estables. Un emparejamiento es estable si no existe un hombre o mujer que prefiera más a la pareja de otro frente a la suya.
[editar] Solución
Suponemos que los hombres y las mujeres están numerados de 1 a n. Una solución consiste en una asignación de hombres a mujeres (o viceversa) de forma que a toda mujer le corresponde uno de los hombres existentes y cada hombre ha sido asignado una sola vez. Además debe cumplirse el criterio de estabilidad.
Para realizar el problema se necesitan dos vectores:
- Para representar la solución utilizamos un vector (x1,...,xn) donde xi es el hombre asignado a la mujer i.
- Para controlar los hombres que ya se han asignado a una pareja usaremos un vector asignados[1..n] de booleanos. Este vector indica si el hombre i ya ha sido asignado.
Criterio de Estabilidad: Vamos a ir construyendo una solución parcial que será un conjunto de parejas estables, lo que supone:
- a) La nueva asignación lleva implícita si la nueva pareja desestabiliza la solución anterior. Si la desestabilizase, se rechaza al hombre que se está considerando y se pasa a considerar el siguiente posible. En caso de que la solución incluyendo el emparejamiento actual sea estable se continúa por ese camino.
- b) Dada una solución parcial (1,x1)...(k-1,xk − 1) y una nueva pareja (k, xk) entonces comprobar la estabilidad de la secuencia consiste en:
-
- b.1) La mujer k prefiere al hombre xk más que al resto de hombres que tienen asignadas las otras parejas (c1) o bien que ninguno de los hombres de las restantes parejas prefiera más a la mujer k que al resto de sus parejas (c2).
-
- b.2) El hombre xk prefiere a la mujer k más que al resto de mujeres de las restantes parejas (c3) o bien que ninguna de las mujeres de las restantes parejas prefieren más al hombre xk que al resto de las parejas (c4).
[editar] Árbol de Exploración
El árbol de exploración tiene n niveles con n hijos por nodo.
[editar] Implementación en Pseudocódigo
En primer lugar se implementa el procedimiento principal, después su llamada inicial y finalmente la función auxiliar estable.
El procedimiento principal usa la técnica de vuelta atrás. Si el hombre actual todavía no se ha incluido en la solución parcial se añade y se marca como añadido. Si la solución parcial actual es estable y se ha llegado al último hombre se devuelve la solución, en caso contrario se realiza una llamada recursiva al procedimiento actualizando los parámetros k y el vector asignado.
Después de salir de esta condición se desmarca el hombre asignado para que al hacer vuelta atrás pueda explorarse el resto de caminos del arbol de exploración desde ese nodo.
[editar] Algoritmo de Vuelta a Atrás
proc parejas-va (H[1..n,1..n], M[1..n,1..n] de nat, sol[1..n] de 1..n, k :1..n; asignado[1..n] de bool)
para hombre=1 hasta n hacer
si NOT asignado[hombre] entonces
sol[k]:= hombre;
asignado[hombre]:=cierto; //marcar
si estable(H,M,sol,k) entonces
si k=n entonces imprimir(sol) ;
sino parejas(H,M,sol, k+1,asignado)
fsi
fsi
asignado[hombre]:=falso; //desmarcar
fsi
fpara
fproc
[editar] Llamada inicial
La llamada inicial llama al procedimiento de vuelta atrás con los parámetros inicializados de manera adecuada.
proc parejas (H[1..n,1..n], M[1..n,1..n] de nat)
var sol[1..n] de 1..n, asignado[1..n] de bool;
asignado[1..n]:=falso;
parejas-va(H,M,sol,1,asignado);
fproc
[editar] Función Auxiliar
Función de estabilidad que se ha definido anteriormente, necesaria para el algoritmo de vuelta atrás.
fun estable (H[1..n,1..n], M[1..n,1..n] de nat, sol[1..n] de 1..n, k :1..n) dev respuesta : bool
respuesta:=cierto; i:=1;
mientras (i<k AND respuesta) hacer
respuesta:= ( (M[k,sol[i]] <= M[k,sol[k]] OR H[sol[i],k] <= H[sol[i],i]) AND //c1 y c2
( (M[i,sol[k]] <= M[i,sol[i]] OR H[sol[k],i] <= H[sol[k],k]) ) //c3 y c4
i:= i+1;
fmientras
ffun
[editar] Referencias
- Martí Oliet, N.; Ortega Mallén, Y.; Verdejo López, J.A.
ESTRUCTURAS DE DATOS Y MÉTODOS ALGORÍTMICOS. Ejercicios resueltos. Pearson Educación 2004.
