Algoritmo de Las Vegas - Las Vegas algorithm

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 del 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 lleva a cabo 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 la solución para indicar un error en la búsqueda de una solución. La naturaleza de los algoritmos de Las Vegas los hace adecuados en situaciones en las que el número de posibles soluciones es limitado y en las que verificar la exactitud de una solución candidata es relativamente fácil, mientras que encontrar una solución es complejo.

Los algoritmos de Las Vegas son prominentes en el campo de la inteligencia artificial y en otras áreas de la ciencia de la computación y la investigación de operaciones . En IA, los algoritmos de búsqueda local estocástica (SLS) se consideran del tipo de Las Vegas. Los algoritmos SLS se han utilizado para abordar problemas de decisión NP-completos y problemas de optimización combinatoria NP-hard . Sin embargo, algunos métodos de búsqueda sistemática, como las variantes modernas del algoritmo 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.

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 a los algoritmos de Monte Carlo . Babai introdujo el término "algoritmo de Las Vegas" junto con un ejemplo que involucra lanzamientos de monedas: el algoritmo depende de una serie de lanzamientos de monedas independientes y existe una pequeña posibilidad de falla (sin resultado). Sin embargo, a diferencia de los algoritmos de Monte Carlo, el algoritmo de Las Vegas puede garantizar la exactitud de cualquier resultado informado.

Ejemplo

// Las Vegas algorithm
repeat:
    k = RandInt(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. Una variable k se genera aleatoriamente; después de k se genera, k se usa para indexar la matriz A . Si este índice contiene el valor 1, se devuelve k ; de lo contrario, el algoritmo repite este proceso hasta que encuentra 1. Aunque se garantiza que este algoritmo de Las Vegas encontrará la respuesta correcta, no tiene un tiempo de ejecución fijo; debido a la aleatorización (en la línea 3 del código anterior), es posible que transcurra arbitrariamente mucho tiempo antes de que finalice el algoritmo.

Definición

Esta sección proporciona las condiciones que caracterizan que un algoritmo sea del tipo Las Vegas.

Un algoritmo A es un algoritmo de Las Vegas para la clase de problema X, si

1. siempre que para una instancia de problema dada x∈X devuelve una solución s, se garantiza que s es una solución válida de x
2. en cada instancia dada x, el tiempo de ejecución de A es una variable aleatoria RT _{A, x}

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

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

Sea P (RT _{A, x} ≤ t) la probabilidad de que A encuentre una solución para una instancia soluble x en el tiempo dentro de t, entonces A está completa exactamente si para cada x existe

algunos t max tales 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 cuando el tiempo de ejecución se acerca 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 exhaustividad aproximada es principalmente de interés teórico, ya que los límites de tiempo para encontrar soluciones suelen ser demasiado grandes para ser de utilidad práctica.

Escenarios de aplicación

Los algoritmos de Las Vegas tienen diferentes criterios para la evaluación según el entorno del problema. Estos criterios se dividen en tres categorías con diferentes límites de tiempo, ya que los algoritmos de Las Vegas no tienen una complejidad de tiempo establecida. A continuación, se muestran 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: Hay un límite de tiempo t _max para encontrar el resultado.

Tipo 3: la utilidad de una solución está determinada por el tiempo necesario para encontrar la solución.

Tenga en cuenta que el tipo 1 y el tipo 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 del 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 en el 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 de 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) 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 surgen con frecuencia en los problemas de búsqueda . Por ejemplo, alguien que busca información en línea puede buscar en sitios web relacionados la información deseada. Por lo tanto, la complejidad del tiempo varía desde tener "suerte" y encontrar el contenido de inmediato, hasta tener "mala suerte" y dedicar una gran cantidad de tiempo. Una vez que se encuentra el sitio web correcto, no hay posibilidad de error.

QuickSort aleatorio

INPUT: 
    # A is an array of n elements
def randomized_quicksort(A):
    if n == 1:
        return A  # A is sorted.
    else:
        i = random.randrange(1, n)  # Will take a random number in the range 1~n
        X = A[i]  # The pivot element
    """Partition A into elements < x, x, and >x  # as shown in the figure above.
    Execute Quicksort on A[1 to i-1] and A[i+1 to n].
    Combine the responses in order to obtain a sorted array."""

Un ejemplo simple es QuickSort aleatorio , donde el pivote se elige al azar y divide los elementos en tres particiones: elementos menores que pivote, elementos iguales a pivote y elementos mayores que pivote. El QuickSort aleatorio requiere muchos recursos pero siempre genera la matriz ordenada como salida.

Es obvio que QuickSort siempre genera la solución, que en este caso la matriz ordenada. Desafortunadamente, la complejidad del tiempo no es tan obvia. Resulta que el tiempo de ejecución depende de qué elemento elegimos como pivote.

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

${\ Displaystyle T (n) = T (0) + T (n-1) + \ Theta (n)}$

${\ Displaystyle T (n) = \ Theta (1) + T (n-1) + \ Theta (n)}$

${\ Displaystyle T (n) = T (n-1) + \ Theta (n)}$

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

• Sin embargo, a través de la aleatorización, donde el pivote se elige al azar y es exactamente un valor medio cada vez, QuickSort se puede hacer en Θ ( n log n ).

${\ Displaystyle T (n) \ leq 2 * T (n / 2) + \ Theta (n)}$

${\ Displaystyle T (n) = \ Theta (n \ log (n))}$

