Algoritmo de Las Vegas

En informática , un algoritmo de Las Vegas es un algoritmo aleatorio que siempre da resultados correctos ; es decir, siempre produce el resultado correcto o informa sobre el fallo. Sin embargo, el tiempo de ejecución de un algoritmo de Las Vegas difiere según la entrada. La definición habitual de un algoritmo de Las Vegas incluye la restricción de que el tiempo de ejecución esperado sea finito, donde la expectativa se realiza sobre el espacio de información aleatoria, o entropía, utilizado en el algoritmo. Una definición alternativa requiere que un algoritmo de Las Vegas siempre termine (sea efectivo ), pero puede generar un símbolo que no forma parte del espacio de soluciones para indicar que no se encontró una solución. ^{[ 1 ]} La naturaleza de los algoritmos de Las Vegas los hace adecuados en situaciones donde el número de posibles soluciones es limitado y donde verificar la corrección de una solución candidata es relativamente fácil, mientras que encontrar una solución es complejo.

Los métodos de búsqueda sistemática para problemas computacionalmente difíciles, como algunas variantes del algoritmo de Davis-Putnam para la satisfacibilidad proposicional (SAT), también utilizan decisiones no deterministas y, por lo tanto, también pueden considerarse algoritmos de Las Vegas. ^{[ 2 ]}

Historia

Los algoritmos de Las Vegas fueron introducidos por László Babai en 1979, en el contexto del problema del isomorfismo de grafos , como un dual de los algoritmos de Monte Carlo . ^{[ 3 ]} Babai ^{[ 4 ]} introdujo el término "algoritmo de Las Vegas" junto con un ejemplo que involucra lanzamientos de moneda: el algoritmo depende de una serie de lanzamientos de moneda independientes, y existe una pequeña probabilidad de fallo (ningún resultado). Sin embargo, a diferencia de los algoritmos de Monte Carlo, el algoritmo de Las Vegas puede garantizar la corrección de cualquier resultado reportado.

Ejemplo

int getRandomInteger ( int n ) { Random rand = new Random ( ); return rand.nextInt ( n ) ; }// Algoritmo de Las Vegas, suponiendo que a es un array de longitud n. // Objetivo: devolver un índice correcto k tal que a[k] == 1. int lasVegasAlgorithm ( int [] a ) { int n = a . length ; while ( true ) { int k = getRandomInteger ( n ); if ( a [ k ] == 1 ) { return k ; } } }

Como se mencionó anteriormente, los algoritmos de Las Vegas siempre devuelven resultados correctos. El código anterior ilustra esta propiedad. El objetivo es encontrar un índice en el arreglo que contenga el valor 1. Se genera auna variable aleatoriamente; después de generarla, se utiliza para indexar el arreglo . Si este índice contiene el valor 1, se devuelve; de lo contrario, el algoritmo repite este proceso hasta encontrar 1. Si bien este algoritmo de Las Vegas garantiza encontrar la respuesta correcta, no tiene un tiempo de ejecución fijo; debido a la aleatorización, es posible que transcurra un tiempo arbitrariamente prolongado antes de que el algoritmo finalice.kkkak

Definición

Esta sección describe las condiciones que caracterizan a un algoritmo como de tipo Las Vegas.

Un algoritmo A es un algoritmo de Las Vegas para la clase de problema X, si ^{[ 5 ]}

Siempre que para una instancia de problema dada x∈X devuelva una solución s, se garantiza que s es una solución válida de x.
En cada instancia x dada, el tiempo de ejecución de A es una variable aleatoria RT _A,x.

Existen tres nociones de completitud para los algoritmos de Las Vegas:

Se puede garantizar que los algoritmos completos de Las Vegas resuelvan cada problema resoluble dentro del tiempo de ejecución t max, donde t max es una constante que depende de la instancia.

Sea P(RT _A,x ≤ t) la probabilidad de que A encuentre una solución para una instancia soluble x en un tiempo dentro de t, entonces A es completa exactamente si para cada x existe

algún t max tal que P(RT _A,x ≤ t _max ) = 1.

Los algoritmos de Las Vegas aproximadamente completos resuelven cada problema con una probabilidad que converge a 1 a medida que el tiempo de ejecución se aproxima al infinito. Por lo tanto, A es aproximadamente completo si para cada instancia x, lim _t→∞ P(RT _A,x ≤ t) = 1.
Los algoritmos de Las Vegas esencialmente incompletos son algoritmos de Las Vegas que no están aproximadamente completos.

