miniaturadeimagen|La imagen muestra una vista pictórica de múltiples ejecuciones de un algoritmo de Las Vegas. El algoritmo siempre termina con una solución, pero el tiempo de ejecución varía.|300px
Un algoritmo tipo Las Vegas es un procedimiento de computación de carácter aleatorio (random) que no es aproximado: es decir, da el resultado correcto o informa que ha fallado.
Características Un algoritmo de este tipo no especula con el resultado, sino que determina los recursos a utilizar en su computación.
De la misma manera que el método de Montecarlo, la probabilidad de encontrar una solución correcta aumenta con el tiempo empleado en obtenerla y el número de muestreos utilizado. Un algoritmo tipo Las Vegas se utiliza sobre todo en problemas NP-completos, que serían intratables con métodos determinísticos.
Existe un riesgo de no encontrar solución debido a que se hacen elecciones de rutas aleatorias que pueden no llevar a ningún sitio. El objetivo es minimizar la probabilidad de no encontrar la solución, tomando decisiones aleatorias con inteligencia, pero minimizando también el tiempo de ejecución al aplicarse sobre el espacio de información aleatoria.
La clase de complejidad de los problemas de decisión de estos algoritmos con ejecución polinómica es ZPP.
Su esquema de implementación se parece al de los algoritmos de Montecarlo, pero se diferencian de ellos en que incluyen una variable booleana para saber si se ha encontrado la solución correcta.
Visión general En informática, un algoritmo de Las Vegas es un algoritmo aleatorio que siempre da resultados correctos, es decir, que siempre produce el resultado correcto o informa acerca del fallo (es decir, que no se ha hallado la solución buscada). Sin embargo, el tiempo de ejecución de un algoritmo de Las Vegas difiere dependiendo de la entrada. Su definición usual 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, usada en el algoritmo. Una definición alternativa requiere que un algoritmo de Las Vegas siempre termine (porque se trata de un método efectivo), pero puede dar como resultado un símbolo que no forma parte del espacio de la solución, para indicar el fallo en encontrarla. 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 complejos, como algunas variantes del algoritmo de Davis-Putnam para la satisfacibilidad proposicional (SAT), también utilizan decisiones no deterministas y, por lo tanto, pueden considerarse algoritmos de Las Vegas.Hoos, Holger H.. “On the Empirical Evaluation of Las Vegas Algorithms — Position Paper.” (1998).
Historia Los algoritmos de Las Vegas fueron introducidos por László Babai en 1979, en el contexto del problema de isomorfismo de grafos, como un dual de los algoritmos del tipo del método de Monte Carlo.* László Babai, Monte-Carlo algorithms in graph isomorphism testing, Université de Montréal, D.M.S. No. 79-10. Leonid Levin, The Tale of One-way Functions, Problems of Information Transmission, vol. 39 (2003), 92-103. Dan Grundy, Concepts and Calculation in Cryptography , University of Kent, Ph.D. thesis, 2008 BabaiBabai, László. “Monte-Carlo algorithms in graph isomorphism testing.” (1979). introdujo el término "algoritmo de Las Vegas" junto con un ejemplo de 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 exactitud de cualquier resultado obtenido.
Ejemplo // Algoritmo de Las Vegas, suponiendo que A es una matriz de longitud n. n = A.length 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 generar k, k se utiliza para indexar la matriz A. Si este índice contiene el valor 1, se devuelve k; de lo contrario, el algoritmo repite este proceso hasta encontrar 1. Aunque este algoritmo de Las Vegas garantiza encontrar la respuesta correcta, no tiene un tiempo de ejecución fijo; debido a la aleatorización (en la línea 4 del código anterior), es posible que transcurra un tiempo arbitrario antes de que el algoritmo finalice.
Definición En esta sección se describen las condiciones que caracterizan a un algoritmo de tipo de Las Vegas.
Un algoritmo A es un algoritmo de Las Vegas para la clase de problema X, siH.H. Hoos and T. Stützle. Evaluating Las Vegas Algorithms — Pitfalls and Remedies. In Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence (UAI-98), pages 238–245. Morgan Kaufmann Publishers, San Francisco, CA, 1998.
Siempre que para una instancia dada del problema x∈X devuelva una solución s, se garantiza que s sea una solución válida de x En cada instancia dada x, el tiempo de ejecución de A es una variable aleatoria RTA,x
Existen tres nociones de completitud para los algoritmos de Las Vegas:
Se puede garantizar que los algoritmos de Las Vegas completos solucienen cada problema resoluble dentro del tiempo de ejecución tmax,, donde tmax es una constante dependiente de la instancia.
Sea P(RTA,x = t) la probabilidad de que A encuentre una solución para una instancia resoluble x en un tiempo t. Entonces, A es completo exactamente si para cada x existe algún tmax tal que P(RTA,x = tmax) = 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 acerca al infinito. Por lo tanto, A es aproximadamente completo si, para cada instancia x, limt→∞ P(RTA,x = t) = 1. Los algoritmos de Las Vegas esencialmente incompletos son aquellos que no son aproximadamente completos.
La completitud aproximada es principalmente de interés teórico, ya que los plazos para encontrar soluciones suelen ser demasiado largos para su uso práctico.
Escenarios de aplicación Los algoritmos de Las Vegas tienen diferentes criterios de evaluación según el 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 definida. 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 encontrar la solución. Tipo 2: Hay un límite de tiempo tmax para encontrar el resultado. Tipo 3: La utilidad de una solución está determinada 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. No ocurre lo mismo para el tipo 2.
Aquí, P(RT = tmax), 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 de tiempo de ejecución rtd: R → [0,1], definida como rtd(t) = P(RT = t) o su aproximación.
La distribución de 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, se pueden 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 Las Vegas surgen con frecuencia en problemas de búsqueda, como es el caso de alguien que busca una información en línea podría requerir la información deseada en sitios web relacionados. La complejidad temporal varía, por lo tanto, desde tener suerte y encontrar el contenido inmediatamente, hasta tener mala suerte y dedicar mucho tiempo hasta encontrarlo. Una vez encontrado el sitio web correcto, no hay posibilidad de error.Randomized Algorithms. Brilliant.org. Retrieved 23:54, October 24, 2018, from https://brilliant.org/wiki/randomized-algorithms-overview/
Ordenamiento rápido aleatorio INPUT: # A es una matriz de n elementos def randomized_quicksort(A): if n == 1: return A # A está ordenada else: i = random.randrange(1, n) # Will take a random number in the range 1~n X = A[i] # El elemento pivote """Repartir A en los elementos <x, x y >x #, como se muestra en la figura anterior. Ejecutar Quicksort en A[1 a i-1] y A[i+1 a n]. Combinar las respuestas para obtener una matriz ordenada."""
Un ejemplo sencillo es el 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 ordenamiento rápido siempre genera la solución, que en este caso es la matriz ordenada. Desafortunadamente, la complejidad temporal no es tan obvia. Resulta que el tiempo de ejecución depende del elemento que se elija como pivote.
El peor caso T(n2) se produce cuando el pivote es el elemento más pequeño o el más grande.
Sin embargo, mediante la aleatorización, donde el pivote se selecciona aleatoriamente y siempre tendrá un valor exactamente situado en la media, el QuickSort se puede realizar en T(nlogn).
El tiempo de ejecución del quicksort depende en gran medida de la precisión con la que se seleccione el pivote. Si un valor del pivote es demasiado grande o demasiado pequeño, la partición estará desequilibrada, lo que resulta en una baja eficiencia de ejecución. Sin embargo, si el valor del pivote está cerca del centro de la matriz, la división estará razonablemente equilibrada, lo que resulta en un tiempo de ejecución más rápido. Dado que el pivote se selecciona aleatoriamente, el tiempo de ejecución será bueno la mayor parte del tiempo y malo ocasionalmente.
En el caso del 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 del 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 T(n2), el tiempo de ejecución en el caso promedio es T(nlogn). Resulta que el peor de los casos no ocurre con frecuencia. Para valores grandes de n, el tiempo de ejecución es T(nlogn) con una alta probabilidad.
Obsérvese que la probabilidad de que el pivote sea el elemento de valor medio cada vez es de una entre n números, lo cual es muy poco común. 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(logn), con O(n) veces tomadas en cada nivel de recursión.
Algoritmo voraz aleatorio para el problema de las ocho reinas
El problema de las ocho reinas suele resolverse con un algoritmo de retroceso. Sin embargo, se puede aplicar un algoritmo de Las Vegas, y de hecho, es más eficiente que el algoritmo de retroceso.
Consiste en colocar 8 reinas en un tablero de ajedrez, de manera que ninguna ataque a otra. Debe recordarse que una reina ataca a otras piezas en la misma fila, columna y diagonales.
Supóngase que k filas, 0 ≤ k ≤ 8, están ocupadas con éxito por reinas.
Si k = 8, se detiene con éxito. De lo contrario, procede a ocupar la fila k + 1.