Problema de la secretaria (un problema de parada óptimo)

Posted on by Rudeus Greyrat

El problema de la secretaria, también conocido como problema del matrimonio, el problema de la dote del sultán , y el problema de la mejor elección es un ejemplo del problema de parada óptima .

Este problema se puede plantear de la siguiente forma: imagine un administrador que quiere contratar a la mejor secretaria de entre n candidatos clasificados para un puesto. Los solicitantes son entrevistados uno por uno en orden aleatorio. Se tomará una decisión sobre cada solicitante en particular inmediatamente después de la entrevista. Una vez rechazado, un solicitante no puede ser retirado. Durante la entrevista, el administrador puede clasificar al solicitante entre todos los entrevistados hasta el momento, pero desconoce la calidad de los solicitantes aún no vistos. La pregunta es sobre la estrategia óptima (regla de parada) para maximizar la probabilidad de seleccionar al mejor candidato.

Detención óptima : en matemáticas, la teoría de la detención óptima o la detención temprana se ocupa del problema de elegir un momento para realizar una acción en particular, con el fin de maximizar una recompensa esperada o minimizar un costo esperado.

Si la decisión de contratar a un candidato se tomaría al final de entrevistar a todos los n candidatos, una solución simple es usar el algoritmo de selección máxima para rastrear el máximo actual (y quién lo logró) y seleccionar el máximo general al final. La parte difícil de este problema es que la decisión debe tomarse inmediatamente después de entrevistar a un candidato.

Ley 1/e de la estrategia óptima
De acuerdo con esta estrategia, la probabilidad óptima de ganar siempre es al menos 1/e.
La regla de detención óptima prescribe siempre rechazar los primeros n/e solicitantes que son entrevistados (donde e es la base del logaritmo natural y tiene el valor 2.71828 ) y luego detenerse en el primer solicitante que es mejor que todos los solicitantes entrevistados hasta el momento (o continuando hasta el último solicitante si esto nunca ocurre). Esta estrategia se denomina regla de parada 1/e porque la probabilidad de seleccionar al mejor candidato es 1/e , en otras palabras, esta estrategia selecciona al mejor candidato alrededor del 37% de las veces.

