Como ya sabe, utilizamos el " Problema de la secretaria "para elegir el mejor candidato. Ahora me gustaría saber si podemos utilizar esta regla para encontrar también el peor candidato? En caso afirmativo, ¿cómo se consigue?
Respuestas
¿Demasiados anuncios?
Sí.
El algoritmo simplemente encuentra al participante que óptimo según alguna propiedad, pero no le importa cuál sea esa propiedad significa (siempre que defina una relación de ordenación sobre los candidatos). El cambio de esa propiedad de ser bueno a ser malo (o cualquier otra) es sólo una definición sin relevancia algorítmica.
Nameless
Puntos
2331
Creo que quiere saber si se puede utilizar el procedimiento para elegir al peor (en lugar del mejor) candidato. La respuesta es sí.
La situación es la siguiente: usted sabe cuántos candidatos $N$ hay, pero no se conoce la distribución de la calidad de los candidatos. Además, sólo se puede mirar a un candidato a la vez, y no se puede volver a un candidato anterior ("no recall").
Se utiliza el $1/e$ algoritmo: primer vistazo a $1/e$ de la $N$ candidatos, y recuerda la calidad de la peor de esos, que es, digamos, $\underline{q}$ . Después de la $N/e$ candidatos muestreados, se elige el primer candidato que es peor que lo que se ha visto anteriormente, es decir, se elige el candidato $i$ si $q_i\le \underline{q}$ y el candidato $N$ si la calidad de ningún candidato era peor. Este procedimiento maximiza la probabilidad de elegir al peor candidato.
Esto no es más que la inversión de la solución para maximizar la probabilidad de elegir al mejor candidato.
Neil W
Puntos
1728
