Algoritmo para problema de “Casamiento Estable”

Aunque el problema es conocido como “casamiento estable” (y se soluciona pensando en esta idea), su utilidad es muy amplia y se puede aplicar a una basta gama de problemas actuales. Este problema fue estudiado por primera vez hace ya unos 50 años por Gale y Shapley, con el fin de seleccionar de la manera más óptima y justa a candidatos que postulan a las diferentes universidades. Parece bastante simple la idea, pero veamos un ejemplo que más o menos ilustra las complicaciones del problema: Supongamos que existen n empresas y n candidatos para trabajar (si, nadie quedará sin empleo esta vez), cada empresa necesita tan sólo 1 empleado y vamos a suponer que todos los candidatos postulan a todas las empresas. Seguir leyendo…

Anuncios