La completitud aproximada es principalmente de interés teórico, ya que los plazos para encontrar soluciones suelen ser demasiado largos para ser de utilidad práctica.

Escenarios de aplicación

Los algoritmos de Las Vegas tienen diferentes criterios de evaluación según el problema planteado. Estos criterios se dividen en tres categorías con distintos límites de tiempo, ya que los algoritmos de Las Vegas no tienen una complejidad temporal fija . A continuación, se presentan algunos posibles escenarios de aplicación:

Tipo 1: No hay límites de tiempo, lo que significa que el algoritmo se ejecuta hasta que encuentra la solución.
Tipo 2: Existe un límite de tiempo t _max para encontrar el resultado.
Tipo 3: La utilidad de una solución se determina por el tiempo necesario para encontrarla.

(Los tipos 1 y 2 son casos especiales del tipo 3).

Para el Tipo 1, donde no hay límite de tiempo, el tiempo de ejecución promedio puede representar el comportamiento en tiempo de ejecución. Este no es el mismo caso para el Tipo 2.

Aquí, P ( RT ≤ t _max ), que es la probabilidad de encontrar una solución dentro del tiempo, describe su comportamiento en tiempo de ejecución.

En el caso del Tipo 3, su comportamiento en tiempo de ejecución solo puede representarse mediante la función de distribución en tiempo de ejecución rtd : R → [0,1] definida como rtd ( t ) = P ( RT ≤ t ) o su aproximación.

La distribución en tiempo de ejecución (RTD, por sus siglas en inglés) es la forma distintiva de describir el comportamiento en tiempo de ejecución de un algoritmo de Las Vegas.

Con estos datos, podemos obtener fácilmente otros criterios como el tiempo de ejecución medio, la desviación estándar , la mediana, los percentiles o las probabilidades de éxito P ( RT ≤ t ) para límites de tiempo arbitrarios t .

Aplicaciones

Analogía

Los algoritmos de Las Vegas aparecen con frecuencia en problemas de búsqueda . Por ejemplo, quien busca información en línea podría consultar sitios web relacionados. La complejidad temporal varía desde tener suerte y encontrar el contenido de inmediato, hasta no tener suerte y dedicar mucho tiempo. Una vez encontrado el sitio web correcto, no hay posibilidad de error. ^{[ 6 ]}

Ordenación rápida aleatoria

def randomized_quicksort ( a : list [ int ]) -> None : if len ( a ) == 1 : return A # A está ordenado. else : i : int = random.randrange ( 1 , len ( a )) # Tomará un número aleatorio en el rango [1, len(a)) x : int = a [ i ] # El elemento pivote# Divide a en elementos < x, x y > x, como se muestra en la figura anterior. # Ejecuta Quicksort en a[1 : i- 1] y A[i + 1 : n]. # Combina las respuestas para obtener un arreglo ordenado.

Un ejemplo sencillo es el algoritmo QuickSort aleatorio , donde el pivote se elige al azar y divide los elementos en tres particiones: elementos menores que el pivote, elementos iguales al pivote y elementos mayores que el pivote. QuickSort siempre genera la solución, que en este caso es el array ordenado . Desafortunadamente, la complejidad temporal no es tan obvia. Resulta que el tiempo de ejecución depende del elemento que elijamos como pivote.

El peor caso Θ( n ² ) cuando el pivote es el elemento más pequeño o el más grande.

T(n)=T(0)+T(n-1)+\Theta (n)

T(n)=\Theta (1)+T(n-1)+\Theta (n)

T(n)=T(n-1)+\Theta (n)

T(n)=\Theta (n^{2})

Sin embargo, mediante la aleatorización, donde el pivote se elige aleatoriamente y es exactamente un valor medio cada vez, el QuickSort se puede realizar en Θ( n log n ).

T(n)\leq 2*T(n/2)+\Theta (n)

T(n)=\Theta (n\log(n))

El tiempo de ejecución de Quicksort depende en gran medida de la correcta selección del pivote. Si el valor del pivote es demasiado grande o pequeño, la partición estará desequilibrada, lo que resultará en una baja eficiencia. Sin embargo, si el valor del pivote se encuentra cerca del centro del array, la partición estará razonablemente bien equilibrada, lo que se traduce en un tiempo de ejecución más rápido. Dado que el pivote se elige aleatoriamente, el tiempo de ejecución será bueno la mayor parte del tiempo y malo ocasionalmente.

