• Artículo

Septiembre de 2016

Volumen 31, número 9

Ejecución de pruebas: el Problema de la secretaria

Por James McCaffrey

James McCaffreySuponga que quiere contratar una secretaria. Tiene un grupo de 100 aspirantes y entrevista a una por día. Después de cada entrevista, debe decidir de forma inmediata si contrata a la aspirante actual o no. Si decide no contratar a una aspirante, no podrá hacerlo más tarde. No dispone del tiempo para entrevistar a las 100 candidatas, por tanto, ¿qué algoritmo puede usar para maximizar las opciones de seleccionar a la mejor aspirante?

Lo que acabo de describir es un ejemplo del Problema de la secretaria. Las soluciones al Problema de la secretaria tienen muchos usos importantes. Por ejemplo, en el aprendizaje automático, a menudo es necesario encontrar un método para detener el entrenamiento con el fin de optimizar la probabilidad de seleccionar el mejor modelo de predicción.

El Problema de la secretaria forma parte de una clase más grande de problemas en los que se busca la mejor solución, además de estar incluido en lo que se conocen como problemas de parada óptima. Hasta donde yo sé, la primera vez que se publicó una descripción del Problema de la secretaria (de una forma ligeramente distinta) fue en la revista Scientific American en 1960. Existen docenas de variaciones interesantes del problema.

En este artículo, le mostraré cómo abordar el Problema de la secretaria mediante lo que se conoce como una regla de parada 1/e. Una buena forma de ver el rumbo que tomará este artículo es examinar el programa de demostración que aparece en la Figura 1. Programé la demostración en C#, pero no debería tener problemas para refactorizar el código a otro lenguaje si lo desea.

Ejecución del programa de demostración del Problema de la secretaria
Figura 1. Ejecución del programa de demostración del Problema de la secretaria

En este artículo se presupone que tiene al menos conocimientos intermedios de programación, pero no se presupone que sepa nada sobre el Problema de la secretaria. El código fuente completo del programa de demostración se presenta en este artículo, pero también puede obtener el código fuente en la descarga de código que lo acompaña.

La regla de parada 1/e

Se puede probar de forma matemática que, bajo ciertas condiciones, es posible maximizar de forma teórica la probabilidad de seleccionar a la mejor aspirante en el Problema de la secretaria mediante el uso de lo que se conoce como un algoritmo o una regla 1/e. En el contexto del Problema de la secretaria, el término Candidata se refiere a la mejor aspirante que se ha visto en un momento determinado. Escribo la palabra Candidata en mayúsculas para enfatizar que la palabra tiene un significado distinto al habitual en español, en el que una candidata y una aspirante son prácticamente sinónimos.

En la explicación siguiente, 'N' representa el número total de aspirantes y 'e' representa la constante de Euler, que tiene un valor de aproximadamente 2,71828. Expresada en palabras, la regla 1/e establece que "Se omiten las primeras N / e aspirantes, pero se hace un seguimiento de la mejor Candidata. Entonces se contrata a la primera Candidata que aparece. Si no aparece ninguna nueva Candidata después de que las primeras N / e aspirantes se hayan omitido, no ha funcionado y no se contrata a nadie".

Un ejemplo concreto ayudará a que el algoritmo se entienda mejor. El algoritmo de parada 1/e se ilustra gráficamente en la Figura 2. Suponga que tiene 10 aspirantes. Cada aspirante tiene una puntuación entre 0,0 y 9,0 (aunque no la conocerá hasta que la entreviste), que cuanto mayor sea el valor, mejor. Las puntuaciones de las aspirantes son:

(5.0, 2.0, 7.0, 1.0, 4.0, 0.0, 8.0, 3.0, 9.0, 6.0)
  0    1    2    3    4    5    6    7    8    9

El algoritmo 1/e para el Problema de la secretaria
Figura 2. El algoritmo 1/e para el Problema de la secretaria

La aspirante 0 tiene una puntuación de 5,0 y será la primera que se entreviste; la aspirante 1 tiene una puntuación de 2,0 y será la segunda en entrevistarse; y así sucesivamente. La mejor aspirante es la persona 8 con una puntuación de 9,0.

El número de aspirantes que se omitirá es N / e = 10 / 2,71828 = 3,6788, que es 3 si se trunca, y 4 si se redondea. Se da la circunstancia de que, en los casos en que N no es muy pequeño, no hay gran diferencia entre truncar o redondear. Suponga que lo trunca a 3.

