Uno de los ejemplos clásicos es el algoritmo de matrimonio estable de Gale y Shapley. El problema del matrimonio estable es el siguiente. Supongamos que hay n hombres yn mujeres. Cada hombre tiene una lista de mujeres con las que le gustaría casarse clasificadas en orden decreciente de preferencia. Del mismo modo para cada mujer. Se dice que los matrimonios son estables si no hay dos personas del sexo opuesto que prefieran tener una pareja como pareja actual.
El problema parece simple. Pero solo para dar una idea de cuán profunda es la solución, Shapley recibió el premio Nobel de economía por su trabajo.
Entonces, ¿qué tan profundo es esto? Se usa en todas partes. Se utiliza para encontrar coincidencias entre estudiantes de medicina y hospitales. Se utiliza en asignaciones estables en el mercado. Las ideas incluso se utilizan para desarrollar buenos algoritmos para el enrutamiento en redes.
- ¿Se puede resolver Codeforces 431C - k-tree por recusión?
- ¿Cómo elige Chrome el color de las rayas en las miniaturas de la página "Más visitadas"? Está claramente basado en el favicon, pero no puedo decir exactamente cómo se deriva.
- ¿Cómo podemos encontrar la aparición de una cadena dada (la secuencia no importa) en una secuencia dada en Java?
- ¿Cuál es el mejor libro sobre estructuras de datos y algoritmos en Java?
- ¿Por qué los algoritmos no hacen las preguntas sobre Quora?
