Algoritmo de aproximación

En Ciencias de la Computación e Investigación de Operaciones, un algoritmo de aproximación es un algoritmo utilizado para encontrar soluciones aproximadas a problemas de optimización. Los Algoritmos de aproximación a menudo se asocian con problemas NP-difíciles; ya que es poco probable que pueda haber algoritmos eficientes en tiempo polinómico exactos que resuelvan problemas NP - difíciles, uno está satisfecho con soluciones subóptimas en tiempo polinómico. A diferencia de la heurística, que suele encontrar soluciones razonablemente buenas en tiempos razonablemente rápidos, en este caso se buscan soluciones de calidad demostrable y tiempos de ejecución con límites demostrables. Idealmente, la aproximación es óptima hasta un factor constante pequeño (por ejemplo, dentro del 5% de la solución óptima). Los Algoritmos de aproximación se utilizan cada vez más para problemas donde se conocen algoritmos exactos en tiempo polinómico, pero son demasiado caros debido al tamaño de la entrada. Un ejemplo típico de un algoritmo de aproximación es que para la cobertura de vértices en gráficos: encuentre un borde descubierto y agregue "ambos" extremos a la cobertura de vértices, hasta que no quede ninguno. Está claro que la cobertura resultante es como máximo el doble de grande que la óptima. Este es un algoritmo de aproximación de factor constante con un factor de 2. NP-los problemas difíciles varían mucho en su aproximabilidad; algunos, como el problema de empaquetado, se pueden aproximar dentro de cualquier factor mayor que 1 (tal familia de Algoritmos de aproximación a menudo se llama esquema de aproximación en tiempo polinomial o PTA). Otros son imposibles de aproximar dentro de cualquier constante, o incluso factor polinómico, a menos que P = NP, como el problema de camarilla máxima. NP-los problemas difíciles a menudo se pueden expresar como programas enteros (IP) y resolver exactamente en tiempo exponencial. Muchos algoritmos de aproximación emergen de la relajación de la programación lineal de todo el programa. No todos los Algoritmos de aproximación son adecuados para todas las aplicaciones prácticas. A menudo utilizan resolutores IP/ LP / semi-definidos, estructuras de datos complejas o técnicas algorítmicas sofisticadas que conducen a problemas que son difíciles de implementar. Además, algunos algoritmos de aproximación tienen tiempos de ejecución poco prácticos a pesar de que están en tiempo polinómico, por ejemplo, O (n 2000). Sin embargo, el estudio de Algoritmos incluso muy caros no es una investigación completamente teórica, ya que pueden proporcionar información valiosa. Un ejemplo clásico son los PTA iniciales para el TSP euclidiano debido a que Sanjeev Arora tiene un tiempo de ejecución prohibitivo; sin embargo, en un año, Arora perfeccionó las ideas en un algoritmo de tiempo lineal. Estos algoritmos también son válidos en algunas aplicaciones en las que el tiempo de ejecución y el costo pueden justificarse, por ejemplo, la biología computacional, la ingeniería financiera, la planificación del transporte y la gestión de inventarios. En tales situaciones, deben competir con las correspondientes formulaciones directas de propiedad intelectual. Otra limitación del enfoque es que se aplica solo a problemas de optimización y no a problemas de decisión "puros" como la satisfacibilidad, aunque a menudo es posible concebir versiones de optimización de tales problemas, como el problema de satisfacibilidad máxima (Max SAT). Inapproximability ha sido un área fructífera de investigación en el campo de la teoría de la complejidad computacional desde el resultado de 1990 de Feige, Goldwasser, Lovasz, Safra y Szegedy sobre la inapproximability del conjunto independiente. Después de eso Arora et al. probaron el Teorema de PCP un año más tarde, se demostró que los Algoritmos de aproximación elaborados en 1974 por Johnson para el SAT máximo, la cobertura del conjunto, el conjunto independiente y la coloración logran la relación de aproximación óptima, asumiendo P! = NP.

