Las Vegas (algoritmo)

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 24 de julio de 2019; la verificación requiere 1 edición .

Las Vegas es un tipo de algoritmo probabilístico (ver también Algoritmos de Monte Carlo ).

La idea detrás del algoritmo de Las Vegas es la siguiente. Si tenemos un cierto algoritmo probabilístico que da el resultado correcto con cierta probabilidad, y es posible verificar algorítmicamente el resultado del algoritmo para ver si es correcto (digamos, usando el algoritmo ), entonces podemos ejecutar el algoritmo hasta que la verificación establezca que el resultado es correcto $A$ $A$ $k$ $A$

Ejecute el algoritmo con el resultado hasta que sea verdadero.

A

r

{\ estilo de visualización K (r)}

El nombre de este principio se dio por un lado en alusión al método Monte Carlo . Por otro lado, este nombre alude al "método ganador del casino", que es similar al proceso del algoritmo: "si juego una y otra vez, definitivamente ganaré algún día".

Cabe señalar que el algoritmo de Las Vegas garantiza un resultado correcto. El algoritmo se ejecuta en un tiempo finito pero no determinista. Solo puede especificar la probabilidad de obtener un resultado en un tiempo determinado.

Un ejemplo de un algoritmo relacionado con la clase de Las Vegas es el algoritmo de clasificación Bogosort : los datos que se clasificarán se barajan aleatoriamente y luego se verifica si están en el orden correcto. En caso de falla, se repite la mezcla muchas veces hasta alcanzar el orden deseado.

Relación con los algoritmos de Monte Carlo

Sea un algoritmo de Las Vegas con la complejidad de tiempo esperada , donde es la longitud de entrada. Si nos detenemos después de los pasos ( ), obtenemos un algoritmo de Monte Carlo con una probabilidad de error de . Para probar el teorema, considere como entrada de longitud y - una variable aleatoria que describe la complejidad temporal de . Entonces la esperanza matemática y según la desigualdad de Markov : . $\mathcal{A}$ $f(n)$ $norte$ $\mathcal{A}$ ${\ estilo de visualización \ alfa \ cdot f (n)}$ $0<\alfa<1$ ${\ matemáticas {B}}$ $1/\alfa$ $X$ $norte$ $T$ $\mathcal{A}$ $\mathbb {E} [T]\leqslant f(n)$ $\mathbb {P} r[T\geqslant \alpha \cdot f(n)]\leqslant \mathbb {P} r[T\geqslant \alpha \cdot \mathbb {E} [T]]\leqslant 1 /\alfa$

Enlaces

Manual de algoritmos y teoría de la computación , CRC Press LLC, 1999
"Algoritmo de Las Vegas" / Diccionario de algoritmos y estructuras de datos , Paul E. Black, ed., NIST de EE. UU . 17 de julio de 2006.