Entrevista a la aspirante 0 y averigua que tiene una puntuación de 5,0; se convierte en la Candidata al tener la mejor puntuación que se ha visto (por el momento, la única que se ha visto). A continuación, entrevista a la aspirante 1 y descubre que tiene una puntuación de 2,0; por este motivo, no se convierte en Candidata, ya que su puntuación no es mejor que 5,0. Entrevista a la aspirante 2 y determina que tiene una puntuación de 7,0; se convierte en la nueva Candidata. En este momento ya ha entrevistado a las primeras N / e = 3 aspirantes, por lo que ahora ya está listo para contratar a la primera nueva Candidata que aparezca.

Entrevista a la aspirante 3 y se encuentra con una puntuación de 1,0; no se convierte en la Candidata. Entrevista a la aspirante 5 y averigua que su puntuación es de 0,0 (¡ups! he trabajado con esta persona), por lo que tampoco es la Candidata. Entrevista a la aspirante 6 y descubre una puntuación de 8,0. Esta es la puntuación más alta de las que se han visto, por lo que se convierte en la Candidata y, dado que ya ha superado las primeras N / e aspirantes, contrata inmediatamente a la aspirante 6.

Observe que el algoritmo 1/e no encontró a la mejor aspirante en este ejemplo, pero encontró a la segunda mejor. Si usa el algoritmo 1/e para el Problema de la secretaria, la probabilidad de que seleccione a la mejor aspirante de N aspirantes es de aproximadamente 1 / e = 1 / 2,71828 = 0,3679.

El programa de demostración

Para crear el programa de demostración, inicié Visual Studio y creé un nuevo programa de aplicación de consola de C# denominado SecretaryProblem. El programa de demostración no tiene ninguna dependencia significativa de .NET, por lo que funcionará con cualquier versión de Visual Studio. Cuando se cargó el código de la plantilla, en la ventana del Explorador de soluciones hice clic con el botón derecho en el archivo Program.cs y cambié su nombre por SecretaryProblemProgram.cs (que es más descriptivo), y Visual Studio cambió el nombre de la clase automáticamente. En la parte superior de la ventana del editor, quité todas las instrucciones using que hacían referencia a espacios de nombres innecesarios y dejé solo la única referencia al espacio de nombres System de nivel superior.

El programa de demostración tiene dos partes. En las primeras líneas del método Main se ilustra el algoritmo 1/e cuando se aplica a un ejemplo del Problema de la secretaria con 10 aspirantes. En la segunda parte de la demostración se ilustra una simulación en la que el algoritmo 1/e se ejecuta 10 000 veces con 100 aspirantes.

Las líneas clave del código de llamada de la primera parte de la demostración son:

double[] ratings =
  new double[] { 5.0, 2.0, 7.0, 1.0, 4.0, 0.0, 8.0, 3.0, 9.0, 6.0 };
Console.WriteLine("Applicant ratings are: \n");
for (int i = 0; i < ratings.Length; ++i)
  Console.Write(ratings[i].ToString("F1") + "  ");
Console.WriteLine("\n");
int selected = Select(ratings, true);  // Verbose

Un problema se configura mediante la definición de aspirantes como una matriz de tipo double, en la que el índice representa el identificador de la aspirante y el valor de la celda representa la puntuación de la aspirante. La versión básica del Problema de la secretaria presupone que todas las puntuaciones de las aspirantes son distintas, por lo que no puede haber empates.

El método Select definido por el programa acepta una matriz de puntuaciones y usa el algoritmo 1/e para encontrar y devolver el índice de la aspirante seleccionada. El método Select tiene una gran cantidad de instrucciones WriteLine que imprimen el progreso, como se muestra en la Figura 1.

Las líneas clave del código de llamada (con pequeñas modificaciones para una mejor legibilidad) de la segunda parte de la demostración son:

int numHiringSessions = 10000;
int numApplicants = 100;
double pBest = Simulation(numApplicants, numHiringSessions);
Console.WriteLine("Simulation prob of best applicant  = " +
  pBest.ToString("F4"));
double pTheory = 1 / Math.E;
Console.WriteLine("Theoretical prob of best applicant = " +
  pTheory.ToString("F4"));

El método Simulation definido por el programa acepta un número fijo de aspirantes. Un diseño alternativo sería permitir que la simulación seleccione de forma aleatoria el número de aspirantes de cada prueba. De forma interna, el método Simulation se ejecuta en bucle y llama a una versión en modo no detallado del método Select, a la vez que realiza un seguimiento del número de veces que se seleccionó la mejor aspirante.