El tiempo de ejecución de QuickSort depende en gran medida de qué tan bien se seleccione el pivote. Si un valor de pivote es demasiado grande o pequeño, la partición estará desequilibrada. Este caso da un mal tiempo de ejecución. Sin embargo, si el valor de pivote está cerca de la mitad de la matriz, entonces la división estará razonablemente bien equilibrada. Por lo tanto, su tiempo de ejecución será bueno. Dado que el pivote se elige al azar, el tiempo de ejecución será bueno la mayor parte del tiempo y malo ocasionalmente.

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

Aunque el tiempo de ejecución del caso más desfavorable es Θ ( n ² ), el tiempo de ejecución promedio del caso es Θ ( n log n ). Resulta que el peor de los casos no ocurre con frecuencia. Para valores grandes de n , el tiempo de ejecución es Θ ( n log n ) con una alta probabilidad.

Tenga en cuenta que la probabilidad de que el pivote sea el elemento de valor medio cada vez es uno de n números, lo cual es muy raro. Sin embargo, sigue siendo el mismo tiempo de ejecución cuando la división es 10% -90% en lugar de 50% -50% porque la profundidad del árbol de recursividad seguirá siendo O (log n ) con O ( n ) veces tomadas cada nivel de recursividad.

Algoritmo codicioso aleatorio para el problema de ocho reinas

El problema de las ocho reinas generalmente se resuelve con un algoritmo de retroceso. Sin embargo, se puede aplicar un algoritmo de Las Vegas; de hecho, es más eficaz que retroceder.

Coloca 8 reinas en un tablero de ajedrez para que nadie ataque a otro. Recuerda que una reina ataca a otras piezas de la misma fila, columna y diagonales.

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

Si k = 8, deténgase con éxito. De lo contrario, proceda a ocupar la fila k + 1.

Calcula todas las posiciones en esta fila no atacadas por reinas existentes. Si no hay ninguno, falla. De lo contrario, elija uno al azar, incremente k y repita.

Tenga en cuenta que los algoritmos simplemente fallan si no se puede colocar una reina. Pero el proceso puede repetirse y cada vez generará una disposición diferente.

Clase de complejidad

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

Resulta que

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

que está íntimamente relacionado con la forma en que a veces se construyen los algoritmos de Las Vegas. Es decir, la clase RP consta de todos los problemas de decisión para los que existe un algoritmo de tiempo polinomial aleatorio que siempre responde correctamente cuando la respuesta correcta es "no", pero se permite que esté equivocada con una cierta probabilidad limitada a una cuando la respuesta es " sí". Cuando tal algoritmo existe tanto para un problema como para su complemento (con las respuestas "sí" y "no" intercambiadas), los dos algoritmos se pueden ejecutar de forma simultánea y repetida: ejecutar cada uno para un número constante de pasos, por turnos, 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 el tiempo polinomial esperado. Tenga en cuenta que, en general, no existe el límite superior del peor de los casos en 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 hacer mediante:

1. El algoritmo de Las Vegas A ( x ) se ejecuta repetidamente durante algunos pasos del número t ₁ . Si A ( x ) se detiene durante el tiempo de ejecución, entonces A ( x ) está terminado; de lo contrario, repita el proceso desde el principio durante otros t ₂ pasos, y así sucesivamente.
2. 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 la estrategia óptima podría ser una observación teórica fascinante. Sin embargo, no es práctico en la vida real porque no es fácil encontrar la información de distribución de T _A ( x ). Además, no tiene sentido ejecutar el experimento repetidamente para obtener la información sobre la distribución, ya que la mayoría de las veces, la respuesta solo se necesita una vez para cualquier x .

Relación con los algoritmos de Monte Carlo

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

Aquí hay una tabla que compara los algoritmos de Las Vegas y Monte Carlo:

Si está disponible una forma determinista de probar la corrección, entonces es posible convertir un algoritmo de Monte Carlo en un algoritmo de Las Vegas. Sin embargo, es difícil convertir un algoritmo de Monte Carlo en un algoritmo de Las Vegas sin una forma de probar el algoritmo. Por otro lado, cambiar un algoritmo de Las Vegas a un algoritmo de Monte Carlo es fácil. Esto se puede hacer ejecutando un algoritmo de Las Vegas durante un período de tiempo específico dado por el parámetro de confianza. Si el algoritmo encuentra la solución dentro del tiempo, entonces es un éxito y si no, la salida simplemente puede ser "lo siento".

Este es un ejemplo de los algoritmos de Las Vegas y Monte Carlo para comparar:

Suponga que hay una matriz con la longitud par n . La mitad de las entradas de la matriz son ceros y la mitad restante son unos. El objetivo aquí es encontrar un índice que contenga un 1.

//Las Vegas algorithm
repeat:
    k = RandInt(n)
    if A[k] == 1,
        return k;
        
//Monte Carlo algorithm
repeat 300 times:
    k = RandInt(n)
    if A[k] == 1
        return k
return "Failed"

Dado que Las Vegas no termina hasta que encuentra 1 en la matriz, no juega con la corrección sino con el tiempo de ejecución. Por otro lado, Monte Carlo se ejecuta 300 veces, lo que significa que es imposible saber que Monte Carlo encontrará "1" en la matriz dentro de 300 bucles hasta que realmente ejecute el código. Puede que encuentre la solución o no. Por lo tanto, a diferencia de Las Vegas, Montecarlo no apuesta por el tiempo de ejecución, sino por la corrección.

Ver también

• Algoritmo de Montecarlo
• Algoritmo de Atlantic City
• Aleatoriedad

Referencias

Citas

Fuentes