• Artigo

Setembro de 2016

Volume 31 – Número 9

Execução de Teste – O Problema da Secretária

Por James McCaffrey

James McCaffreySuponha que você queira contratar uma secretária. Você possui um pool de 100 candidatas e você entrevista uma candidata por dia. Após cada entrevista, você deve decidir imediatamente se contrata ou não a candidata em questão. Se não contratar uma candidata, você já não poderá entrar em contato com a mesma. Você não tem tempo para entrevistar todas as 100 candidatas, então qual algoritmo pode ser usado para maximizar a sua chance de selecionar a melhor candidata?

O que eu descrevi é um exemplo do Problema da Secretária. As soluções para o Problema da Secretária possuem muitos usos importantes. Por exemplo, no aprendizado de máquina, muitas vezes é necessário criar uma abordagem para interromper o treinamento de forma a otimizar a probabilidade de selecionar o melhor modelo de previsão.

O Problema da Secretária faz parte de uma classe maior de problemas também chamados de problemas da melhor opção e que também fazem parte do que chamamos problemas de interrupção ideal. Até onde sei, uma descrição do Problema da Secretária (de uma forma ligeiramente diferente) foi primeiramente publicada na Scientific American em 1960. Existem dezenas de variações interessantes desse problema.

Neste artigo mostrarei como resolver o Problema da Secretária usando a chamada regra de interrupção 1/e. Uma boa maneira de saber o rumo que este artigo tomará é examinar o programa de demonstração na Figura 1. Codifiquei a demonstração usando C#, mas você não deve ter problemas ao refatorar o código para outra linguagem, se desejar.

Execução do Programa de Demonstração do Problema da Secretária
Figura 1 Execução do Programa de Demonstração do Problema da Secretária

Este artigo pressupõe que você tenha habilidades de programação que sejam, pelo menos, intermediárias, mesmo que não tenha familiaridade alguma com o Problema da Secretária. O código-fonte completo do programa de demonstração é apresentado neste artigo e você também pode obtê-lo baixando o código em anexo.

A Regra de Interrupção 1/e

É possível provar matematicamente que, sob determinadas circunstâncias, você pode teoricamente maximizar a probabilidade de selecionar a melhor candidata no Problema da Secretária usando a chamada regra ou algoritmo 1/e. No contexto do Problema da Secretária, o termo Candidata representa a melhor candidata vista até um determinado momento. Estou escrevendo a palavra Candidata com letra maiúscula para enfatizar que a palavra possui um significado diferente do que o da palavra candidata com letra minúscula.

Na explicação a seguir, N representa o número total de candidatas e a letra e representa a constante de Euler que é aproximadamente 2,71828. Colocando em palavras, a regra 1/e é, “Ignore as primeiras N / e candidatas, mas acompanhe a melhor Candidata. Depois, contrate a primeira Candidata que aparecer. Se nenhuma nova Candidata aparecer após as primeiras N / e candidatas terem sido ignoradas, então não contrate ninguém.”

Um exemplo concreto deve tornar esse algoritmo claro. O algoritmo de interrupção 1/e está ilustrado graficamente na Figura 2. Suponha que você possua 10 candidatas. Cada candidata possui (que são desconhecidas para você até o momento da entrevista) uma classificação entre 0,0 e 9,0 onde os valores mais altos são melhores. As classificações das candidatas são:

(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

O algoritmo 1/e para o Problema da Secretária
Figura 2 O algoritmo 1/e para o Problema da Secretária

A candidata 0 possui uma classificação de 5,0 e será entrevistada primeiro. A candidata 1 possui uma classificação de 2,0 e será entrevistada em segundo lugar e assim por diante. A melhor candidata é a pessoa 8 com uma classificação de 9,0.

O número de candidatas a serem ignoradas é N / e = 10 / 2,71828 = 3,6788, que é 3 se for feito um truncamento e 4 se for feito um arredondamento. No final, se N não for muito pequeno faz muito pouca diferença se você trunca ou arredonda. Suponha que você faça o truncamento para 3.

Você entrevista a candidata 0 e descobre que ela tem uma classificação de 5,0, então ela torna-se a Candidata pois a mesma tem a melhor classificação (até esse ponto, a única classificação vista). A seguir, você entrevista a candidata 1 e descobre que ela possui uma classificação de 2,0, então a mesma não será a Candidata pois sua classificação não é melhor do que 5,0. Você entrevista a candidata 2 e descobre uma classificação de 7,0 e a mesma torna-se a nova Candidata. Nesse ponto você entrevistou as primeiras N / e = 3 candidatas, então agora você está pronto para contratar as primeira nova Candidata que aparecer.

Você entrevista a candidata 3 e descobre uma classificação de 1,0, então a mesma não se torna a Candidata. Você entrevista a candidata 5 e descobre uma classificação de 0,0 (Ai! Eu trabalhei com essa pessoa), então ela também não é a Candidata. Você entrevista a Candidata 6 e descobre uma classificação de 8,0. Essa é a classificação mais alta, então ela torna-se a Candidata e como você já passou as primeiras N / e candidatas, você contrata imediatamente a candidata 6.

Observe que o algoritmo 1/e não encontrou a melhor candidata nesse exemplo, mas encontrou a segunda melhor candidata. Se você usou o algoritmo 1/e para o Problema da Secretária, a probabilidade de você selecionar a melhor candidata entre N candidatas é de aproximadamente 1 / e = 1 / 2.71828 = 0.3679.

O programa de demonstração

Para criar o programa de demonstração, iniciei o Visual Studio e criei um novo programa de aplicativo no console C# denominado SecretaryProblem. O programa de demonstração não tem dependências significativas do .NET, portanto, funcionará em qualquer versão do Visual Studio. Após o carregamento do código de modelo, na janela Gerenciador de Soluções, cliquei com o botão direito no arquivo Program.cs e renomeei-o para um mais descritivo, o SecretaryProblemProgram.cs e o Visual Studio renomeou a classe Program para mim automaticamente. Na parte superior da janela do Editor, removi todas as instruções que faziam referência a namespaces desnecessários, deixando somente uma referência ao namespace System de nível superior.

O programa de demonstração possui duas partes. As primeiras poucas linhas no método Main ilustram o algoritmo 1/e aplicado a um exemplo específico do Problema da Secretária com 10 candidatas. A segunda parte da demonstração ilustra uma simulação onde o algoritmo 1/e é executado 10.000 vezes com 100 candidatas.

As linhas principais do código de chamada para a primeira parte da demonstração são:

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

Um problema é configurado definindo as candidatas como uma matriz do tipo double onde o índice representa a ID de uma candidata e o valor da célula representa a classificação de uma candidata. A versão básica do Problema da Secretária considera que as classificações das candidatas são diferentes, então não pode haver empates.

O método Select definido pelo programa aceita uma matriz de classificações e usa o algoritmo 1/e para encontrar e retornar o índice da candidata selecionada. O método Select possui várias declarações WriteLine que imprimem o progresso, conforme mostrado na Figura 1.

As principais linhas do código de chamada (com o mínimo de edição para legibilidade) da segunda parte da demonstração são:

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"));

O método Simulation definido pelo programa aceita um número fixo de candidatas. Um design alternativo é permitir que a simulação escolha aleatoriamente o número de candidatas em cada avaliação. Nos bastidores, o método Simulation fica em loop, chamando uma versão não detalhada do método Select enquanto controla o número de vezes que a melhor candidata foi selecionada.

O Método Select

A definição do método Select começa da seguinte maneira:

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;
...

O número de candidatas é determinado pelo número de células na matriz de classificações. Você pode tornar isso explícito passando um parâmetro adicional N para o método Select. A variável numSkip é o número inicial de candidatas a ser ignorado enquanto a melhor candidata é acompanhada. Se quiser arredondar em vez de truncar, você pode escrever:

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

A variável candidate é a melhor candidata vista até aquele momento durante o processo de contratação e a variável bestRating é a classificação associada à Candidata. As duas variáveis são inicializadas para os valores da primeira candidata em vez de usar valores dummy como -1 e -1,0, respectivamente.

A variável rating representa a classificação da candidata atual e existe somente para legibilidade. A variável booliana readyToHire é false ao processar as primeiras numSkip-1 candidatas e, em seguida, é definida como true.

O corpo do método Select é curto e relativamente simples:

...
  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;
}

O método percorre cada candidata na matriz de classificações. Para cada candidata, a candidata atual torna-se a Candidata se a classificação da candidata atual for maior do que a melhor classificação (mais alta) vista. Quando a variável booliana readyToHire for false, as Candidatas são identificadas, mas não são retornadas. Quando readyToHire é true, a primeira Candidata disponível encontrada é retornada, o que corresponde a uma contratação imediata no Problema da Secretária.

Um design alternativo é usar dois loops em vez de um único loop de processamento, onde o primeiro loop itera sobre as candidatas a serem ignoradas e o segundo loop identifica a primeira Candidata disponível:

// 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
}