El método Select

La definición del método Select comienza así:

static int Select(double[] ratings)
{
  int numApplicants = ratings.Length;
  int numSkip = (int)(numApplicants / Math.E);
  int candidate = 0;  // Best applicant seen
  double bestRating = ratings[0];
  double rating = 0.0;
  bool readyToHire = false;
...

El número de aspirantes viene determinado por el número de celdas de la matriz de puntuaciones. Podría conseguir que fuera explícito si pasase un parámetro adicional N a Select. La variable numSkip es el número de aspirantes iniciales que se omitirán mientras se realiza el seguimiento de la mejor aspirante hasta el momento. Si quisiera redondear en lugar de truncar, podría escribir:

int numSkip = (int)Math.Round(numApplicants / Math.E);

La variable candidate es la mejor aspirante que se haya visto en cualquier momento del proceso de contratación y la variable bestRating es la puntuación asociada a la Candidata. Las dos variables se inicializan con los valores de la primera aspirante, en lugar de usar valores ficticios como -1 y -1,0 (respectivamente).

La variable rating representa la puntuación de la aspirante actual y solo existe por motivos de legibilidad. La variable booleana readyToHire tiene un valor false cuando se procesan las primeras numSkip-1 aspirantes, para cambiar después a un valor true.

El cuerpo del método Select es corto y relativamente simple:

...
  for (int applicant = 0; applicant < numApplicants; ++applicant) {
    rating = ratings[applicant];
    if (applicant >= numSkip) readyToHire = true;
    if (rating > bestRating) {
      candidate = applicant;
      bestRating = rating;
      if (readyToHire == true) return candidate;
    }
  }
  return -1;
}

El método recorre cada una de las aspirantes de la matriz de puntuaciones. Por cada aspirante, la aspirante actual se convierte en la Candidata si la puntuación de la aspirante actual es superior que la mejor (la mayor) puntuación que se haya visto. Cuando la variable booleana readyToHire tiene un valor false, se identifican Candidatas, pero no se devuelven. Cuando el valor de readyToHire es true, se devuelve la primera Candidata disponible que se encuentre, lo que en el Problema de la secretaria se corresponde con una contratación inmediata.

Un diseño alternativo sería utilizar dos bucles en lugar un único bucle de procesamiento, con un primer bucle que itere por las aspirantes que se omiten y un segundo que identifique la primera Candidata disponible:

// 1. prelim loop
for (int applicant = 0; applicant < numSkip; ++applicant)
{
  // Track best rating seen
}
// 2. hiring loop
for (int applicant = numSkip; applicant < numApplicants; ++applicant)
{
  // Return first Candidate found
}

Es posible que no aparezca una nueva Candidata después de las primeras numSkip aspirantes. Por ejemplo, suponga que tiene ocho aspirantes con las puntuaciones (7,0; 6,0; 5,0; 4,0; 3,0; 2,0; 1,0; 0,0). La variable numSkip se establecería a 8 / 2,71828 = 2. Después de entrevistar a las dos primeras aspirantes, la mejor puntuación sería 7,0 y ninguna de las seis aspirantes restantes se identificarían como Candidata. El método Select devuelve un valor ficticio de -1 cuando no se encuentra ninguna Candidata.

El método Simulation

En pseudocódigo de alto nivel, el método Simulation es:

generate applicants / ratings
determine optimal rating
set number_times_best_applicant_selected = 0
loop numTrials times
  randomize order of applicants
  select an applicant using 1/e algorithm
  if selected applicant is optimal
    ++number_times_best_applicant_selected
  end-if
end-loop
return number_times_best_applicant_selected / numTrials

La definición del método Simulate comienza de la siguiente manera:

