Algoritmo probabilista

Un algoritmo probabilista (o probabilístico) es un algoritmo que basa su resultado en la toma de algunas decisiones al azar, de tal forma que, en promedio, obtiene una buena solución al problema planteado para cualquier distribución de los datos de entrada. Es decir, al contrario que un algoritmo determinista, a partir de unos mismos datos se pueden obtener distintas soluciones y, en algunos casos, soluciones erróneas.

Existen varios tipos de algoritmos probabilísticos dependiendo de su funcionamiento, pudiéndose distinguir:

• Algoritmos numéricos, que proporcionan una solución aproximada del problema.
• Algoritmos de Montecarlo, que pueden dar la respuesta correcta o respuesta erróneas (con probabilidad baja).
• Algoritmos de Las Vegas, que nunca dan una respuesta incorrecta: o bien dan la respuesta correcta o informan del fallo.

Consideraciones

Se puede optar por la elección aleatoria si se tiene un problema cuya elección óptima es demasiado costosa frente a la decisión aleatoria. Un algoritmo probabilista puede comportarse de distinta forma aplicando la misma entrada.

• A un algoritmo determinista nunca se le permite que no termine: hacer una división por 0, entrar en un bucle infinito, etc.
• Si existe más de una solución para unos datos dados, un algoritmo determinista siempre encuentra la misma solución (a no ser que se programe para encontrar varias o todas).
• Un algoritmo probabilista puede encontrar soluciones diferentes ejecutándose varias veces con los mismos datos.
• A un algoritmo determinista no se le permite que calcule una solución incorrecta para ningún dato.
• Un algoritmo probabilista puede equivocarse siempre que esto ocurra con una probabilidad pequeña para cada dato de entrada.
• Repitiendo la ejecución un número suficiente de veces para el mismo dato, puede aumentarse tanto como se quiera el grado de confianza en obtener la solución correcta.
• El análisis de la eficiencia de un algoritmo determinista es, en determinadas ocasiones, difícil.
• El análisis de los algoritmos probabilistas es, a menudo, muy difícil.

Algoritmos numéricos

La solución obtenida es siempre aproximada pero su precisión esperada mejora aumentando el tiempo de ejecución. Normalmente, el error es inversamente proporcional a la raíz cuadrada del esfuerzo invertido en el cálculo.

Ejemplo: La aguja de Buffon

Teorema de Buffon: si se tira una aguja de longitud μ a un suelo hecho con tiras de madera de anchura w (w>=μ), la probabilidad de que la aguja toque más de una tira de madera es p=2μ/wp.

Aplicación:

• Si μ=w/2, entonces p=1/p.
• Si se tira la aguja un número de veces n suficientemente grande y se cuenta el número k de veces que la aguja toca más de una tira de madera, se puede estimar el valor de p: k ~ n/p → p ~ n/k

• Es (probablemente) el primer algoritmo probabilista de la historia.

¿Es útil este método?

• ¿Cómo de rápida es la convergencia? → ¿cuántas veces hay que tirar la aguja?

Muy lenta: n=1500000 para obtener un valor de p±0’01 con probabilidad 0’9.

Algoritmos de Montecarlo

Hay problemas para los que no se conocen soluciones deterministas ni probabilistas que den siempre una solución correcta(ni siquiera una solución aproximada).

Algoritmo de Montecarlo:

• A veces da una solución incorrecta.
• Con una alta probabilidad encuentra una solución correcta sea cual sea la entrada.

Definición: Sea p un número real tal que 0.5<p<1.Un algoritmo de Montecarlo es p–correcto si:

• Devuelve una solución correcta con probabilidad mayor o igual que p, cualesquiera que sean los datos de entrada.
• A veces, p dependerá del tamaño de la entrada, pero nunca de los datos de la entrada en sí.

Un ejemplo de algoritmo de Montecarlo (el más conocido): decidir si un número impar es primo o compuesto.

• Ningún algoritmo determinista conocido puede responder en un tiempo “razonable” si el número tiene cientos de cifras.

• La utilización de primos de cientos de cifras es fundamental en criptografía

Pierre Fermat postuló en 1640 el Pequeño teorema de Fermat: Sea n primo. Entonces, a^(n-1) mod n <> 1 para todo entero a tal que 1<=a<=n-1.

Ejemplo: n = 7, a = 5 → 5^6 mod 7 = 1.

Enunciado contrarrecíproco del mismo teorema: si a y n son enteros tales que 1<=a<=n-1, y si a^(n-1) mod n <> 1, entonces n no es primo.

Fermat formuló la hipótesis: "Fn = 2^(2^n)+ 1 es primo para todo n"

