Hispanopedia WikiEl principio de decisiones diferidas es una técnica utilizada en el análisis de algoritmos aleatorios .
Definición
Un algoritmo aleatorio realiza una serie de elecciones aleatorias. Estas elecciones pueden estar intrincadamente relacionadas, lo que dificulta su análisis. En muchos de estos casos, se utiliza el Principio de Decisiones Diferidas . La idea subyacente a este principio es que el conjunto completo de elecciones aleatorias no se realiza de antemano, sino que se fija únicamente a medida que se revelan al algoritmo.
Aplicaciones
El juego del solitario del reloj
Este principio se utiliza para evaluar y determinar la probabilidad de "ganar" con una baraja de cartas . La idea es dejar que las elecciones aleatorias se desarrollen hasta que la iteración termine en 52, momento en el que, si se extrae la cuarta carta de un grupo etiquetado como "K", el juego finaliza.
Referencias
Fuentes
- M. Mitzenmacher y E. Upfal . Probabilidad y computación : algoritmos aleatorios y análisis probabilístico. Cambridge University Press, Nueva York (NY), 2005. Sección 1.3, página 9.
- Algoritmos aleatorios
- Algoritmos y estructuras de datos básicos