Existen problemas en los cuales su solución involucra algoritmos en los que aparece una decisión, es preferible a veces elegir aleatoriamente una de las posibles alternativas antes que perder tiempo calculando cuál de ellas es la mejor. Esta situación se produce si el tiempo requerido para determinar la alternativa optima es demasiado largo frente al promedio obtenido tomando la decisión al azar.
Algoritmos probabilísticos
Figura 1: Ejemplo de algoritmo probabilístico para optimizar soluciones complejas
Los algoritmos probabilísticos, son algoritmos que utilizan la aleatoriedad con el fin de tomar decisiones al azar, en ocasiones el resultado de estos es incorrecto, es decir son algoritmos que ofrecen un margen de probabilidad como resultado, de modo que no hay total certeza de su precisión. Este tipo de algoritmo se divide en tres tipos según su porcentaje de acierto: numéricos, Montecarlo y Las Vegas.
En estos casos es en los cuales se implementan los algoritmos probabilísticos. A este tipo de algoritmo se le permite que en alguna ejecución devuelva un resultado incorrecto, o cicle indefinidamente, siempre y cuando lo haga con una probabilidad baja.
Algoritmo probabilístico
Es un algoritmo que contiene entre sus operaciones elementales la generación de números aleatorios y su principal característica es que el mismo algoritmo aplicado a la misma instancia usando los mismos datos varias veces puede dar distintos resultados, por lo tanto, podría necesitar distinta cantidad de tiempo y espacio.
A este tipo de algoritmo se le puede permitir calcular una solución equivocada, con una probabilidad pequeña y en muchos casos se puede aumentar la confianza en el resultado ejecutando el algoritmo varias veces.
Clasificación de los algoritmos probabilísticos
Algoritmos Numéricos:
Este tipo de algoritmos proporciona una solución aproximada, con un intervalo de confianza del 90%, su precisión esperada mejora aumentando el tiempo de ejecución. Son muy útiles si nos basta con una respuesta aproximada.
Ejemplos: La aguja de Buffon y la integración numérica
Algoritmos de Monte Carlo:
Este algoritmo posee una respuesta exacta con una probabilidad alta. Pero también puede producir respuestas incorrectas.
Además, no se puede saber si la respuesta producida es correcta o no, pero entre más tiempo de ejecución existe menor probabilidad de error tendremos.
Ejemplo: verificación de la multiplicación de matrices
Algoritmos de Las Vegas:
Estos algoritmos toman decisiones probabilísticas como ayuda para guiarse a la solución correcta, por ende, nunca proporcionan una respuesta incorrecta.
Verifican que la solución encontrada sea correcta sino es correcta lo admiten. Es posible volver a ejecutar el algoritmo con los mismos datos hasta obtener la solución correcta, ya que entre más ejecuciones existe mayor probabilidad de encontrar la solución.
Ejemplos: El problema de las ocho reinas y factorización de enteros muy grandes.
Existen 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.
Ejemplo de comportamiento de los distintos tipos de algoritmos probabilísticos
Problema: “¿Cuándo descubrió América Cristóbal Colón?”
Figura 2: Ejemplo del comportamiento de los tipos de algoritmos
- 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.”
Aparentemente, la probabilidad de dar un intervalo erróneo es del 20% (1 de cada 5). 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.
Igual que el anterior se obtuvo 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, ¡Perdón!, 1492, 1492, 1492, 1492, 1492, ¡Perdón!, 1492.
El algoritmo nunca da una respuesta incorrecta, sin embargo, el algoritmo falla con una cierta probabilidad (20% en este caso).
Bibliografía
Brassard, G. and Bratley, P., 2008. Fundamentos De Algoritmia. Madrid: Pearson Prentice Hall.
Cs.uns.edu.ar. 2017. [online] Disponible en: http://www.cs.uns.edu.ar/~prf/teaching/AyC17/downloads/Teoria/AlgoritmosProbabilisticos-1x1.pdf
studylib.es. 2020. Algoritmos Probabilistas. [online] Disponible en: https://studylib.es/doc/2142/algoritmos-probabilistas
Webdiis.unizar.es.2020. [online] Disponible en: https://webdiis.unizar.es/asignaturas/EDA/ea/slides/8-Algoritmos%20probabilistas.pdf