En algorítmica , un algoritmo de Monte-Carlo es un algoritmo aleatorio cuyo tiempo de ejecución es determinista, pero cuyo resultado puede ser incorrecto con una cierta probabilidad (generalmente mínima). En otras palabras, un algoritmo de Monte-Carlo es un algoritmo que utiliza una fuente de azar, cuyo tiempo de cálculo se conoce desde el principio (no sorprende la duración del cálculo), sin embargo, el resultado del cual puede no ser el respuesta al problema planteado, pero este es un caso muy raro. La ventaja de estos algoritmos es que tienen una baja probabilidad de falla y son rápidos.
Otros dos tipos de algoritmos probabilísticos son la familia de algoritmos de Las Vegas y la familia de algoritmos Atlantic City (en) . Los algoritmos de Las Vegas toman un tiempo de ejecución aleatorio, pero aún producen una respuesta correcta. Los algoritmos de Atlantic City dan una respuesta probablemente correcta en un tiempo de respuesta probablemente rápido. Un algoritmo de Monte-Carlo se puede transformar en un algoritmo de Las Vegas cuando existe un procedimiento capaz de verificar la exactitud del resultado. De hecho, basta con ejecutar el algoritmo de Monte-Carlo hasta que produzca una respuesta correcta.
Por cierto, el calificador Monte-Carlo se refiere al Principado de Mónaco y su famoso casino llamado Casino de Monte-Carlo , una meca para los juegos de azar.
Un algoritmo de Monte-Carlo tiene dos características: primero, es aleatorio , es decir, utiliza un peligro durante su cálculo, segundo, su tiempo de ejecución es determinista. Su naturaleza aleatoria se manifiesta en su resultado que puede ser incorrecto con cierta probabilidad (generalmente mínima), pero que puede cuantificarse rigurosamente.
La prueba de primalidad de Solovay-Strassen es una prueba que determina si un número dado es primo . Siempre responde verdadero para números primos, mientras que para números compuestos (es decir, no primos) responde falso con una probabilidad de al menos ½ y verdadero con una probabilidad de al menos ½. Por tanto, las respuestas falsas del algoritmo son correctas, mientras que las respuestas verdaderas son aleatorias; en otras palabras, el algoritmo está sesgado hacia lo falso.
Si bien la respuesta devuelta por un algoritmo determinista siempre es correcta, este no es el caso de los algoritmos de Monte-Carlo que solo pueden ser correctos en el caso de un sesgo. Supongamos que se trata de resolver un problema de decisión, entonces se dice que estos algoritmos son no sesgados, o sesgados hacia lo falso, o sesgados hacia lo verdadero. Un algoritmo de Monte-Carlo con sesgo falso siempre es correcto cuando devuelve falso ; un algoritmo sesgado hacia verdadero siempre es correcto cuando devuelve verdadero . En cuanto a los algoritmos de Monte-Carlo insesgados, su respuesta (verdadera o falsa) será incorrecta o correcta con una cierta probabilidad acotada.
En inglés, hablamos de error unilateral y error bilateral .
Dado un algoritmo de Monte Carlo sesgado, su probabilidad de falla se puede reducir (y su probabilidad de éxito aumentar) realizándolo k veces. Considere nuevamente el algoritmo Solovay-Strassen que está sesgado hacia lo falso. Podemos ejecutarlo varias veces para que devuelva verdadero si responde verdadero durante los k pasos de la iteración y falso en caso contrario. Entonces, si el número es primo, entonces la respuesta es realmente correcta, y si el número es compuesto, entonces la respuesta es correcta, con una probabilidad mejorada de al menos 1− (1 - ½) k = 1−2 −k .
Para los algoritmos de decisión de Monte Carlo insesgados, la probabilidad de error también se puede reducir ejecutando el algoritmo k veces y devolviendo la respuesta que coincida con la mayoría.
La clase de complejidad BPP ( tiempo polinomial probabilístico de error acotado ) describe problemas de decisión que pueden resolverse mediante un algoritmo de Monte-Carlo insesgado en tiempo polinomial, con una probabilidad de error acotada.
La clase de complejidad RP (para tiempo polinomial aleatorio ) describe los problemas que pueden resolverse con una probabilidad limitada de error mediante un algoritmo de Monte-Carlo sesgado: si la respuesta correcta es falsa , el algoritmo lo dice, pero puede responder falsa en algunos casos. donde la respuesta correcta es verdadera .
Por otro lado, la clase de complejidad ZPP (para tiempo polinomial probabilístico de error cero ) describe problemas solucionables en tiempo polinomial mediante un algoritmo de Las Vegas. Tenemos ZPP ⊆ RP ⊆ BPP, pero no sabemos si estas clases de complejidad son mutuamente distintas. En otras palabras, los algoritmos Monte-Carlo pueden tener un mejor rendimiento que los algoritmos de Las Vegas, pero esto no se ha demostrado.
Otra clase de complejidad es PP (para polinomio probabilístico ); describe los problemas de decisión resueltos en tiempo polinomial por un algoritmo de Monte-Carlo que da un resultado más preciso que un simple lanzamiento de moneda, pero cuya probabilidad de error no puede reducirse significativamente por debajo de ½.
Los algoritmos de Monte-Carlo notables incluyen la prueba de primalidad de Solovay-Strassen y la prueba de primordialidad de Miller-Rabin , y algunas variaciones rápidas del algoritmo de Schreier-Sims en la teoría de grupos computacional .
Resolviendo el viajar vendedor problema es difícil, debido a la complejidad del problema, el uso de probabilísticas de optimización de métodos puede ser eficaz en la obtención de una aproximación de la mejor solución, en un tiempo más corto que para los métodos deterministas.
Corte mínimoEl algoritmo de Karger es un algoritmo de Monte Carlo para el problema del corte mínimo .