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 en el espacio de información aleatoria, o entropía, utilizada 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 solución para indicar que no se ha podido encontrar una solución. [1] La naturaleza de los algoritmos de Las Vegas los hace adecuados en situaciones donde el número de soluciones posibles es limitado y donde 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 destacados en el campo de la inteligencia artificial y en otras áreas de la informática y la investigación de operaciones . En IA, los algoritmos de búsqueda local estocástica (SLS) se consideran del tipo Las Vegas [ cita requerida ] . Los algoritmos SLS se han utilizado para abordar problemas de decisión NP-completos y problemas de optimización combinatoria NP-difícil . [2] Sin embargo, algunos métodos de búsqueda sistemática, como las variantes modernas 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. [3]
Los algoritmos de Las Vegas fueron introducidos por László Babai en 1979, en el contexto del problema de isomorfismo de grafos , como un algoritmo dual de Monte Carlo . [4] Babai [5] 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.
// Algoritmo de Las Vegasrepetir : k = RandInt ( norte ) si A [ k ] == 1 , devolver k ; Como se mencionó anteriormente, los algoritmos de Las Vegas siempre arrojan resultados correctos. El código anterior ilustra esta propiedad. Una variable k se genera aleatoriamente; después de generar k , k se usa para indexar la matriz A. Si este índice contiene el valor 1, entonces 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 un tiempo arbitrario antes de que finalice el algoritmo.
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 [6]
Hay tres nociones de integridad para los algoritmos de Las Vegas:
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á completo exactamente si para cada x existe
algún t max tal que P(RT A,x ≤ t max ) = 1.
La exhaustividad aproximada es principalmente de interés teórico, ya que los plazos para encontrar soluciones suelen ser demasiado grandes para ser de utilidad práctica.
Los algoritmos de Las Vegas tienen diferentes criterios de evaluación según el planteamiento 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 temporal establecida. A continuación se muestran algunos posibles escenarios de aplicación:
(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 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) 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 .
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 inmediatamente, hasta tener "mala suerte" y dedicar grandes cantidades de tiempo. Una vez que se encuentra el sitio web correcto, no hay posibilidad de error. [7]
ENTRADA : # A es una matriz de n elementos def randomized_quicksort ( A ): si n == 1 : devuelve A # A está ordenado. de lo contrario : i = aleatorio . randrange ( 1 , n ) # Tomará un número aleatorio en el rango 1~n X = A [ i ] # El elemento pivote """Partición A en elementos < x, x y >x # como se muestra en la figura anterior . Ejecute Quicksort en A[1 a i-1] y A[i+1 a n]. Combine las respuestas para obtener una matriz ordenada.""" Un ejemplo simple es QuickSort aleatorio , donde el pivote se elige aleatoriamente y divide los elementos en tres particiones: elementos menores que el pivote, elementos iguales al pivote y elementos mayores que el pivote. El QuickSort aleatorio requiere muchos recursos, pero siempre genera la matriz ordenada como salida. [8]
Es obvio que QuickSort siempre genera la solución, que en este caso es 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 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 se desequilibrará, lo que dará como resultado una eficiencia de tiempo de ejecución deficiente. Sin embargo, si el valor de pivote está cerca del centro de la matriz, entonces la división estará razonablemente bien equilibrada, lo que producirá un tiempo de ejecución más rápido. 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 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 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 2 ), el tiempo de ejecución promedio es Θ ( n log n ). Resulta que lo peor de los casos no ocurre a menudo. 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 de uno entre n números, lo cual es muy raro. Sin embargo, sigue siendo el mismo tiempo de ejecución cuando la división es del 10% al 90% en lugar de del 50% al 50% porque la profundidad del árbol de recursividad seguirá siendo O (log n ) con O ( n ) veces tomadas en cada nivel de recursividad.
El problema de las ocho reinas suele resolverse con un algoritmo de retroceso. Sin embargo, se puede aplicar un algoritmo de Las Vegas; de hecho, es más eficiente que retroceder.
Coloca 8 reinas en un tablero de ajedrez para que ninguna ataque a otra. Recuerda que una reina ataca a otras piezas de la misma fila, columna y diagonales.
Supongamos que k filas, 0 ≤ k ≤ 8, están ocupadas con éxito por reinas.
Si k = 8, entonces deténgase con éxito. En caso contrario se procede a ocupar la fila k +1.
Calcule todas las posiciones en esta fila que no sean atacadas por reinas existentes. Si no hay ninguno, entonces fracasa. De lo contrario, elija uno al azar, incremente k y repita.
Tenga en cuenta que el algoritmo simplemente falla si no se puede colocar una reina. Pero el proceso se puede repetir y cada vez generará un arreglo diferente. [9]
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
lo cual 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 cuales existe un algoritmo de tiempo polinomial aleatorio que siempre responde correctamente cuando la respuesta correcta es "no", pero se le permite equivocarse con una cierta probabilidad limitada 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), los dos algoritmos se pueden ejecutar simultáneamente y repetidamente: ejecute cada uno durante un número constante de pasos, turná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 ejecute en el tiempo polinómico esperado. Tenga en cuenta que, en general, no existe un límite superior en el peor de los casos en el tiempo de ejecución de un algoritmo 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:
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 información sobre la distribución, ya que la mayoría de las veces, la respuesta solo se necesita una vez para cualquier x . [10]
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 probabilidad determinada (normalmente pequeña) . Un algoritmo de Las Vegas se puede convertir en un algoritmo de Monte Carlo ejecutándolo durante un tiempo determinado 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: [11]
Si se dispone de una forma determinista de comprobar 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 sencillo. Esto se puede hacer ejecutando un algoritmo de Las Vegas durante un período de tiempo específico determinado por el parámetro de confianza. Si el algoritmo encuentra la solución dentro del tiempo, entonces es un éxito y, si no, el resultado puede ser simplemente "lo siento".
Este es un ejemplo de algoritmos de Las Vegas y Monte Carlo para comparar: [12]
Supongamos que hay una matriz con una 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.
// Repetición del algoritmo de Las Vegas : k = RandInt ( n ) si A [ k ] == 1 , devuelve k ; //Algoritmo de Monte Carlo se repite 300 veces : k = RandInt ( n ) if A [ k ] == 1 return k return "Error" 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 veces de bucles hasta que realmente ejecute el código. Podría encontrar la solución o no. Por tanto, a diferencia de Las Vegas, Montecarlo no apuesta por el tiempo de ejecución sino por la corrección.