Más que ser “simples ejercicios para desarrollar habilidades técnicas en el campo de la programación”, los algoritmos nos permiten resolver problemas de razonamiento complejo mediante una serie de pasos o premisas que ya han sido analizados y probados y los cuales se sintetizan en una lógica relativamente simple que pueda ser reproducida de manera sistemática y garantice resultados similares en todos los casos.
Si aún no has visto el Curso de Algoritmos y Estructuras de Datos, te invito a verlo cuanto antes ya que este interesante, completo y ameno curso complementará tu formación y te dará las bases necesarias, para ser un desarrollador integral, y no sólo un coder de algún lenguaje particular, ya que los conceptos, fundamentos y técnicas que aprenderás, aplican a todos los lenguajes de programción modernos e incluso los que salgan en el futuro!
Los Matrimonios Estables
El problema de los “Matrimonios Estables” plantea una situación particular en la que cada uno de los hombres de un conjunto se debe emparejar con las mujeres de otro conjunto de igual número,para lo cual se deben tomar en cuenta las preferencias entre ambos.
En otras palabras:
Todas las parejas formadas por los hombres y mujeres de dos grupos deberán quedar al final con un hombre y una mujer cuya preferencia del uno por el otro es la mejor, considerando las opciones que cada uno tuvo al escoger.
El problema es que: si por el contrario quedasen emparejados un hombre y una mujer que prefieren a los miembros de otra pareja que recíprocamente los prefieren también más que a las parejas con las que quedaron, entonces se da una condición de inestabilidad que invalida el algoritmo utilizado.
La Teoría
Para desarrollar el algoritmo y código de este ejercicio en Lenguaje C++ (con DevC win) en una asignatura de postgrado que cursé hace unos años, hice una breve investigación en internet sobre las diferentes propuestas de solución utilizando algoritmos de backtracking (1) y algunos otros algoritmos formales como el de Poisson-Lebesgue (2) o el de Gale-Shapley (3), y en esta búsqueda llegué a un video en youtube en el que una participante de post-doctorado de la universidad de Hardvard, Emily Riehl, hace una explicación magistral de cómo funciona el algoritmo mediante un proceso de postulación y selección iterativos.
El video de Emily Riehl
Enlace a youtube: https://youtu.be/w1leqkpDaRw
Si prefieres, adelanta el video hasta el min 08:25s para ver un ejemplo práctico de la aplicación del algoritmo
El Algoritmo / La Solución
El algoritmo que desarrolla la profesora Emily Riehl y que fue propuesto originalmente en 1962 por los científicos Gale y Shapely (4), describe lo siguiente:
- Antes de iniciar, cada hombre debe calificar a cada una de las mujeres en función de su preferencia, colocando en una lista primero la que prefiere más como esposa y así hasta la que prefiere menos.
- Luego se inicia el ciclo de proposiciones.
- En la mañana del primer día, cada hombre le hace la proposición a la primera mujer en su lista, es decir; a quién prefiere más de entre todas.
- Cada mujer recibe la proposición de matrimonio perono da su respuesta sino hasta el final del día, debido a que esperará a ver si algún otro hombre desea proponerle también matrimonio.
- Al finalizar el día cada mujer evalúa las proposiciones que ha recibido, y si más de un hombre le propuso matrimonio, entonces aceptará al que esté mejor calificado en su propia lista de preferencias, y rechazará al que prefiera menos en su lista, excepto si sólo recibió una proposición.
- Así pues al menos una pareja se habrá formado inicialmente, pero los hombres que hayan sido rechazados habrán quedado sin pareja, y por otra parte, habrá alguna mujer que no haya recibido ninguna proposición.
- Las mujeres que recibieron sólo una propuesta, al final del día la aceptarán.
- Mientras aún queden hombres y mujeres sin emparejarse, continuará este mismo proceso de proposiciones por parte de los hombres aún solteros, con cada una de las mujeres que siguen en su lista de preferencias.
El algoritmo garantiza que si se sigue el proceso descrito, al momento en que ya ningún hombre se encuentre soltero, se habrán formado ya todas las mejores parejas posibles en función de sus preferencias, dándose así los matrimonios estables.
Esto puede verificarse, evaluando las preferencias de cada uno de los miembros en todas las parejas y confirmando que no hayan quedado emparejados un hombre y una mujer que prefieren a los miembros de otra pareja que recíprocamente los prefieren también más a ellos que a las parejas con las que quedaron.
Profundizando un poco más en las referencia teóricas de este algoritmo, encontré que la situación de “estabilidad” o equilibrio al que se llega al finalizar el proceso, es también conocido como Equilibro de Nash (1951) (5) en la teoría de juegos, es un tema interesantísimo, pero ya quedará para otro post 😃 …
Finalmente
El algoritmo de los Matrimonios Estables no solamente sirve para encontrar una pareja estable -para lo cual ya vimos que funciona a la perfección–, sino que además tiene infinifad de aplicaciones en situaciones que no están precisamente relacionadas con las relaciones sentimentales; aún cuando sí lo están con la decisión de escoger la mejor opción disponible en base a ciertas preferencias.
Así pues, ya sea elegir a los candidatos más aptos para el ingreso a una universidad o saber cuál es el país que más te conviene a lo hora de decidir emigrar buscando nuevos horizontes, si decides usar este increíble algoritmo, podrás estar seguro de haber tomado la mejor decisión posible wn base a tus opciones, y que a fín de cuentas este emparejamiento tenga mayores probabilidades de ser perdurable, en tanto las preferencias no cambien con el tiempo, claro.
Fuente original: Enlace a documento en Google Drive
Si te gustó este post o te ha parecido útil, recuerda darle clic a la manito en el título. bai! 🤓🤘
Referencias:
Referencias:
(1) Algoritmia/Vuelta atrás - Wikilibros
(2) Algoritmo del matrimonio estable de Poisson y Lebesgue
(3) Algoritmo de Gale-Shapley
(4) Bio: David Gale - Bio: Lloyd Shapley
(5) El Equilibrio de Nash - Economioedia.com
Lectura recomendada:
El problema de los Matrimonios Estables y otros problemas de emparejamiento
Me parece un buen algoritmo para emparejar no solo personas, sino cualquier cosa que necesitemos