• Lo comprobó para: F0=3, F1=5, F2=17, F3=257, F4=65537.
• Pero no pudo comprobar si F5=4294967297 lo era.

Utilización del pequeño teorema de Fermat para comprobar la primalidad: en el caso de F5, a Fermat le hubiera bastado con ver que existe un 'a' tal que 1<=a<=F5-1 tal que a^(F5 - 1) mod F5 <> 1) (a=3). Con estas premisas, se puede desarrollar el siguiente algoritmo:

función .(n:.) . booleano 
variable a:.
principio 
  a:=._.(.,n-.); 
  si an-. mod n=. 
     entonces devuelve . 
     sino devuelve . 
  fsi 
fin

Estudio del algoritmo basado en el pequeño teorema de punto:

• Si devuelve el valor ., es seguro que . (por el teorema de punto).

Algoritmos de Las Vegas

Un algoritmo de Las Vegas nunca da una solución falsa.

• Toma decisiones al azar para encontrar una solución antes que un algoritmo determinista.
• Si no encuentra solución lo admite.

Hay dos tipos de algoritmos de Las Vegas, según la posibilidad de no encontrar una solución:

• Los que siempre encuentran una solución correcta, aunque las decisiones al azar no sean afortunadas y la eficiencia disminuya.

• Los que a veces, debido a decisiones desafortunadas, no encuentran una solución.

Tipo a: Algoritmos de Sherwood

Existe una solución determinista que es mucho más rápida en media que en el peor caso.

Ejemplo: quicksort.

Coste peor Ω(n^2) y coste promedio O(nlog n).

• Coste promedio: se calcula bajo la hipótesis de equiprobabilidad de la entrada.
• En aplicaciones concretas, la equiprobabilidad es falsa: entradas catastróficas pueden ser muy frecuentes.
• Degradación del rendimiento en la práctica.

Los algoritmos de Sherwood pueden reducir o eliminar la diferencia de eficiencia para distintos datos de entrada:

• Uniformización del tiempo de ejecución para todas las entradas de igual tamaño.
• En promedio (tomado sobre todos los ejemplares de igual tamaño) no se mejora el coste.
• Con alta probabilidad, ejemplares que eran muy costosos (con algoritmo determinista) ahora se resuelven mucho más rápido.
• Otros ejemplares para los que el algoritmo determinista era muy eficiente, se resuelven ahora con más coste.

Tipo b: Algoritmos que, a veces, no dan respuesta.

• Son aceptables si fallan con probabilidad baja.
• Si fallan, se vuelven a ejecutar con la misma entrada.
• Resuelven problemas para los que no se conocen algoritmos deterministas eficientes(ejemplo: la factorización de enteros grandes).
• El tiempo de ejecución no está acotado pero sí es razonable con la probabilidad deseada para toda entrada.

Consideraciones sobre el coste:

• Sea LV un algoritmo de Las Vegas que puede fallar y sea p(x) la probabilidad de éxito si la entrada es x.

algoritmo LV(ent x:tpx; sal s:tpsolución; 
             sal éxito:booleano) 
{éxito devuelve . si LV encuentra la solución 
y en ese caso s devuelve la solución encontrada}

• Se exige que p(x)>0 para todo x.
• Es mejor aún si existe d>0: p(x)>=d para todo x (así, la probabilidad de éxito no tiende a 0 con el tamaño de la entrada).

Ahora repetimos el algoritmo anterior para ganar en eficacia:

función repe_LV(x:tpx) devuelve tpsolución 
variables s:tpsolución; éxito:booleano 
principio 
   repetir 
      LV(x,s,éxito) 
   hastaQue éxito; 
   devuelve s 
fin

• El número de ejecuciones del bucle es ./p(x).
• Sea v(x) el tiempo esperado de ejecución de LV si éxito=. y f(x) el tiempo esperado si éxito=.
• el tiempo esperado de repe_LV() = v(x) + ((. - p(x))/ p(x)) f(x).

Ejemplo: El problema de todos los . en el tablero de go.

• Algoritmo determinista: Nº de nodos visitados: . de los . nodos del árbol)
• Algoritmo de Las Vegas voraz: colocar cada . aleatoriamente en uno de los escapes posibles de la siguiente fila. El algoritmo solo puede terminar con éxito (pues siempre hay forma de colocar el siguiente .).Nº de nodos visitados para éxito: v=., Probabilidad de éxito: p=. (más de . vez de cada .)

• Número esperado de nodos visitados repitiendo hasta obtener un éxito: t=v+f(.-p)/p=., menos de .

Enlaces externos

Wikilibros

• Wikilibros alberga un libro o manual sobre Algoritmos probabilísticos (Algoritmia).