En informática teórica , el análisis suavizado es una forma de medir la complejidad de un algoritmo . Desde su introducción en 2001, el análisis suavizado se ha utilizado como base para una investigación considerable, para problemas que van desde la programación matemática , el análisis numérico , el aprendizaje automático y la minería de datos . [1] Puede proporcionar un análisis más realista del rendimiento práctico del algoritmo, como su tiempo de ejecución, que el uso de escenarios del peor de los casos o del caso medio.
El análisis suavizado es un híbrido de análisis del caso medio y del peor de los casos que hereda las ventajas de ambos. Mide el rendimiento esperado de los algoritmos bajo ligeras perturbaciones aleatorias de las entradas del peor de los casos. Si la complejidad suavizada de un algoritmo es baja, es poco probable que el algoritmo tarde mucho en resolver casos prácticos cuyos datos están sujetos a ligeros ruidos e imprecisiones. Los resultados de complejidad suavizada son resultados probabilísticos fuertes, que indican a grandes rasgos que, en cada vecindario suficientemente grande del espacio de entradas, la mayoría de las entradas se pueden resolver fácilmente. Por tanto, una baja complejidad suavizada significa que la dureza de las entradas es una propiedad "frágil".
Aunque el análisis del peor de los casos ha tenido un gran éxito en explicar el rendimiento práctico de muchos algoritmos, este estilo de análisis da resultados engañosos para una serie de problemas. La complejidad del peor de los casos mide el tiempo que lleva resolver cualquier entrada, aunque es posible que las entradas difíciles de resolver nunca surjan en la práctica. En tales casos, el peor tiempo de ejecución puede ser mucho peor que el tiempo de ejecución observado en la práctica. Por ejemplo, la complejidad del peor caso de resolver un programa lineal usando el algoritmo simplex es exponencial, [2] aunque el número observado de pasos en la práctica es aproximadamente lineal. [3] [4] El algoritmo simplex es de hecho mucho más rápido que el método elipsoide en la práctica, aunque este último tiene la complejidad del peor de los casos en tiempo polinómico .
El análisis de casos promedio se introdujo por primera vez para superar las limitaciones del análisis de casos más desfavorables. Sin embargo, la complejidad de casos promedio resultante depende en gran medida de la distribución de probabilidad que se elija sobre la entrada. Las entradas reales y la distribución de las entradas pueden ser diferentes en la práctica de las suposiciones hechas durante el análisis: una entrada aleatoria puede ser muy diferente a una entrada típica. Debido a esta elección del modelo de datos, un resultado de caso promedio teórico podría decir poco sobre el rendimiento práctico del algoritmo.
El análisis suavizado generaliza tanto el análisis del caso medio como el del peor de los casos y hereda las fortalezas de ambos. Se pretende que sea mucho más general que la complejidad de caso promedio, al tiempo que permite probar los límites de baja complejidad.
Historia
ACM y la Asociación Europea de Ciencias de la Computación Teórica otorgaron el Premio Gödel 2008 a Daniel Spielman y Shanghua Teng por desarrollar análisis suavizados. En 2010, Spielman recibió el Premio Nevanlinna por desarrollar análisis suavizados. El artículo de JACM de Spielman y Teng "Análisis suavizado de algoritmos: por qué el algoritmo simplex generalmente toma tiempo polinomial" también fue uno de los tres ganadores del Premio Fulkerson 2009 patrocinado conjuntamente por la Sociedad de Programación Matemática (MPS) y la Sociedad Matemática Americana (AMS) .
Ejemplos de
Algoritmo simplex para programación lineal
El algoritmo simplex es un algoritmo muy eficiente en la práctica y es uno de los algoritmos dominantes para la programación lineal en la práctica. En problemas prácticos, el número de pasos dados por el algoritmo es lineal en el número de variables y restricciones. [3] [4] Sin embargo, en el peor de los casos teóricos, se necesitan muchos pasos exponencialmente para la mayoría de las reglas de pivote analizadas con éxito. Esta fue una de las principales motivaciones para desarrollar un análisis suavizado. [5]
Para el modelo de perturbación, asumimos que los datos de entrada están perturbados por el ruido de una distribución gaussiana . Para fines de normalización, asumimos que los datos no alterados satisface para todas las filas de la matriz El ruido tiene entradas independientes muestreadas de una distribución gaussiana con media y desviación estándar . Establecimos. Los datos de entrada suavizados consisten en el programa lineal
- maximizar
- sujeto a
- .
Si el tiempo de ejecución de nuestro algoritmo en datos es dado por entonces la complejidad suavizada del método simplex es [6]
Este límite es válido para una regla de pivote específica llamada regla de vértice de sombra. La regla del vértice de la sombra es más lenta que las reglas de pivote más comúnmente utilizadas, como la regla de Dantzig o la regla del borde más empinado [7], pero tiene propiedades que la hacen muy adecuada para el análisis probabilístico. [8]
Búsqueda local de optimización combinatoria
Varios algoritmos de búsqueda local tienen malos tiempos de ejecución en el peor de los casos, pero funcionan bien en la práctica.
Un ejemplo es la heurística de 2 opciones para el problema del vendedor ambulante . Puede tomar exponencialmente muchas iteraciones hasta encontrar una solución localmente óptima, aunque en la práctica el tiempo de ejecución es subcuadrático en el número de vértices. [9] La relación de aproximación , que es la relación entre la longitud de la salida del algoritmo y la longitud de la solución óptima, tiende a ser buena en la práctica, pero también puede ser mala en el peor de los casos teóricos.
Una clase de casos de problemas puede estar dada por puntos en la caja , donde sus distancias por pares provienen de una norma . Ya en dos dimensiones, la heurística de 2 opciones podría tomar exponencialmente muchas iteraciones hasta encontrar un óptimo local. En este escenario, se puede analizar el modelo de perturbación donde los vérticesse muestrean de forma independiente de acuerdo con distribuciones de probabilidad con función de densidad de probabilidad . Para, los puntos se distribuyen uniformemente. Cuándoes grande, el adversario tiene más capacidad para aumentar la probabilidad de casos de problemas difíciles. En este modelo de perturbación, el número esperado de iteraciones de la heurística de 2 opciones, así como las razones de aproximación de la salida resultante, están acotadas por funciones polinómicas de y . [9]
Otro algoritmo de búsqueda local para el que el análisis suavizado tuvo éxito es el algoritmo de Lloyd para la agrupación de k-medias . Dado puntos en , es NP-difícil encontrar una buena partición en grupos con pequeñas distancias por pares entre puntos en el mismo grupo. El algoritmo de Lloyd se usa ampliamente y es muy rápido en la práctica, aunque puede tomariteraciones en el peor de los casos para encontrar una solución localmente óptima. Sin embargo, suponiendo que los puntos tienen distribuciones gaussianas independientes , cada una con una expectativa en y desviación estándar , el número esperado de iteraciones del algoritmo está limitado por un polinomio en , y . [10]
Ver también
- Complejidad de casos promedio
- Tiempo pseudopolinomial
- Complejidad en el peor de los casos
Referencias
- ^ Spielman, Daniel ; Teng, Shang-Hua (2009), "Análisis suavizado: un intento de explicar el comportamiento de los algoritmos en la práctica" (PDF) , Comunicaciones del ACM , ACM, 52 (10): 76–84, doi : 10.1145 / 1562764.1562785
- ^ Amenta, Nina ; Ziegler, Günter (1999), "Productos deformados y sombras máximas de politopos", Contemporary Mathematics , American Mathematical Society, 223 : 10-19, CiteSeerX 10.1.1.80.3241 , doi : 10.1090 / conm / 223 , ISBN 9780821806746, MR 1661377
- ^ a b Shamir, Ron (1987), "The Efficiency of the Simplex Method: A Survey", Management Science , 33 (3): 301–334, doi : 10.1287 / mnsc.33.3.301
- ^ a b Andrei, Neculai (2004), "Andrei, Neculai." Sobre la complejidad del paquete MINOS para la programación lineal ", Estudios en Informática y Control , 13 (1): 35–46
- ^ Spielman, Daniel ; Teng, Shang-Hua (2001), "Análisis suavizado de algoritmos: por qué el algoritmo simplex generalmente toma tiempo polinomial", Actas del trigésimo tercer simposio anual de ACM sobre teoría de la computación , ACM: 296-305, arXiv : cs / 0111050 , Bibcode : 2001cs ....... 11050S , doi : 10.1145 / 380752.380813 , ISBN 978-1-58113-349-3
- ^ Dadush, Daniel; Huiberts, Sophie (2018), "Un análisis amigable y suavizado del método simplex", Actas del 50 ° Simposio anual ACM SIGACT sobre teoría de la computación : 390–403, arXiv : 1711.05667 , doi : 10.1145 / 3188745.3188826 , ISBN 9781450355599
- ^ Borgwardt, Karl-Heinz; Damm, Renate; Donig, Rudolf; Joas, Gabriele (1993), "Estudios empíricos sobre la eficiencia promedio de variantes simplex bajo simetría de rotación", ORSA Journal on Computing , Sociedad de Investigación de Operaciones de América, 5 (3): 249-260, doi : 10.1287 / ijoc.5.3. 249
- ^ Borgwardt, Karl-Heinz (1987), El método simplex: un análisis probabilístico , algoritmos y combinatorios, 1 , Springer-Verlag, doi : 10.1007 / 978-3-642-61578-8 , ISBN 978-3-540-17096-9
- ^ a b Englert, Matthias; Röglin, Heiko; Vöcking, Berthold (2007), "Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP", Actas del Decimoctavo Simposio Anual ACM-SIAM sobre Algoritmos Discretos , 68 : 190–264, doi : 10.1007 / s00453-013 -9801-4
- ^ Arthur, David; Manthey, Bodo; Röglin, Heiko (2011), "Análisis suavizado del método de k-medias", Journal of the ACM , 58 (5): 1–31, doi : 10.1145 / 2027216.2027217