Para algunos algoritmos de aproximación es posible probar ciertas propiedades en la aproximación del resultado óptimo. Por ejemplo, un algoritmo para la aproximación ρ A se define como un algoritmo para el que se ha demostrado que el valor/coste, f (x), de la solución aproximada A (x) a una instancia x no será más (o menos, dependiendo de la situación) tan grande de un factor ρ veces el valor, OPT, de una solución óptima. El factor ρ se denomina garantía de rendimiento relativo. Un algoritmo para la aproximación tiene un error de garantía de rendimiento absoluto o limitado C, si se ha demostrado para cada instancia x que de manera similar, la garantía de rendimiento, R (x, y), de una solución y a una instancia x se define como donde f (y) es el valor/costo de la solución y para la instancia x. Claramente, la garantía de rendimiento es mayor o igual a 1 si y solo si y es una gran solución. Si un algoritmo A garantiza devolver soluciones con una garantía de rendimiento al máximo de r (n), entonces se dice que A es un algoritmo de aproximación r (n) y tiene una relación de aproximación de r (n). Del mismo modo, un problema con un algoritmo de aproximación R (n) se dice que es r (n) - aproximable o que tiene una relación de aproximación de r (n). Cabe señalar que, para los problemas de minimización, las dos garantías diferentes proporcionan el mismo resultado y que, para los problemas de maximización, una garantía relativa de rendimiento de ρ es equivalente a una garantía de rendimiento de ρ. r = ρ − 1 {\displaystyle R = \ Rho ^{ - 1}} . La garantía de rendimiento absoluta P A {\displaystyle \mathrm {P} _{A}} de algún algoritmo de aproximación A, donde x se refiere a la instancia de un problema, y donde R A ( x ) {\displaystyle R_{a} (x)} es la garantía de rendimiento de A en x (es decir, ρ para la instancia del problema x) es: esto significa que P A {\displaystyle \mathrm {P} _{A}} es el mayor límite en la relación de aproximación, r, que se ve en todos los casos posibles del problema En la literatura, ambas definiciones son comunes, pero está claro cuál es la definición utilizada desde entonces para los problemas de maximización, como ρ ≤ 1 mientras r ≥ 1. Del mismo modo, la relación de rendimiento asintótico R A ∞ {\displaystyle R_ {a}^{\infty }} is: esto significa que es el mismo que la relación de rendimiento absoluto, con un límite inferior n en el tamaño de las instancias del problema. Estos dos tipos de relaciones se utilizan porque hay algoritmos donde la diferencia entre los dos es significativa.

Ahora hay varias técnicas estándar que se utilizan para diseñar un algoritmo de aproximación. Estos incluyen los siguientes.

En la literatura, una relación de aproximación para un problema de maximización (minimización) de c - ++ (min: c + ϵ) significa que el algoritmo tiene una relación de aproximación de c ++ para un arbitrario ϵ > 0, pero que la relación no se muestra (o no se puede mostrar) Para ϵ = 0. Un ejemplo de esto es la relación óptima de inaproximabilidad - inexistencia de aproximabilidad - de 7 / 8 + ϵ Para instancias satisfactorias de MAX - 3sat debido a Johan Håstad. Como se mencionó anteriormente, cuando c = 1, se dice que el problema tiene un esquema de aproximación en tiempo polinómico. Un término ϵ Se puede mostrar cuando un algoritmo de aproximación introduce un error multiplicativo y un error constante al excelente mínimo de instancias de tamaño n va al infinito cuando lo hace n. en este caso, la relación de la aproximación es c k k / OPT = c o o (1) para algunas constantes c y k. dado un arbitrario 0 > 0, podemos elegir una N lo suficientemente grande como para que el término k / OPT < ϵ para cada N ≥ N. Para cada IU fija, las instancias de tamaño n < N pueden ser resueltas por fuerza bruta, mostrando así una relación aproximación - existencia de Algoritmos de aproximación con una garantía - de C ++ para cada IU & gt; 0.

Algoritmo

Teoría de la complejidad computacional

Algoritmo en línea

En Ciencias de la Computación, el término algoritmo en línea significa un algoritmo, para resolver un problema, que debe proporcionar resultados sin tener al pr...

Algoritmo

Un algoritmo es una estrategia que sirve para resolver un problema y consiste en una secuencia finita de operaciones (también llamadas instrucciones), le permit...

Stub-programación

Esta página se basa en el artículo de Wikipedia: Fuente, Autores, Licencia Creative Commons Reconocimiento-CompartirIgual.
This page is based on the Wikipedia article: Source, Authors, Creative Commons Attribution-ShareAlike License.
contactos
Política de privacidad , Descargos de responsabilidad