El problema de la novia exigente

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 22 de noviembre de 2021; la verificación requiere 1 edición .

El problema de la novia quisquillosa ( problema de detención de la elección ) es un problema de optimización formulado por primera vez por Martin Gardner en 1960 .

En la literatura inglesa, también se encuentra bajo el nombre de problema de la secretaria .

Redacción

La tarea se puede formular de la siguiente manera [1] :

  1. La novia busca novio (solo hay una vacante).
  2. Hay un número conocido de contendientes - .
  3. La novia se comunica con los solicitantes en orden aleatorio, con cada uno no más de una vez.
  4. Los solicitantes forman un orden lineal : asimétrico, transitivo y dos cualesquiera son comparables: se sabe que cada solicitante es mejor o peor que cualquiera de los anteriores.
  5. Después de hablar con el solicitante, la novia lo compara con los anteriores y rechaza o acepta su propuesta. Si se acepta la propuesta, se casan y el proceso se detiene. Si la novia rechaza al novio, entonces no podrá volver con él más tarde.
  6. El objetivo  es elegir al mejor candidato. Incluso el segundo no le conviene.

Decisiones

En 1963, Evgeny Dynkin propuso una solución a este problema para un caso particular. La solución general fue encontrada por Sabir Hussein-Zade en 1966 .

Este problema ha recibido mucha atención, en gran parte porque la estrategia óptima tiene una característica interesante: si el número de candidatos es lo suficientemente grande, la estrategia óptima será rechazar a todos los primeros (donde  está la base del logaritmo natural ) solicitantes y luego elige el primero que es mejor que todos los anteriores [2] . Al aumentar , la probabilidad de elegir al mejor candidato tiende a , es decir, aproximadamente al 37%.

Variantes del problema

Entre las variantes y generalizaciones del problema, se encuentran aquellas en las que no se conoce de antemano el número total de solicitantes, o aquellas en las que para cada solicitante es posible no sólo compararlo con los demás, sino también darle una evaluación absoluta [3] .

En la disertación de Boris Berezovsky , luego miembro correspondiente de la Academia Rusa de Ciencias , para el grado de Doctor en Ciencias "Desarrollo de los fundamentos teóricos de la algoritmización para tomar decisiones previas al proyecto y su aplicación", defendida en 1983, una generalización del problema de una novia quisquillosa se considera [4] .

Historia

El problema de la novia exigente parece haber sido presentado en 1949 por Merrill M. Flood, quien lo llamó el problema de la novia en una conferencia que dio el mismo año. Lo mencionó varias veces durante la década de 1950, como en un discurso en una conferencia en Purdue el 9 de mayo de 1958, y finalmente se hizo ampliamente conocido por el público, aunque no se publicó nada en ese momento. En 1958, envió una carta a Leonard Gillman, con copias, a una docena de amigos, entre ellos Samuel Carlin y J. Robbins, esbozando una prueba de la estrategia óptima con un apéndice de R. Palermo, quien demostró que todas las estrategias están dominadas por la estrategia de "rechazar incondicionalmente al primer p, luego aceptar al próximo candidato que sea mejor".

Aparentemente, la primera publicación fue de Martin Gardner en Scientific American , febrero de 1960. Se enteró por John H. Fox, Jr. y L. Gerald Marney, quienes de forma independiente plantearon un problema similar en 1958; lo llamaron "juego de googol". Fox y Marnie no conocían la solución óptima; Gardner buscó el consejo de Leo Moser, quien (junto con J. R. Pounder) proporcionó el análisis correcto para su publicación en la revista. Poco después, varios matemáticos le escribieron a Gardner para contarle un problema equivalente del que habían oído rumores, y lo más probable es que todos convergieran en el trabajo original de Flood.

La ley 1/e de mejor elección se debe a F. Thomas Bruce (1984).

Ferguson (1989) tiene una extensa bibliografía y señala que un problema similar (pero diferente) fue considerado por Arthur Cayley en 1875 e incluso por Johannes Kepler mucho antes.

Notas

  1. ↑ Hussein-Zade, 2003 , pág. 3-4.
  2. ↑ Hussein-Zade, 2003 , pág. Dieciocho.
  3. ↑ Pinzón, 2003 .
  4. ↑ Hussein-Zade, 2003 .

Enlaces