Algoritmos de aproximación

Descripción general:
un algoritmo de aproximación es una forma de tratar la completitud de NP para un problema de optimización. Esta técnica no garantiza la mejor solución. El objetivo del algoritmo de aproximación es acercarse lo más posible a la solución óptima en tiempo polinomial. Dichos algoritmos se denominan algoritmos de aproximación o algoritmos heurísticos.

Características del algoritmo de aproximación : 
aquí, discutiremos las características del algoritmo de aproximación de la siguiente manera.

• Un algoritmo de aproximación garantiza ejecutarse en tiempo polinomial aunque no garantiza la solución más efectiva.
• Un algoritmo de aproximación garantiza la búsqueda de una solución de alta precisión y calidad superior (digamos dentro del 1% del óptimo)
• Los algoritmos de aproximación se utilizan para obtener una respuesta cercana a la solución (óptima) de un problema de optimización en tiempo polinómico.

Proporciones de rendimiento para algoritmos de aproximación:
aquí, discutiremos las proporciones de rendimiento del algoritmo de aproximación de la siguiente manera.

Escenario 1 :

1. Supongamos que estamos trabajando en un problema de optimización en el que cada solución potencial tiene un costo y deseamos encontrar una solución casi óptima. Dependiendo del problema, podemos definir una solución óptima como una con el máximo costo posible o una con el mínimo costo posible, es decir, el problema puede ser un problema de maximización o minimización.
2. Decimos que un algoritmo para un problema tiene una razón apropiada de P(n) si, para cualquier tamaño de entrada n, el costo C de la solución producida por el algoritmo está dentro de un factor de P(n) del costo C* de una solución óptima de la siguiente manera.

max(C/C*,C*/C)<=P(n)

Escenario 2:
si un algoritmo alcanza una relación de aproximación de P(n), lo llamamos algoritmo de aproximación P(n).

• Para un problema de maximización, 0< C < C*, y la relación C*/C da el factor por el cual el costo de una solución óptima es mayor que el costo del algoritmo aproximado.
• Para un problema de minimización, 0< C* < C, y la relación de C/C* da el factor por el cual el costo de una solución aproximada es mayor que el costo de una solución óptima.

Algunos ejemplos del algoritmo de aproximación:
aquí, discutiremos algunos ejemplos del algoritmo de aproximación de la siguiente manera.

1. El problema de cobertura de vértices : 
   en el problema de cobertura de vértices, el problema de optimización es encontrar la cobertura de vértices con la menor cantidad de vértices , y el problema de aproximación es encontrar la cobertura de vértices con pocos vértices .
    
2. Problema del vendedor viajero :
   en el problema del vendedor viajero, el problema de optimización es encontrar el ciclo más corto y el problema de aproximación es encontrar un ciclo corto .
    
3. El problema de cobertura de conjuntos : 
   este es un problema de optimización que modela muchos problemas que requieren la asignación de recursos. Aquí, se utiliza una relación de aproximación logarítmica.
    
4. El problema de la suma de subconjuntos : 
   en el problema de la suma de subconjuntos, el problema de optimización consiste en encontrar un subconjunto de {x1,×2,×3…xn} cuya suma sea lo más grande posible pero no mayor que el valor objetivo t.