É possível que nenhuma Candidata apareça após as primeiras numSkip candidatas. Por exemplo, suponha que você possua oito candidatas com classificações (7,0, 6,0, 5,0, 4,0, 3,0, 2,0 1,0, 0,0). A variável numSkip seria definida como 8 / 2,71828 = 2. Após as duas primeiras candidatas terem sido entrevistadas, a melhor classificação seria 7,0 e nenhuma das seis candidatas restantes seria identificada como uma Candidata. O método Select retorna um valor dummy de -1 quando nenhuma Candidata é encontrada.

O Método Simulation

Em um pseudo-código de alto nível o método Simulation é:

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

A definição do método Simulate começa da seguinte forma:

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;
...

Conforme descrito anteriormente, as candidatas e suas classificações são armazenadas em uma matriz onde o índice da matriz é a ID da candidata e o valor da célula é a classificação. O valor na célula 0 é definido como 0,0, o valor na célula 1 é definido como 1,0 e assim por diante. Por exemplo, se houver N = 100 candidatas, as IDs das candidatas irão de 0 até 99 e a classificação ideal é de 99,0.

O loop de processamento principal no método Simulation é:

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;
}

Um método definido pelo programa chamado Shuffle reorganiza as classificações usando o mini-algoritmo de 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;
  }
}

O algoritmo de Fisher-Yates é frequentemente usado em programas de simulação e aprendizado de máquina para embaralhar os valores em uma coleção linear. Muitas linguagens de programação como Python e R, por exemplo, incluem um método de embaralhamento interno como parte das suas respectivas bibliotecas de função padrão. Aqui, o método Shuffle definido pelo programa considera a existência de um objeto Random do escopo da classe:

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

Após as classificações serem embaralhadas de forma aleatória, o loop de processamento no método Simulation chama o método Select para escolher uma candidata usando o algoritmo 1/e, em seguida, a candidata selecionada é verificada para confirmar se ela é a candidata ideal.

Ao verificar a candidata ideal, dois valores de ponto flutuantes são comparados para verificar a igualdade exata dos mesmos:

if (rating == optimalRating)
  ++numBestSelected;

Essa abordagem geralmente é uma má ideia pois alguns valores de ponto flutuante são armazenados somente como aproximações, com um número fixo de casas decimais. A abordagem de comparar para saber se a igualdade é exata funciona neste exemplo específico, mas, em geral, é melhor comparar a proximidade e não a igualdade dos valores.

Conclusão

As informações apresentadas neste artigo são baseadas principalmente na pesquisa de 2003, “Analysis of Heuristic Solutions to the Best Choice Problem,” de W. Stein, D. Seale e A. Rapoport. Você pode encontrar essa pesquisa no formato PDF em vários sites na Internet. Esse documento apresenta uma análise matemática da regra 1/e além de duas regras adicionais.

A regra “contagem de candidatas” seleciona aleatoriamente a enésima Candidata. Por exemplo, se n = 3, a terceira Candidata encontrada será selecionada. No exemplo apresentado no início deste artigo, onde as candidatas e as classificações são (5,0, 2,0, 7,0, 1,0, 4,0, 0,0, 8,0, 3,0, 9,0, 6,0), a terceira Candidata é a candidata 6 com uma classificação de 8,0, que coincidentemente é a mesma da regra 1/e. No final das contas, a regra da contagem de candidatas não é muito eficaz.

A regra “candidatas não sucessivas” seleciona a primeira Candidata vista após observar k não Candidatas. Por exemplo, suponha que k = 3. Para as candidatas e classificações do exemplo, as primeiras k não Candidatas possuem as classificações 2,0, 1,0 e 4,0. A Candidata seguinte é a candidata 6 com uma classificação de 8,0, o que novamente é, coincidentemente, a mesma da regra 1/e. A regra de candidatas não sucessivas mostrou que funciona muito bem.

Depois de familiarizar-se com a estrutura geral do Problema da Secretária, você encontrará um número razoável de cenários onde os principais princípios serão relevantes. Sempre que você se deparar com uma tarefa de programação que envola um ponto de interrupção incerto, as ideias do Problema da Secretária podem ser úteis.

Dr. James McCaffreytrabalha para a Microsoft Research em Redmond, Washington. Ele trabalhou em vários produtos da Microsoft, incluindo Internet Explorer e Bing. Entre em contato com o Dr. McCaffrey pelo email jammc@microsoft.com.

Agradecemos aos seguintes especialistas técnicos da Microsoft pela revisão deste artigo: Chris Lee e Kirk Olynyk