Algoritmos Probabilisticos

ALGORITMOS PROBABILISTICOS

Introducción

Imagine que usted es el héroe de un cuento de hadas. Hay un tesoro oculto en un lugar que se describe en un mapa que no consigue descifrar. Se las ha arreglado para reducir la búsqueda a dos posibles escondites, que sin embargo distan bastante entre si. Si estuviera en uno de estos dos lugares, sabría de inmediato si es o no el correcto. Se necesitancinco días para ir a cualquiera de los dos lugares, o para viajar desde uno hasta otro. Y el problema se complica más, porque hay un dragón que visita el tesoro todas las noches, y se lleva una parte a un inaccesible cubil en las montañas. Piensa usted que se .necesitarán cuatro días de cálculo para resolver el misterio del mapa, y por tanto para saber con certeza dónde está oculto el tesoro, perosi se pone en marcha ya no podrá utilizar una computadora. Un elfo le ofrece mostrarle la forma de descifrar el mapa a cambio del equivalente del tesoro que se lleva el dragón en tres noches. ¿Debe de aceptar la oferta del elfo?
Evidentemente, es preferible dar el valor de tres noches de tesoro al elfo frente a permitir que el dragón se dedique al pillaje cuatro noches más. Sin embargo, si estádispuesto a correr un riesgo calculado, puede hacerlo mejor. Supongamos que es x el valor del tesoro que queda hoy, y que y es el valor del tesoro que se lleva el dragón todas las noches. Supongamos además que es x > 9y. Recordando que necesitará cinco días para alcanzar el escondite, puede esperar volver a casa con x-9y si espera cuatro días para acabar de descifrar el mapa. Si acepta la ofertadel elfo, puede partir inmediatamente y volver con x - 5y de lo cual 3y servirá para pagar al elfo; entonces le quedará x-8y. Una estrategia mejor consiste en tirar una moneda al aire para decidir cuál de los dos escondites va a visitar primero, viajando hasta el otro si se ha equivocado. Esto le da una oportunidad de entre dos de volver a casa con x - 5y, y una oportunidad de entre dos de volver acasa con x - 10y. Por tanto, el beneficio esperado es x – 7,5y.
Esta fábula se puede traducir al contexto de la algoritmia en la forma siguiente: cuando un algoritmo se enfrenta a una decisión, a veces es preferible seguir un curso de acción aleatorio, en lugar de invertir tiempo en determinar cuál de las alternativas es la mejor. Esta situación se produce cuando el tiempo necesario paradeterminar la opción óptima es prohibitivo en comparación con el tiempo que se ahorra de análisis en el caso medio al tomar esta decisión óptima.
La característica fundamental 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 considerablementeentre usos consecutivos. Esto se puede explotar 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 probabilista siempre y cuando se produzca con unaprobabilidad razonablemente pequeña en cualquier caso dado; si el algoritmo se atasca, basta reiniciarlo para ese mismo caso y dispondremos de una nueva oportunidad 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; un algoritmo determinista siempre llega a la misma respuesta, aunquepor supuesto se puede programar para buscar varias.



Otra consecuencia del hecho de que los algoritmos probabilistas se pueden comportar de forma distinta cuando se ejecutan dos veces con las mismas entradas es que algunas veces les permitiremos que produzcan resultados erróneos. Supuesto que esto suceda con probabilidad suficientemente pequeña en cualquier caso dado, basta invocar el...