lunes, 27 de noviembre de 2017

Algoritmo de Irving

El llamado The Stable Rommates Problem o 'Problema de las Compañeras de Piso' fue resuelto mediante un algoritmo por Robert W. Irving en 1985. Cada participante ordena a sus posibles compañeras según sus preferencias. Cada chica elige una compañera y ésta acepta o no la oferta. En caso de no aceptar se entiende que rechaza a la chica que le ha hecho la propuesta. En el ejemplo de la tabla el AZUL indica la elegida, el VERDE la que acepta y el ROJO la rechazada.
  • 1ª ETAPA
    • Cada chica propone a su compañera favorita.
    • La elegida acepta, pero si es elegida por más de una, acepta la mejor propuesta y rechaza las demás.
    • Las rechazadas esperan para ser aceptadas más adelante.
    • Si alguna chica es rechazada por todas no existe una solución estable.
Aunque Berta elige a Delia, ella prefiere a Clara y es rechazada. Igualmente, aunque Eva elige a Flor, ella prefiere a Delia y es rechazada.
Ahora Berta propone a Eva que acepta y Eva propone a Clara que acepta.
  • 2ª ETAPA
    • Todas desechan las posibles compañeras que son menos deseadas que la actualmente aceptada.
Ana rechaza a Clara y a Eva, Berta rechaza a Clara, y así sucesivamente.
Así las opciones quedan reducidas a las siguientes:
  • 3ª ETAPA
    • Elige una participante X que tenga al menos dos opciones.
    • Busca su segunda preferencia Y.
    • Sea Z la última preferencia de Y.
    • Repite el proceso hasta que se llegue a X.
    • Elimina las parejas (Y,Z) y sus simétricas.
    • Repite el proceso hasta que todas tengan una única opción.
Los emparejamientos son: Ana y Flor, Berta y Eva, Clara y Delia.
En este caso no hay una solución estable, pues nadie quiere ir con D.