Algoritmo de aproximación

Algoritmo de aproximación

En ciencias de la computación e investigación de operaciones, un algoritmo de aproximación es un algoritmo usado para encontrar soluciones aproximadas a problemas de optimización. Están a menudo asociados con problemas NP-hard; como es poco probable que alguna vez se descubran algoritmos eficientes de tiempo polinómico que resuelvan exactamente problemas NP-hard, se opta por encontrar soluciones no-óptimas en tiempo polinomial. A diferencia de las heurísticas, que usualmente sólo encuentran soluciones razonablemente buenas en tiempos razonablemente rápidos, lo que se busca aquí es encontrar soluciones que está demostrado son de calidad y cuyos tiempos de ejecución están acotadas por cotas conocidas. Idealmente, la aproximación mejora su calidad para factores constantes pequeños (por ejemplo, dentro del 5% de la solución óptima). Los algoritmos de aproximación están siendo cada vez más utilizados para resolver problemas donde los algoritmos exactos de tiempo polinomial son conocidos pero demasiado costosos debido al tamaño de la entrada.

Un ejemplo típico para un algoritmo de aproximación es uno para resolver el problema de la cobertura de vértices de la teoría de grafos: encontrar una arista no cubierta y añadir sus dos puntos finales a la cobertura de vértice, y repetir hasta que ya no queden aristas. Es claro que la cobertura resultante será a lo más dos veces del largo de la solución óptima. Este es un algoritmo de aproximación de factor constante con un factor de 2.

Los problemas NP-hard varían mucho en su aproximación; algunos, tales como el problema de la mochila, pueden ser aproximados mediante cualquier factor superior a 1 (tal familia de algoritmos de aproximación se conoce como esquema de aproximación de tiempo polinomial o PTAS). Otros, como el problema de la clique, son imposibles de aproximar dentro de cualquier constante, o incluso factor polinomiales, a menos que P = NP.

Los problemas NP-hard frecuentemente pueden expresarse como programación entera (PE) y ser resueltos exactamente en tiempo exponencial. Muchos algoritmos de aproximación surgen de la relajación de la programación lineal (PL), propia de la programación entera.

No todos los algoritmos de aproximación son adecuados para todas las aplicaciones prácticas. A menudo utilizan resolvedores (solvers) de IP, LP y programación semidefinida, estructuras de datos complejas o técnicas de algoritmos sofisticadas que tienden a dificultar los problemas de implementación. Además, algunos algoritmos de aproximación poseen tiempos de ejecución poco prácticos, incluso a pesar de ser polinómicos, como por ejemplo, del orden de O(n2000). Sin embargo, a pesar de esto último, existen problemas donde los altos tiempos de ejecución y costos de memoria pueden justificarse, tales como los relacionados con la biología computacional, ingeniería financiera, la planificación del transporte, y la gestión de inventario. En estos escenarios, se debe competir contra las correspondientes formulaciones de programación entera directa.

Otra limitación de la aproximación es que esta sólo es aplicable a los problemas de optimización, y no a los problemas de decisión en estado "puro", tales como SAT (a pesar de que es posible representar versiones de optimización para tales problemas, como el respectivo Problema de satisfacibilidad máximo).

Garantías de comportamiento

Para algunos algoritmos de aproximación es posible demostrar con certeza propiedades sobre la aproximación del resultado óptimo. Por ejemplo, en el caso de un ρ-algoritmo de aproximación se ha demostrado que la aproximación a no será mayor (o menor, dependiendo de la situación) que un factor ρ veces la solución óptima s.

\begin{cases}s \leq a \leq \rho s,\qquad\mbox{if } \rho > 1; \\ \rho s \leq a \leq s,\qquad\mbox{if } \rho < 1.\end{cases}

El factor ρ se llama garantía de comportamiento relativo (relative performance guarantee). Un algoritmo de aproximación tiene una garantía de comportamiento absoluto o error acotado ε, si se ha demostrado que

 (s - \epsilon) \leq a \leq (s + \epsilon).

Análogamente, el radio de comportamiento aboluto (absolute performance ratio) ΡA de un algoritmo de aproximación A, donde I es una instancia del problema, y RA(I) es la garantía de comportamiento de A en I (es decir, ρ para la instancia I del problema) es:

 \Rho_A = \inf \{ r \geq 1 | R_A(I) \leq r, \forall I \}

