aproximaciones con redes neuronales

Capítulo 4 Algoritmos de aproximación
4.1 Fundamentos de los Algoritmos de Aproximación
Muchos problemas NP-Completos son formulados en forma natural como
problemas de optimización. Se sabe que la programación dinámica y los algoritmos de
Ramificación y Acotamiento (Branch and Bound) que son algoritmos exactos para
encontrar soluciones óptimas requieren tiempo superpolinomial a pesar de queestos
algoritmos son más eficientes que la búsqueda exhaustiva pura, su tiempo de corrida es
aún exponencial. Por esa razón es entonces natural buscar otra alternativa de solución
como son los algoritmos de aproximación que trabajan en tiempo polinomial [YAN94],
[MEH93].
Definición 4.1 :

La clase de problemas de optimización que se derivan de
problemas de decisión en NP es llamada NPO,como un acrónimo
para designar que son problemas de optimización derivados de
problemas NP [DJO74].

Así, los algoritmos de aproximación surgen de la inquietud de la comunidad
científica en los años 70's, donde se pensó que las dos clases P y NP eran distintas y que
por lo tanto no había algoritmos de tiempo polinomial que fuesen capaces de resolver
estos problemas en NPO. Sin embargo dadoque existían muchos problemas que tenían
fuertes aplicaciones en la práctica era importante determinar la tratabilidad
computacional de ellos, por lo que muchos investigadores comenzaron a considerar
relajaciones de estos problemas de manera que se obtuvieran versiones que fueran
tratables. Así nace la primera relajación considerada que fue la condición de
"optimabilidad", por lo que seenfocaron a la construcción de algoritmos de aproximación
que trabajan en tiempo polinomial y que calculan soluciones cercanas al óptimo global en
un tiempo pequeño; es decir, soluciones que garantizaran estar dentro de un factor
multiplicativo de la solución óptima [DJO74], [MEH93]. De lo que se deriva la
definición de un algoritmo de aproximación:
Definición 4.2 :

Un algoritmo A es un algoritmode aproximación para un
problema de optimización ∏ en NPO si dada una instancia de
entrada I, éste calcula una solución factible S para cada entrada I
[JOD74].

Lo interesante de la solución de estos problemas es precisamente que si son
algoritmos de aproximación, ¿qué tanto se aproximan a su solución real y cuál es un valor
garantizado de exactitud?, para ello existe una métrica teóricaestándar para medir la
calidad de un algoritmo de aproximación, que es el cociente para el peor de los casos que
indica que tan cerca del valor óptimo están las soluciones encontradas por un algoritmo
de aproximación. Dicha cercanía puede ser expresada como el cociente del valor
obtenido por el algoritmo de aproximación sobre el valor de la solución óptima. Se usará
la notación OPT(I) paradenotar el valor óptimo de la función objetivo en la instancia I y
V(I,A(I)) para denotar el valor obtenido por el algoritmo A al evaluar la instancia I en la
función objetivo [JOD74].
57

Definición 4.3 :

Se define el cociente de aproximación de un algoritmo A, denotado
por CA, para una instancia I de un problema de optimización ∏ (
con  I = n ) como [JOD74] :

 V(I,A(I)) OPT(I) 
CA = min 
,

 OPT(I) V(I, A(I) 

Nótese que CA es siempre menor o igual a 1 y el factor de garantía rA del
algoritmo A para ∏ será :
rA = min {CA  para toda I de ∏ }
A una solución que está dentro de un factor multiplicatico rA del valor óptimo se le
conoce como una rA-aproximación, y decimos que :
Definición 4.4 :

Un problema NPO es aproximable dentro de un factor rA si éstetiene un algoritmo de aproximación de tiempo polinomial con
factor de garantía rA [JOD74].

Se dice que un algoritmo A es un algoritmo de aproximación-α para un problema
de optimización ∏, con α una constante, Si A es un algoritmo de aproximación tal que
para toda instancia I de ∏, produce una solución que está dentro de α-veces el OPT(I).
También es usual considerar el término algoritmo de...