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:

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.

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.

En el siglo XVIII, Georges Louis Leclerc, conde de Buffon enunció el 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μ/wπ.

Aplicación:

Una aplicación del teorema de Buffon es utilizarlo para predecir el valor de π. Sea μ=w/2, entonces p=1/π. 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.

En la práctica, no es un algoritmo útil, porque se pueden obtener aproximaciones de π mucho mejores empleando métodos deterministas. A pesar de esto, esta aproximación fue muy utilizada en el siglo XIX, haciendo de este uno de los primeros algoritmos probabilistas que se utilizaron.

El algoritmo probabilista numérico más conocido es la integración de Monte Carlo. Cabe destacar que a pesar de su nombre, no es un algoritmo probabilista de Monte Carlo.

El algoritmo de Monte Carlo puede ser representado por el siguiente pseudocódigo, en donde se integra la función f entre a y b utilizando n iteraciones.

La varianza de la estimación calculada mediante este algoritmo es inversamente proporcional al número de puntos de la muestra. El error esperado en la estimación es inversamente proporcional a la raíz cuadrada de n, de forma que se requieren 100 iteraciones más para obtener un dígito adicional de precisión.

En general, se pueden obtener estimaciones de integrales mediante métodos deterministas con mayor precisión y con menos iteraciones. Sin embargo, a todo algoritmo determinista de integración, incluso a los más complejos, le corresponden funciones continuas diseñadas expresamente para engañar al algoritmo. Esto no ocurre con el método de Monte Carlo, aunque existe una probabilidad pequeña de que el algoritmo pudiera cometer un error similar aun cuando integre una función completamente común.

La aplicación de la integración de Monte Carlo tiene más sentido cuando se tiene que evaluar una integral múltiple, ya que la dimensión de la integral suele tener poco efecto sobre la precisión obtenida, aunque la cantidad de trabajo aumente con la dimensión. En la práctica, se utiliza para evaluar integrales de dimensiones mayores que tres ya que no hay otra técnica que sea competitiva. Se puede mejorar la precisión de las respuestas empleando técnicas híbridas.

Hay problemas para los que no se conoce ningún algoritmo eficiente (determinista o probabilista) que de siempre una solución correcta en todas las ocasiones. Los algoritmos de Monte Carlo cometen ocasionalmente un error, pero encuentran la solución correcta con una probabilidad alta sea cual sea el caso considerado. Al contrario de los algoritmos de Las Vegas, no suele darse ningún aviso cuando el algoritmo comete un error. Una característica importante es que suele ser posible reducir arbitrariamente la probabilidad de error a costa de un aumento del tiempo de cálculo.

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

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

La historia de la comprobación probabilista de primalidad tiene sus raíces en Pierre Fermat, quien postuló en 1640 el Pequeño teorema de Fermat

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

El algoritmo se basa en el enunciado del contrarrecíproco del mismo teorema

Fermat formuló la hipótesis: F_n = 2⁽²ⁿ⁾+ 1 es primo para todo n y lo comprobó para: F₀=3, F₁=5, F₂=17, F₃=257, F₄=65537. Lamentablemente, no pudo comprobar F₅ ya que era un número demasiado grande. Tuvo que pasar casi un siglo para que Euler demostrara que no es primo.

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≤F₅-1 tal que a^{(F₅ - 1)} mod F₅ <> 1) (a=3). Con estas premisas, se puede desarrollar el siguiente algoritmo:

Sabemos que n es compuesto cuando la función devuelve el valor falso, por el teorema de Fermat. Cabe destacar que cuando el algoritmo establece que el número es compuesto, no ofrece información de sus divisores. En cambio, cuando el algoritmo devuelve el valor verdadero no podemos afirmar que n sea primo. Necesitaríamos el recíproco y el contrapositivo del teorema de Fermat.

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

Hay dos tipos de algoritmos de Las Vegas, según la posibilidad de no encontrar 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 O(n²) y coste promedio Ω(n log(n)).

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

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

Consideraciones sobre el coste:

Ahora repetimos el algoritmo anterior para ganar en eficacia:

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