En el caso promedio, es difícil determinarlo, ya que el análisis no depende de la distribución de entrada, sino de las elecciones aleatorias que realiza el algoritmo. El promedio de quicksort se calcula sobre todas las posibles elecciones aleatorias que el algoritmo podría realizar al elegir el pivote.

Aunque el tiempo de ejecución en el peor de los casos es Θ( n² ), el tiempo de ejecución promedio es Θ( n log n ). Resulta que el peor de los casos no ocurre con frecuencia. Para valores grandes de ⁿ, el tiempo de ejecución es Θ( n log n ) con alta probabilidad.

Nótese que la probabilidad de que el pivote sea el elemento de valor medio en cada iteración es de una entre n números, lo cual es muy raro. Sin embargo, el tiempo de ejecución sigue siendo el mismo cuando la división es del 10 % al 90 % en lugar del 50 % al 50 %, ya que la profundidad del árbol de recursión seguirá siendo O (log n ), con O ( n ) veces tomadas cada nivel de recursión.

Algoritmo voraz aleatorio para el problema de las ocho reinas

El problema de las ocho reinas se suele resolver con un algoritmo de retroceso . Sin embargo, también se puede aplicar el algoritmo de Las Vegas, que de hecho es más eficiente que el de retroceso.

Coloca ocho reinas en un tablero de ajedrez de manera que ninguna ataque a otra. Recuerda que una reina ataca a las piezas que se encuentran en la misma fila, columna y diagonal.

Supongamos que k filas, 0 ≤ k ≤ 8, están ocupadas con éxito por reinas.

Si k = 8, entonces finaliza con éxito. De lo contrario, procede a ocupar la fila k + 1.

Calcula todas las posiciones en esta fila que no hayan sido atacadas por reinas existentes. Si no hay ninguna, falla. De lo contrario, elige una al azar, incrementa k y repite.

Nótese que el algoritmo simplemente falla si no se puede colocar una reina. Pero el proceso se puede repetir y cada vez generará una disposición diferente. ^{[ 7 ]}

Clase de complejidad

La clase de complejidad de los problemas de decisión que tienen algoritmos de Las Vegas con un tiempo de ejecución polinomial esperado es ZPP .

Resulta que

{\textsf {ZPP}}={\textsf {RP}}\cap {\textsf {co-RP}}

Esto está íntimamente relacionado con la forma en que a veces se construyen los algoritmos de Las Vegas. Concretamente, la clase RP comprende todos los problemas de decisión para los que existe un algoritmo aleatorio de tiempo polinomial que siempre responde correctamente cuando la respuesta correcta es "no", pero que puede equivocarse con una cierta probabilidad acotada inferiormente a uno cuando la respuesta es "sí". Cuando existe un algoritmo de este tipo tanto para un problema como para su complemento (con las respuestas "sí" y "no" intercambiadas), ambos algoritmos pueden ejecutarse simultáneamente y de forma repetida: cada uno se ejecuta durante un número constante de pasos, alternándose, hasta que uno de ellos devuelve una respuesta definitiva. Esta es la forma estándar de construir un algoritmo de Las Vegas que se ejecuta en tiempo polinomial esperado. Cabe señalar que, en general, no existe un límite superior en el peor de los casos para el tiempo de ejecución de un algoritmo de Las Vegas.

Algoritmo óptimo de Las Vegas

Para que un algoritmo de Las Vegas sea óptimo, se debe minimizar el tiempo de ejecución esperado. Esto se puede lograr mediante:

El algoritmo de Las Vegas A ( x ) se ejecuta repetidamente durante un número determinado _de_pasost1 . Si A ( x ) se detiene durante el tiempo de ejecución, entonces A ( x ) ha terminado; de lo contrario, se repite el proceso desde el principio durante otros t2 pasos, y así sucesivamente.
Diseñar una estrategia que sea óptima entre todas las estrategias para A ( x ), dada la información completa sobre la distribución de T _A ( x ).

La existencia de una estrategia óptima puede ser una observación teórica fascinante. Sin embargo, no es práctica en la vida real porque no es fácil encontrar información sobre la distribución de T _A ( x ). Además, no tiene sentido repetir el experimento varias veces para obtener información sobre la distribución, ya que en la mayoría de los casos, la respuesta solo se necesita una vez para cualquier x . ^{[ 8 ]}

