Algoritmos Aleatorizados y de Aproximación
Los algoritmos aleatorizados y de aproximación sacrifican la exactitud o el determinismo por la eficiencia: los algoritmos aleatorizados utilizan elecciones al azar para ganar velocidad o simplicidad, mientras que los algoritmos de aproximación encuentran soluciones demostrablemente casi óptimas para problemas demasiado difíciles de resolver exactamente.
Definition
Los algoritmos aleatorizados toman decisiones al azar durante la ejecución y se analizan en cuanto al tiempo de ejecución esperado o la probabilidad de corrección; los algoritmos de aproximación se ejecutan de manera eficiente y devuelven soluciones garantizadas de estar dentro de un factor probado del óptimo para problemas de optimización difíciles.
Scope
Esta área abarca algoritmos que relajan el objetivo de una respuesta exacta y determinista. Incluye algoritmos aleatorizados (Las Vegas y Monte Carlo), con sus garantías probabilísticas; algoritmos de aproximación para optimización NP-difícil con razones de aproximación probadas; y algoritmos en línea que deben decidir sin conocer el futuro, analizados por su razón competitiva. Estas son las respuestas estándar a la intratabilidad y a los entornos con incertidumbre, basándose en el análisis de complejidad y los paradigmas de diseño.
Sub-topics
Core questions
- ¿Cómo mejora la aleatorización el tiempo de ejecución, la simplicidad o la robustez?
- ¿Cuál es la diferencia entre las garantías de Las Vegas y Monte Carlo?
- ¿Cómo se cuantifica la calidad de un algoritmo de aproximación mediante una razón de aproximación?
- ¿Qué problemas NP-difíciles admiten buenas aproximaciones y cuáles se resisten a ellas?
- ¿Cómo se evalúan competitivamente las decisiones en línea, tomadas sin información futura?
Key concepts
- algoritmos aleatorizados
- Las Vegas y Monte Carlo
- tiempo de ejecución esperado
- desigualdades de concentración
- razón de aproximación
- esquema de aproximación en tiempo polinomial
- algoritmos en línea
- razón competitiva
Key theories
- Aleatorización para la eficiencia
- Las elecciones aleatorias pueden producir algoritmos que son más rápidos o más simples que los mejores algoritmos deterministas, con garantías sobre el tiempo esperado (Las Vegas) o sobre la probabilidad de error (Monte Carlo), a menudo utilizando desigualdades de concentración para el análisis.
- Razones de aproximación para problemas NP-difíciles
- Cuando las soluciones exactas son intratables, un algoritmo de aproximación proporciona una solución demostrablemente dentro de un factor (la razón de aproximación) del óptimo; la razón alcanzable caracteriza qué tan bien se puede aproximar un problema.
Clinical relevance
Estos métodos constituyen el conjunto de herramientas prácticas para problemas difíciles e inciertos: los algoritmos aleatorizados impulsan las pruebas de primalidad en criptografía, el hashing y el equilibrio de carga; los algoritmos de aproximación producen soluciones utilizables para problemas NP-difíciles de programación, enrutamiento, agrupamiento y localización de instalaciones; y los algoritmos en línea modelan el almacenamiento en caché, la paginación y la asignación de recursos donde las decisiones deben tomarse en tiempo real.
History
Los algoritmos aleatorizados ganaron prominencia con las pruebas de primalidad de Solovay-Strassen y Rabin en la década de 1970 y la defensa más amplia de Rabin de los métodos probabilísticos. Los algoritmos de aproximación crecieron junto con la teoría de la NP-completitud a partir de la década de 1970, y el análisis competitivo de los algoritmos en línea fue formalizado por Sleator y Tarjan en la década de 1980, formando juntos el estudio moderno de los algoritmos inexactos y probabilísticos.
Key figures
- Rajeev Motwani
- Prabhakar Raghavan
- Vijay Vazirani
- Michael Rabin
- Robert Solovay
- Volker Strassen
Related topics
Seminal works
- motwani1995
- vazirani2001
- cormen2009
Frequently asked questions
- ¿Son poco fiables los algoritmos aleatorizados porque utilizan la aleatoriedad?
- No. Los algoritmos de Las Vegas siempre devuelven una respuesta correcta y solo su tiempo de ejecución varía. Los algoritmos de Monte Carlo pueden cometer errores, pero la probabilidad de error puede reducirse arbitrariamente mediante la repetición. Sus garantías son afirmaciones probabilísticas precisas, no imprevisibilidad.
- ¿Por qué utilizar un algoritmo de aproximación en lugar de simplemente encontrar la solución óptima?
- Para los problemas de optimización NP-difíciles, encontrar el óptimo exacto puede ser inviable para entradas grandes. Un algoritmo de aproximación se ejecuta en tiempo polinomial y garantiza una solución dentro de un factor conocido del óptimo, lo que a menudo es lo suficientemente bueno y mucho más práctico que esperar una respuesta exacta.