Esto significa que ΡA es la mayor cota en el radio de aproximación, r, que uno encuentra en todas las posibles instancias del problema. Del mismo modo, el radio de comportamiento asintótico (asymptotic performance ratio) R_A^\infty es:

 R_A^\infty = \inf \{ r \geq 1 | \exists n \in \mathbb{Z}^+, R_A(I) \leq r, \forall I, I \geq n\}

Es decir, que es el mismo radio de comportamiento absoluto, con una cota inferior n en el tamaño de las instancias del problema. Se utilizan estos dos tipos de radio porque debido a que existen algoritmos donde la diferencia entre ellos es significativa.

El análisis de dominación (Domination analysis) provee un camino alternativo para analizar la calidad de un algoritmo de aproximación, en términos del rango de la solución computada en la secuencia ordenada de todas las posibles soluciones.

Referencias

  • Vazirani, Vijay V. (2003). Approximation Algorithms. Berlin: Springer. ISBN 3540653678. 
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, y Clifford Stein. Introduction to Algorithms, Segunda Edición. MIT Press y McGraw-Hill, 2001. ISBN 0-262-03293-7. Capítulo 35: Approximation Algorithms, pp.1022–1056.
  • Dorit H. Hochbaum, ed. Approximation Algorithms for NP-Hard problems, PWS Publishing Company, 1997. ISBN 0-534-94968-1. Capítulo 9: Various Notions of Approximations: Good, Better, Best, and More.

Enlaces externos


Wikimedia foundation. 2010.

Игры ⚽ Поможем написать реферат

Mira otros diccionarios:

  • Algoritmo divide y vencerás — En la cultura popular, divide y vencerás hace referencia a un refrán que implica resolver un problema difícil, dividiéndolo en partes más simples tantas veces como sea necesario, hasta que la resolución de las partes se torna obvia. La solución… …   Wikipedia Español

  • Algoritmo de Shor — En computación cuántica, el algoritmo de Shor es un algoritmo cuántico para descomponer en factores un número N en tiempo O((log N)3) y espacio O(logN), así nombrado por Peter Shor. Muchas criptografías de clave pública, tales como RSA, llegarían …   Wikipedia Español

  • Algoritmo de Gauss-Legendre — El algoritmo de Gauss Legendre es un algoritmo para computar los dígitos de π. El método se basa en los trabajos individuales de Carl Friedrich Gauss (1777 1855) y Adrien Marie Legendre (1752 1833) combinados con algoritmos modernos para la… …   Wikipedia Español

  • Algoritmo de recocido simulado — Simulated annealing (SA) o recocido simulado es un algoritmo de búsqueda meta heurística para problemas de optimización global; el objetivo geneneral de este tipo de algoritmos es encontrar una buena aproximación al valor óptimo de una función en …   Wikipedia Español

  • Algoritmo de compresión con pérdida — Se denomina algoritmo de compresión con pérdida a cualquier procedimiento de codificación que tenga como objetivo representar cierta cantidad de información utilizando una menor cantidad de la misma, siendo imposible una reconstrucción exacta de… …   Wikipedia Español

  • Algoritmo de compresión con pérdida — Se llama así a cualquier procedimiento de codificación que tenga como objetivo representar cierta cantidad de información utilizando una menor cantidad de la misma, siendo imposible una reconstrucción exacta de los datos originales. La compresión …   Enciclopedia Universal

  • Error de aproximación — Saltar a navegación, búsqueda El error de aproximación o error numérico es una medida del ajuste de la medida o cálculo de una magnitud con respecto al valor real o teórico que dicha magnitud tiene. Un aspecto importante de los errores de… …   Wikipedia Español

  • Problema de la suma de subconjuntos — Saltar a navegación, búsqueda El problema de la suma de subconjuntos es un problema importante en la teoría de la complejidad y en la criptografía. El problema es este: dado un conjunto de enteros, ¿existe algún subconjunto cuya suma sea… …   Wikipedia Español

  • Inverso multiplicativo — Para otros usos de este término, véase Función recíproca. La función recíproca y = 1/x. Para cada valor de x (eje horizontal) excepto el 0, y (eje vertical) representa su inverso multiplicativo. En matemática, el inverso multiplicativo, recíproco …   Wikipedia Español

  • Cálculo de la raíz cuadrada — Este artículo o sección necesita referencias que aparezcan en una publicación acreditada, como revistas especializadas, monografías, prensa diaria o páginas de Internet fidedignas. Puedes añadirlas así o avisar …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”