Relación con los algoritmos de Monte Carlo

Los algoritmos de Las Vegas se diferencian de los algoritmos de Monte Carlo , en los que los recursos utilizados son limitados, pero la respuesta puede ser incorrecta con una probabilidad determinada (generalmente pequeña) . Un algoritmo de Las Vegas se puede convertir en un algoritmo de Monte Carlo ejecutándolo durante un tiempo fijo y generando una respuesta aleatoria cuando no finaliza. Mediante la aplicación de la desigualdad de Markov , podemos establecer un límite para la probabilidad de que el algoritmo de Las Vegas supere dicho límite.

Aquí hay una tabla que compara los algoritmos de Las Vegas y Monte Carlo: ^{[ 9 ]}

Si se dispone de un método determinista para comprobar la corrección, es posible convertir un algoritmo de Monte Carlo en un algoritmo de Las Vegas. Sin embargo, resulta difícil convertir un algoritmo de Monte Carlo a un algoritmo de Las Vegas sin un método para probarlo. Por otro lado, convertir un algoritmo de Las Vegas a un algoritmo de Monte Carlo es sencillo. Esto se puede lograr ejecutando el algoritmo de Las Vegas durante un período de tiempo específico determinado por un parámetro de confianza. Si el algoritmo encuentra la solución dentro de ese tiempo, se considera exitoso; de lo contrario, la salida puede ser simplemente "lo sentimos".

Este es un ejemplo de los algoritmos de Las Vegas y Monte Carlo para su comparación: ^{[ 10 ]}

Supongamos que tenemos un arreglo de longitud par n . La mitad de los elementos del arreglo son 0 y la otra mitad son 1. El objetivo es encontrar un índice que contenga un 1.

// Algoritmo de Las Vegas int lasVegasAlgorithm ( int [] a ) { int n = a . longitud ; mientras ( verdadero ) { int k = getRandomInteger ( n ); si ( a [ k ] == 1 ) { retorno k ; } } }// Algoritmo de Monte Carlo int monteCarloAlgorithm ( int [] a ) { int n = a . length ; for ( int i = 0 ; i < 300 ; ++ i ) { int k = getRandomInteger ( n ); if ( a [ k ] == 1 ) { return k ; } } return - 1 ; // indica fallo }

Dado que el algoritmo de Las Vegas no finaliza hasta encontrar el 1 en el array, no arriesga la corrección, sino el tiempo de ejecución. Por otro lado, el algoritmo de Monte Carlo se ejecuta 300 veces, lo que significa que es imposible saber si encontrará el "1" en el array en 300 iteraciones hasta que se ejecute el código. Puede que encuentre la solución o no. Por lo tanto, a diferencia de Las Vegas, el algoritmo de Monte Carlo no arriesga el tiempo de ejecución, sino la corrección.

Véase también

Referencias

Citas

↑ Steven D. Galbraith (2012). Matemáticas de la criptografía de clave pública . Cambridge University Press. pág. 16. ISBN 978-1-107-01392-6.
↑ Hoos, Holger H.. “Sobre la evaluación empírica de los algoritmos de Las Vegas: documento de posición.” (1998).
↑
- László Babai , Algoritmos de Monte-Carlo en pruebas de isomorfismo de gráficos , Universidad de Montréal, DMS No. 79-10.
- Leonid Levin , El cuento de las funciones unidireccionales , Problemas de transmisión de información , vol. 39 (2003), 92-103.
- Dan Grundy, Conceptos y cálculo en criptografía, archivado el 12 de abril de 2016 en Wayback Machine , Universidad de Kent, tesis doctoral, 2008.
↑ Babai, László. "Algoritmos de Monte-Carlo en pruebas de isomorfismo de gráficos". (1979).
↑ HH Hoos y T. Stützle. Evaluación de algoritmos de Las Vegas: escollos y soluciones. En Actas de la Decimocuarta Conferencia sobre Incertidumbre en Inteligencia Artificial (UAI-98), páginas 238-245. Morgan Kaufmann Publishers, San Francisco, CA, 1998.
↑ Algoritmos aleatorios. Brilliant.org . Recuperado a las 23:54 del 24 de octubre de 2018, de https://brilliant.org/wiki/randomized-algorithms-overview/
↑ Barringer, Howard (diciembre de 2010). "Algoritmos aleatorios: una breve introducción" (PDF) . www.cs.man.ac.uk. Consultado el 8 de diciembre de 2018 .
↑ Luby, Michael (27 de septiembre de 1993). "Optimal Speedup of Las Vegas algorithms". Information Processing Letters . 47 (4): 173– 180. doi : 10.1016/0020-0190(93)90029-9 .
↑ Goodrich, Michael. Diseño y aplicaciones de algoritmos: algoritmos aleatorios. Wiley, 2015 , https://nscpolteksby.ac.id/ebook/files/Ebook/Computer%20Engineering/Algorithm%20Design%20and%20Applications%20A4%20(2015)/20.%20Chapter%2019%20-%20Randomized%20Algorithms.pdf . 23 de octubre de 2018.
↑ Procaccia, Ariel (5 de noviembre de 2015). "Grandes ideas teóricas en informática" (PDF) . www.cs.cmu.edu ( PowerPoint ) . Consultado el 3 de noviembre de 2018 .