Si piensa detenidamente, puede parecer obvio que uno no puede seleccionar al primer candidato porque el primer candidato no tiene con quién compararse. Una mejor estrategia es elegir algunos candidatos como muestra para establecer el punto de referencia para los candidatos restantes. Por lo tanto, la muestra será rechazada y solo se utilizará para establecer un punto de referencia.

  • Si una muestra es demasiado pequeña, no obtenemos suficiente información para establecer el punto de referencia para los candidatos restantes.

  • Si una muestra es demasiado grande, obtenemos mucha información, pero también hemos quemado demasiados candidatos potenciales. Esto nos deja con muy pocos candidatos para elegir y, por lo tanto, hace que la estrategia sea pobre.

  • La mejor estrategia es elegir el tamaño de muestra perfecto u óptimo (tamaño de muestra ideal), lo que se puede hacer usando la ley 1/e que rechaza n/e candidatos (este n/e es el tamaño de muestra).

    • El tamaño de muestra óptimo y la probabilidad de éxito para diferentes valores de n son :
    Tamaño de muestra óptimo k = n / e
    La probabilidad de éxito viene dada por :

    donde x = k / n

    La probabilidad de seleccionar al mejor candidato en el problema clásico de la secretaria converge hacia 1/e = 0.368 (aprox.)

    Programa para probar el problema del secretario:
    Nota* : La estrategia óptima no siempre encuentra al mejor candidato, sino que selecciona a los casi mejores candidatos la mayoría de las veces.

    C++

    // C++ Program to test 1/e law for Secretary Problem :
    #include <iostream>
    #include <time.h>
    #define e 2.71828
    using namespace std;
      
    // To find closest integer of num.
    int roundNo(float num)
    {
        return num < 0 ? num - 0.5 : num + 0.5;
    }
      
    // Finds best candidate using n/e rule. candidate[]
    // represents talents of n candidates.
    void printBestCandidate(int candidate[], int n)
    {
        // Calculating sample size for benchmarking.
        int sample_size = roundNo(n/e);
        cout << "\n\nSample size is " << sample_size << endl;
      
        // Finding best candidate in sample size
        int best = 0; 
        for (int i = 1; i < sample_size; i++)
            if (candidate[i] > candidate[best])
                best = i;
      
        // Finding the first best candidate that is  
        // better than benchmark set.
        for (int i = sample_size; i < n; i++)
            if (candidate[i] >= candidate[best]) {
                best = i;
                break;
            }
      
        if (best >= sample_size)
            cout << endl << "Best candidate found is "
                << best + 1 << " with talent " 
                << candidate[best] << endl;
        else
            cout << "Couldn't find a best candidate\n";
    }
      
    int main()
    {
        int n = 8;
      
        // n = 8 candidates and candidate array contains
        // talents of n candidate where the largest 
        // number means highest talented candidate.
        int candidate[n];
      
        // generating random numbers between 1 to 8 
        // for talent of candidate
        srand(time(0));    
        for (int i = 0; i < n; i++)
            candidate[i] = 1 + rand() % 8;
      
        cout << "Candidate : ";
        for (int i = 0; i < n; i++)
            cout << i + 1 << " ";
        cout << endl;
        cout << "  Talents : ";
        for (int i = 0; i < n; i++)
            cout << candidate[i] << " ";
          
        printBestCandidate(candidate, n);
      
        return 0;
    }

    Java

    // Java Program to test 1/e law for Secretary Problem :
    import java.util.*;
    class GFG
    {
    static double e = 2.71828;
      
    // To find closest integer of num.
    static int roundNo(float num)
    {
        return (int) (num < 0 ? 
                      num - 0.5 : num + 0.5);
    }
      
    // Finds best candidate using n/e rule. candidate[]
    // represents talents of n candidates.
    static void printBestCandidate(int candidate[], int n)
    {
        // Calculating sample size for benchmarking.
        int sample_size = roundNo((float) (n / e));
        System.out.println("\n\nSample size is " + sample_size);
      
        // Finding best candidate in sample size
        int best = 0; 
        for (int i = 1; i < sample_size; i++)
            if (candidate[i] > candidate[best])
                best = i;
      
        // Finding the first best candidate that is 
        // better than benchmark set.
        for (int i = sample_size; i < n; i++)
            if (candidate[i] >= candidate[best])
            {
                best = i;
                break;
            }
      
        if (best >= sample_size)
            System.out.println("\nBest candidate found is " + 
                               (best + 1) + " with talent " + 
                                candidate[best]);
        else
            System.out.print("Couldn't find a best candidate\n");
    }
      
    // Driver Code
    public static void main(String[] args)
    {
        int n = 8;
      
        // n = 8 candidates and candidate array contains
        // talents of n candidate where the largest 
        // number means highest talented candidate.
        int []candidate = new int[n];
      
        // generating random numbers between 1 to 8 
        // for talent of candidate
        Random rand = new Random();
        for (int i = 0; i < n; i++)
            candidate[i] = 1 + rand.nextInt((8 - 1) + 1);
      
        System.out.print("Candidate : ");
        for (int i = 0; i < n; i++)
            System.out.print(i + 1 + " ");
        System.out.println();
        System.out.print("Talents : ");
        for (int i = 0; i < n; i++)
            System.out.print(candidate[i] + " ");
          
        printBestCandidate(candidate, n);
    }
    }
      
    // This code is contributed by 29AjayKumar

    Python3

    # Python3 Program to test 1/e law for
    # Secretary Problem
    import random
    import math
      
    e = 2.71828;
      
    # To find closest integer of num.
    def roundNo(num):
        if(num < 0): 
            return (num - 0.5)
        else: 
            return (num + 0.5);
      
    # Finds best candidate using n/e rule. 
    # candidate[] represents talents of n candidates.
    def printBestCandidate(candidate, n):
          
        # Calculating sample size for benchmarking.
        sample_size = roundNo(n / e);
        print("\n\nSample size is", 
               math.floor(sample_size));
      
        # Finding best candidate in sample size
        best = 0; 
        for i in range(1, int(sample_size)):
            if (candidate[i] > candidate[best]):
                best = i;
      
        # Finding the first best candidate that 
        # is better than benchmark set.
        for i in range(int(sample_size), n):
            if (candidate[i] >= candidate[best]):
                best = i;
                break;
      
        if (best >= int(sample_size)):
            print("\nBest candidate found is", 
                         math.floor(best + 1), 
                  "with talent", math.floor(candidate[best]));
        else:
            print("Couldn't find a best candidate");
      
    # Driver code
    n = 8;
      
    # n = 8 candidates and candidate 
    # array contains talents of n 
    # candidate where the largest 
    # number means highest talented 
    # candidate.
    candidate = [0] * (n);
      
    # generating random numbers between 1 to 8 
    # for talent of candidate
    for i in range(n):
        candidate[i] = 1 + random.randint(1, 8);
    print("Candidate : ", end = "");
      
    for i in range(n):
        print((i + 1), end = " ");
    print("\nTalents : ", end = "");
      
    for i in range(n):
        print(candidate[i], end = " ");
       
    printBestCandidate(candidate, n);
      
    # This code is contributed by mits

    C#

    // C# Program to test 1/e law for Secretary Problem
    using System;
          
    class GFG
    {
    static double e = 2.71828;
      
    // To find closest integer of num.
    static int roundNo(float num)
    {
        return (int) (num < 0 ? 
                      num - 0.5 : num + 0.5);
    }
      
    // Finds best candidate using n/e rule. candidate[]
    // represents talents of n candidates.
    static void printBestCandidate(int []candidate, int n)
    {
        // Calculating sample size for benchmarking.
        int sample_size = roundNo((float) (n / e));
        Console.WriteLine("\n\nSample size is " + 
                                    sample_size);
      
        // Finding best candidate in sample size
        int best = 0; 
        for (int i = 1; i < sample_size; i++)
            if (candidate[i] > candidate[best])
                best = i;
      
        // Finding the first best candidate that is 
        // better than benchmark set.
        for (int i = sample_size; i < n; i++)
            if (candidate[i] >= candidate[best])
            {
                best = i;
                break;
            }
      
        if (best >= sample_size)
            Console.WriteLine("\nBest candidate found is " + 
                              (best + 1) + " with talent " + 
                                           candidate[best]);
        else
            Console.Write("Couldn't find a best candidate\n");
    }
      
    // Driver Code
    public static void Main(String[] args)
    {
        int n = 8;
      
        // n = 8 candidates and candidate array contains
        // talents of n candidate where the largest 
        // number means highest talented candidate.
        int []candidate = new int[n];
      
        // generating random numbers between 1 to 8 
        // for talent of candidate
        Random rand = new Random();
        for (int i = 0; i < n; i++)
            candidate[i] = 1 + rand.Next(1, 8);
      
        Console.Write("Candidate : ");
        for (int i = 0; i < n; i++)
            Console.Write(i + 1 + " ");
        Console.WriteLine();
        Console.Write("Talents : ");
        for (int i = 0; i < n; i++)
            Console.Write(candidate[i] + " ");
          
        printBestCandidate(candidate, n);
    }
    }
      
    // This code is contributed by Princi Singh

    PHP

    <?php
    // PHP Program to test 1/e 
    // law for Secretary Problem :
      
    $e = 2.71828;
      
    // To find closest 
    // integer of num.
    function roundNo($num)
    {
        return $num < 0 ? 
             $num - 0.5 : $num + 0.5;
    }
      
    // Finds best candidate using 
    // n/e rule. candidate[] 
    // represents talents of n candidates.
    function printBestCandidate($candidate, $n)
    {
        global $e;
          
        // Calculating sample size 
        // for benchmarking.
        $sample_size = roundNo($n / $e);
        echo "\n\nSample size is " . 
               floor($sample_size) . "\n";
      
        // Finding best candidate
        // in sample size
        $best = 0; 
        for ($i = 1; $i < $sample_size; $i++)
            if ($candidate[$i] > 
                $candidate[$best])
                $best = $i;
      
        // Finding the first best 
        // candidate that is better
        // than benchmark set.
        for ($i = $sample_size; $i < $n; $i++)
            if ($candidate[$i] >= 
                $candidate[$best])
            {
                $best = $i;
                break;
            }
      
        if ($best >= $sample_size)
            echo "\nBest candidate found is " . 
                             floor($best + 1) . 
                              " with talent " . 
                     floor($candidate[$best]) . "\n";
        else
            echo "Couldn't find a best candidate\n";
    }
      
    // Driver code
    $n = 8;
      
    // n = 8 candidates and candidate 
    // array contains talents of n 
    // candidate where the largest 
    // number means highest talented 
    // candidate.
    $candidate = array_fill(0, $n, 0);
      
    // generating random numbers 
    // between 1 to 8 for talent
    // of candidate
    for ($i = 0; $i < $n; $i++)
        $candidate[$i] = 1 + rand(1, 8);
    echo "Candidate : ";
      
    for ($i = 0; $i < $n; $i++)
        echo ($i + 1) . " ";
    echo "\n Talents : ";
      
    for ($i = 0; $i < $n; $i++)
        echo $candidate[$i] . " ";
      
    printBestCandidate($candidate, $n);
      
    // This code is contributed by mits
    ?>

    Producción:

Candidates : 1 2 3 4 5 6 7 8 
  Talents  : 5 3 8 6 5 7 8 6 

Sample size is 3

Best candidate found is 7 with talent 8

Estrategia óptima alternativa : esta estrategia, en lugar de elegir el tamaño de la muestra como n/e, selecciona la raíz cuadrada de n como el tamaño de muestra óptimo (es decir, sqrt(n) ).

Este artículo es una contribución de Shubham Rana . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *