Algoritmos Probabilistas
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.
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 no encuentran la respuesta correcta e informan del fallo..
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.
Algoritmos probabilistas vs deterministas
A un algoritmo determinista nunca se le permite que no
termine: hacer una división por 0, entrar en un bucle infinito,
etc.
A un algoritmo probabilista se le puede permitir siempre que
eso ocurra con una probabiliad muy pequeña para datos
cualesquiera. Si ocurre, se aborta el algoritmo y se repite su
ejecución con los mismos datos.
Un algoritmo probabilista puede equivocarse pero
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.
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.
El análisis de la eficiencia de un algoritmo determinista es, a
veces, difícil.
El análisis de los algoritmos probabilistas es, muy muy difícil
A un algoritmo probabilista se le puede permitir calcular una
solución equivocada, con una probabilidad pequeña.
Un algoritmo determinista que tarde mucho tiempo en
obtener la solución puede sufrir errores provocados por
fallos del hardware y obtener una solución equivocada. Es
decir, el algoritmo determinista tampoco garantiza siempre la
certeza de la solución y además es más lento.
Es mejor un algoritmo probabilista rápido que dé la solución
correcta con una cierta probabilidad de error. P.g. decidir si
un nº de 1000 cifras es primo.
Ejemplo. Aguja de Buffon
La aguja de Buffon es un clásico problema de probabilidad geométrica, de
realización práctica y cuyo interés radica en que es un método difícil para
ir aproximando el valor del número π a partir de sucesivos intentos. Fue
planteado por el naturalista francés Buffon en 1733 y reproducido por él
mismo ya resuelto en 1757 . Se trata de lanzar una aguja sobre un papel
en el que se han trazado rectas paralelas distanciadas entre sí de manera
uniforme. Se puede demostrar que si la distancia entre las rectas es igual
a la longitud de la aguja, la probabilidad de que la aguja cruce alguna de
las líneas es
2 /𝜋
.
De esa manera 𝜋 =
2𝑁 /𝐴
siendo N el número total de intentos y A el
número de veces que la aguja ha cruzado alguna línea.
Clasificación de los algoritmos probabilistas
Existen varios tipos de algoritmos probabilísticos
dependiendo de su funcionamiento, pudiéndose
distinguir:
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 no encuentran la respuesta correcta e informan del fallo..
Por ejemplo si tenemos la pregunta ¿Cuándo descubrió América Cristóbal Colón?
Respuesta correcta 1492
Algoritmo numérico ejecutado cinco veces:
- “Entre 1490 y 1500.”
- “Entre 1485 y 1495.”
- “Entre 1491 y 1501.”
- “Entre 1480 y 1490.”
- “Entre 1489 y 1499.”
Dando más tiempo a la ejecución se podría reducir esa probabilidad
o reducir la anchura del intervalo (a menos de 11 años).
Algoritmo de Monte Carlo ejecutado diez veces:
1492, 1492, 1492, 1491, 1492, 1492, 357 A.C., 1492, 1492,
1492.
De nuevo un 20% de error. Este porcentaje puede reducirse dando
más tiempo para la ejecución.
Las respuestas incorrectas pueden ser próximas a la correcta o
completamente desviadas.
Algoritmo de Las Vegas ejecutado diez veces:
1492, 1492, ¡Error!, 1492, 1492, 1492, 1492, 1492, ¡Error!,
1492.
El algoritmo nunca da una respuesta incorrecta
El algoritmo falla con una cierta probabilidad (20% en este caso).
Ejemplo de algoritmo numérico
Ejemplo de algoritmo Monte Carlo
Ejemplo de algoritmo Las Vegas
Comentarios
Publicar un comentario