Fuentes

Manual de algoritmos y teoría de la computación , CRC Press LLC, 1999.
«Algoritmo de Las Vegas», en Diccionario de algoritmos y estructuras de datos [en línea], Paul E. Black, ed., Instituto Nacional de Estándares y Tecnología de EE . UU. 17 de julio de 2006. (Consultado el 9 de mayo de 2009) Disponible en:

[Galbraith201222-1] Steven D. Galbraith (2012). Matemáticas de la criptografía de clave pública . Cambridge University Press. pág. 16. ISBN 978-1-107-01392-6.

[2] Hoos, Holger H.. “Sobre la evaluación empírica de los algoritmos de Las Vegas: documento de posición.” (1998).

[3] 
László Babai , Algoritmos de Monte-Carlo en pruebas de isomorfismo de gráficos , Universidad de Montréal, DMS No. 79-10.
Leonid Levin , El cuento de las funciones unidireccionales , Problemas de transmisión de información , vol. 39 (2003), 92-103.
Dan Grundy, Conceptos y cálculo en criptografía, archivado el 12 de abril de 2016 en Wayback Machine , Universidad de Kent, tesis doctoral, 2008.

[mwAlo] László Babai , Algoritmos de Monte-Carlo en pruebas de isomorfismo de gráficos , Universidad de Montréal, DMS No. 79-10.

[mwAl0] Leonid Levin , El cuento de las funciones unidireccionales , Problemas de transmisión de información , vol. 39 (2003), 92-103.

[mwAmE] Dan Grundy, Conceptos y cálculo en criptografía, archivado el 12 de abril de 2016 en Wayback Machine , Universidad de Kent, tesis doctoral, 2008.

[4] Babai, László. "Algoritmos de Monte-Carlo en pruebas de isomorfismo de gráficos". (1979).

[5] HH Hoos y T. Stützle. Evaluación de algoritmos de Las Vegas: escollos y soluciones. En Actas de la Decimocuarta Conferencia sobre Incertidumbre en Inteligencia Artificial (UAI-98), páginas 238-245. Morgan Kaufmann Publishers, San Francisco, CA, 1998.

[6] Algoritmos aleatorios. Brilliant.org . Recuperado a las 23:54 del 24 de octubre de 2018, de https://brilliant.org/wiki/randomized-algorithms-overview/

[7] Barringer, Howard (diciembre de 2010). "Algoritmos aleatorios: una breve introducción" (PDF) . www.cs.man.ac.uk. Consultado el 8 de diciembre de 2018 .

[8] Luby, Michael (27 de septiembre de 1993). "Optimal Speedup of Las Vegas algorithms". Information Processing Letters . 47 (4): 173– 180. doi : 10.1016/0020-0190(93)90029-9 .

[9] Goodrich, Michael. Diseño y aplicaciones de algoritmos: algoritmos aleatorios. Wiley, 2015 , https://nscpolteksby.ac.id/ebook/files/Ebook/Computer%20Engineering/Algorithm%20Design%20and%20Applications%20A4%20(2015)/20.%20Chapter%2019%20-%20Randomized%20Algorithms.pdf . 23 de octubre de 2018.

[10] Procaccia, Ariel (5 de noviembre de 2015). "Grandes ideas teóricas en informática" (PDF) . www.cs.cmu.edu ( PowerPoint ) . Consultado el 3 de noviembre de 2018 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]