Implementación de G-S

Implementación de G-S

de Diego Furrer Dellepiane -
Número de respuestas: 2

Buenas! Espero se encuentren bien.

Leyendo el capítulo de "Implementing the Stable Matching Algorithm" (pag. 45) me generó una duda. 

Entiendo que como tenemos hasta n^2 iteraciones del while necesitamos que cada iteración sea en tiempo constante para poder decir que nuestra implementación del algoritmo es O(n^2), pero, cuando especifica que pasos deben ser O(1) el primero dice:

1. Debemos poder identificar a un hombre libre

Pero nunca menciona la parte de verificar que no se haya propuesto a todas las mujeres. 

Tengo entendido que la parte de que no se haya propuesto a todas las mujeres se agrega para poder probar la terminación del algoritmo de forma simple y que la demostración de que "existe un hombre libre" implica que existe una mujer a la que no se propuso es sencilla. Simplemente utilizando el hecho de que si una mujer termina el algoritmo libre significa que ningun hombre le propuso y si un hombre termina el algoritmo libre entonces una mujer termina el algoritmo libre, llegando a la contradicción de que el hombre libre no le propuso a esa mujer libre.

Pero, se puede ignorar esa parte sin hacer ninguna demostración? Podemos asumir que G-S no incluye la parte de "que no se haya propuesto a todas las mujeres"?

Muchas gracias!

Saludos,

Diego Furrer



En respuesta a Diego Furrer Dellepiane

Re: Implementación de G-S

de Fernando Fernandez -
Hola Diego.

Lo que planteas, si lo entendí bien, creo que es correcto. Pero me parece que está demostrado en (1.4), que abreviado puede ser: "Si m está libre, entonces hay alguna w a la que no se propuso".
Entonces, no hace falta verificar si hizo todas las propuestas; se sabe, está demostrado, que no lo hizo.

¿Esto explica la duda?

Saludos,
Fernando