Algoritmos de aproximación y heurísticas
Cuando el óptimo exacto no está al alcance, hay dos caminos distintos: uno que promete estar cerca y puede probarlo, y otro que anda bien sin prometer nada. Conviene no confundirlos.
Para este tema conviene tener claro:P, NP y qué significa NP-completo
Un problema NP-difícil no desaparece porque haya que entregarlo el viernes. Lo que se hace es resignar algo: exactitud o garantía. La diferencia entre un algoritmo de aproximación y una heurística es justamente cuál de las dos se resigna, y es una diferencia que se paga en producción.
Garantía demostrada contra andar bien en la práctica
Un algoritmo de aproximación corre en tiempo polinomial y viene con una cota demostrada: su resultado nunca es peor que un factor respecto del óptimo, para toda instancia.
Una heurística también corre rápido y suele dar buenos resultados, pero no promete nada. Puede fallar arbitrariamente mal en alguna entrada, y no hay forma de saber en cuál. Las dos son válidas; lo que no es válido es presentar una como la otra.
Antes de seguir, predecí
Cubrimiento de vértices: el factor 2 más limpio
El ejemplo más limpio es cubrimiento de vértices: elegir el menor conjunto de vértices que toque todas las aristas. El algoritmo de 2-aproximación es casi absurdo: tomar cualquier arista sin cubrir y meter los dos extremos.
El grafo. Hay que elegir el menor conjunto de vértices que toque todas las aristas.
Como el óptimo tiene que incluir al menos uno de los dos por cada arista elegida, y esas aristas no comparten vértices, la solución nunca supera el doble del óptimo. La demostración compara contra un óptimo que nadie calculó, y ese es el truco de casi todas las cotas.
El viajante y su letra chica
En el viajante hay que mirar la letra chica. Con desigualdad triangular —la ruta directa nunca es peor que el desvío— el árbol generador mínimo da una 2-aproximación, y el algoritmo de Christofides la baja a 1.5.
Sin desigualdad triangular, en cambio, se puede demostrar que no existe aproximación con ningún factor constante salvo que P sea igual a NP. Mismo problema, hipótesis distinta, resultado opuesto: la aproximabilidad no es una propiedad del nombre del problema.
Qué tan bien se deja aproximar cada problema
Los problemas se agrupan por lo bien que se dejan aproximar. Algunos admiten un esquema que alcanza cualquier precisión deseada pagando tiempo: mochila tiene uno que da un en tiempo polinomial en .
Otros tienen un techo demostrado —cubrimiento de conjuntos no se puede aproximar mejor que — y otros no admiten nada. Dos problemas igual de NP-completos pueden ser completamente distintos cuando se los mira desde la aproximación.
Las heurísticas y lo que no prometen
Las heurísticas son el otro camino: búsqueda local, recocido simulado, algoritmos genéticos, búsqueda tabú. Todas exploran el espacio de soluciones con alguna regla de mejora y algún mecanismo para no quedarse en un óptimo local.
En la práctica ganan seguido: para el viajante, una búsqueda local bien hecha suele quedar más cerca del óptimo que la 1.5-aproximación con garantía. La contra es que no se sabe cuánto falta, y ajustar sus parámetros es trabajo empírico que no transfiere entre instancias.
Cuándo hace falta poder afirmar algo
La pregunta que decide es si hace falta poder afirmar algo. Si la respuesta va en un contrato, una licitación o un cálculo de costos que alguien va a auditar, la garantía vale más que unos puntos de calidad promedio.
Y hay una tercera opción que combina lo mejor: branch and bound cortado por tiempo devuelve la mejor solución encontrada más el gap contra la cota. Es una garantía calculada sobre la instancia concreta, no un peor caso teórico.
Elegir entre garantía y resultado
| Aproximación | Heurística | Metaheurística | |
|---|---|---|---|
| Promete | nunca peor que un factor ρ | nada | nada, y suele andar muy bien |
| Se puede demostrar | sí, y hay que hacerlo | no | no |
| Calidad típica | suele quedar lejos de la cota | sorprendentemente buena | la mejor de las tres, con tiempo |
| Cuándo va | hay que garantizarle algo a alguien | se puede medir contra el óptimo en casos chicos | hay tiempo de cómputo y el problema es grande |
| Ejemplo | 2-aproximación de cubrimiento de vértices | el vecino más cercano en el viajante | recocido simulado, búsqueda tabú |
Más a fondo · formalProblemas que no se pueden ni aproximar
Hay un resultado que conviene conocer porque marca un límite más duro que NP-completo. Para algunos problemas, encontrar una aproximación dentro de cualquier factor constante es también NP-difícil. El caso clásico es el viajante general, sin desigualdad triangular: si existiera una aproximación con factor constante, se podría usar para decidir si hay un ciclo hamiltoniano, que es NP-completo.
El contraste es instructivo: agregando la desigualdad triangular —que se cumple en cualquier problema con distancias reales—, aparece la 2-aproximación del árbol generador mínimo y la 1,5-aproximación de Christofides. El mismo problema pasa de inaproximable a razonablemente aproximable por una propiedad de los datos.
Esa es la moraleja que más rinde: cuando algo parece imposible, vale la pena mirar qué supuesto adicional cumple tu instancia real. Casi siempre hay uno, y casi siempre cambia la clase del problema.
Cierre
Aproximación es resignar exactitud conservando garantía; heurística es resignar la garantía buscando calidad. Las cotas se demuestran contra un óptimo que nunca se calcula, dependen de las hipótesis del problema, y son lo que permite decir algo sobre el resultado además de mostrarlo.
Autoevaluación
¿Lo entendiste?
Práctica