static double Simulation(int numApplicants, int numTrials)
{
  double[] ratings = new double[numApplicants];
  for (int i = 0; i < numApplicants; ++i)
    ratings[i] = (i * 1.0);
  double optimalRating = 1.0 * (numApplicants - 1);
  int numBestSelected = 0;
...

Como se describió anteriormente, las aspirantes y sus puntuaciones se almacenan en una matriz en la que el índice de la matriz es el identificador de la aspirante y el valor de la celda es la puntuación. El valor de la celda 0 se establece a 0,0; el valor de la celda 1 se establece a 1,0; y así sucesivamente. Por ejemplo, si existen N = 100 aspirantes, los identificadores de las aspirantes irán del 0 al 99 y la puntuación óptima será 99,0.

El bucle de procesamiento del método Simulation es:

for (int trial = 0; trial < numTrials; ++trial) {
  Shuffle(ratings);
  int selected = Select(ratings);
  if (selected == -1)  // failed to select an applicant
    continue;
  double rating = ratings[selected];
  if (rating == optimalRating)
    ++numBestSelected;
}

Un método definido por el programa denominado Shuffle reordena las puntuaciones existentes mediante el minialgoritmo Fisher-Yates:

static void Shuffle(double[] ratings)
{
  for (int i = 0; i < ratings.Length; ++i)
  {
    int ri = rnd.Next(i, ratings.Length);  // random index in [i, N)
    double tmp = ratings[i];
    ratings[i] = ratings[ri];
    ratings[ri] = tmp;
  }
}

El algoritmo Fisher-Yates se suele usar en programas de simulación y aprendizaje automático para reordenar de forma aleatoria los valores de una colección lineal. Muchos lenguajes de programación, entre los que se incluyen Python y R, incluyen un método de reordenación aleatoria como parte de su biblioteca de funciones estándares. Aquí, el método Shuffle definido por el programa presupone la existencia de un objeto Random de ámbito de clase:

class SecretaryProblemProgram
{
  static Random rnd = new Random(0);
  static void Main(string[] args)
  {
...

Después de aplicar aleatoriedad en las puntuaciones, el bucle de procesamiento del método Simulation llama al método Select para elegir una aspirante mediante el algoritmo 1/e; después se comprueba la aspirante seleccionada para ver si se trata de la aspirante óptima.

Cuando se comprueba si es la candidata óptima, se comparan dos valores de punto flotante en busca de una igualdad absoluta:

if (rating == optimalRating)
  ++numBestSelected;

Este enfoque suele ser una mala idea, ya que algunos valores de punto flotante solo se almacenan como aproximaciones, hasta un número determinado de cifras decimales. El enfoque "comparar en busca de una igualdad absoluta" es aceptable en este ejemplo concreto, pero en general querrá comparar en busca de una aproximación muy cercana en lugar de una igualdad absoluta.

Resumen

La información que se incluye en este artículo se basa principalmente en el artículo de investigación de 2003 "Analysis of Heuristic Solutions to the Best Choice Problem", escrito por W. Stein, D. Seale y A. Rapoport. Puede encontrar este artículo en formato PDF en varias ubicaciones de Internet. El artículo presenta un análisis matemático de la regla 1/e y dos reglas adicionales.

La regla del "recuento de candidatos" selecciona arbitrariamente la Candidata n-ésima. Por ejemplo, si n = 3, se seleccionará la tercera Candidata que se encuentre. En el ejemplo que se presenta al principio de este artículo, en el que las aspirantes y sus puntuaciones son (5,0; 2,0; 7,0; 1,0; 4,0; 0,0; 8,0; 3,0; 9,0; 6,0), la tercera Candidata es la aspirante 6 con una puntuación de 8,0, que casualmente es la misma que con la regla 1/e. Parece que la regla del recuento de candidatos no es muy eficaz.

La regla del "no candidato sucesivo" selecciona la primera Candidata vista después de observar a k no Candidatas. Por ejemplo, suponga que k = 3. Para las puntuaciones y aspirantes de ejemplo, las primeras k no Candidatas tienen unas puntuaciones de 2,0; 1,0; y 4,0. La siguiente Candidata es la aspirante 6 con una puntuación de 8,0, que de nuevo es, casualmente, la misma que con la regla 1/e. La regla del no candidato sucesivo parece funcionar bastante bien.

Una vez se familiarice con la estructura general del Problema de la secretaria, encontrará numerosos escenarios en los que los principios clave sean apropiados. Cuando se encuentre frente a una tarea de programación en la que esté involucrado un punto de parada incierto, las ideas del Problema de la secretaria podrían resultarle útiles.

El Dr. James McCaffrey trabaja para Microsoft Research en Redmond, Washington. Ha colaborado en el desarrollo de varios productos de Microsoft como, por ejemplo, Internet Explorer y Bing. Puede ponerse en contacto con James en jammc@microsoft.com.

Gracias a los siguientes expertos técnicos de Microsoft por revisar este artículo: Chris Lee y Kirk Olynyk