La característica principal de los algoritmos probabilistas es que un mismo algoritmo se
puede comportar de forma distinta cuando se aplica dos veces a un mismo caso. Su
tiempo de ejecución e incluso el resultado obtenido, pueden variar considerablemente
entre usos consecutivos. Esto se puede explorar de muchas maneras. Por ejemplo, no se
permite que un algoritmo determinista pierda el control(bucle infinito, división por cero)
porque si hace esto en un caso dado, entonces nunca se podrá resolver ese caso con ese
algoritmo.
Por contraste, este comportamiento es admisible para un algoritmo
probabilístico siempre y cuando se produzca una probabilidad razonablemente pequeña
en cualquier caso dado: si el algoritmo se atasca, basta con reiniciarlo para ese mismo
caso y dispondremos de una nueva probabilidad de éxito. Otra ventaja de este enfoque es
que si hay más de una respuesta correcta, se pueden obtener varias diferentes ejecutando
el algoritmo probabilista más de una vez.
Hay muchos algoritmos probabilísticos que dan respuestas probabilistas, esto es, que no
son necesariamente exactas. Hay aplicaciones críticas para las cuales no se pueden admitir
esas respuestas inciertas. Sin embargo, es frecuente que la probabilidad de error se pueda
hacer descender por debajo de la de un error del equipo físico durante el
significativamente mayor tiempo que el necesario para calcular la respuesta de forma
determinista. Por tanto, paradójicamente, puede suceder que la respuesta incierta dada
por un algoritmo probabilista no sólo se obtenga más deprisa, sino que además podamos
confiar más en ella que la respuesta “garantizada” que se obtiene mediante ningún
algoritmo(determinista o probabilista) que se pueda dar la respuesta con certeza en una
cantidad razonable de tiempo(incluso ignorando posibles errores del equipo físico), y sin
embargo hay algoritmos probabilísticos que pueden resolver rápidamente el problema si
se admite una pequeña probabilidad de error.
Se pueden distinguir fundamentalmente cuatro grandes categorías:
Algoritmos numéricos
Devuelven una aproximación al resultado, frecuentemente en forma de intervalo. Son
útiles cuando la solución exacta es demasiado costosa (o directamente imposible de
calcular, como por ejemplo, para números irracionales) y una aproximación es lo
suficientemente buena. Considérese que se desea calcular el resultado de una complicada
integral de varias dimensiones. Tal vez sólo se necesite una precisión de cuatro decimales,
aunque la solución exacta conste de varias decenas de los mismos. Este tipo de algoritmos
suelen ofrecer resultados más precisos cuanto mayor tiempo se dedica a su cálculo.El
margen de error suele ser inversamente proporcional a la raíz cuadrada de la cantidad de
trabajo que se haya efectuado, así que se necesita cien veces más trabajo para obtener un
dígito de precisión adicional
Algoritmos de Montecarlo
Existen problemas para los cuales no se conoce ningún algoritmo eficiente(probabilista o
determinista) que sea capaz de obtener una solución correcta en todas las ocasiones. Los
algoritmos Monte Carlo ocasionalmente cometen un error, pero siempre devuelven una
solución aunque esta a veces no sea correcta. Son útiles cuando una aproximación no es
suficiente (por ejemplo, en un problema de decisión). Cuentan con el inconveniente de no
saber con exactitud si la respuesta es acertada, pues sólo existe una cierta probabilidad de
éxito. Cuantas más veces se ejecute, más seguro se estará de la corrección de la solución.
Algoritmos de Las Vegas
Los algoritmos de las vegas toman decisiones probabilistas como ayuda para guiarse más
rápidamente hacia una solución correcta. Similares a los de Montecarlo pero que nunca
devuelven una solución errónea, con el inconveniente de que pueden no terminar o
devolver solución. Esto garantiza que la respuesta sea la buena, pero no garantiza que el
algoritmo funcione. Como en los casos anteriores, cuanto mayor es el tiempo dedicado al
cálculo, más fiable es la solución. No debe confundirse este tipo de algoritmos con aquellos
deterministas, como el simplex en programación lineal, que son muy eficientes para la
mayoría de los posibles datos de entrada pero desastrosos para unos pocos. Nótese que
dichos algoritmos siempre devuelven una solución correcta.
Algoritmos de Sherwood
Devuelven siempre una respuesta, la cual es forzosamente exacta. Aparecen cuando un
algoritmo determinista conocido es más rápido en el caso medio que en el peor. El uso del
azar permite reducir, e incluso eliminar, la diferencia entre buenos y malos ejemplares.
Referencias
Brassard, G., & Bratley, P. (2000). Fundamentos de Algoritmia. Prentice Hall.
EcuRed. (2010). Algoritmos probabilísticos - EcuRed.
https://www.ecured.cu/Algoritmos_probabil%C3%ADsticos.