Informática teórica: ¿Cuál es la diferencia entre un algoritmo de aproximación y un heurístico?

Una heurística es típicamente un conjunto de pasos intuitivos que pueden o no llevarlo a una solución óptima. Un algoritmo de aproximación, por otro lado, está equipado con una promesa formal de estar razonablemente cerca de una solución óptima.

Un ejemplo canónico que ilustra la diferencia es el siguiente. Supongamos que tiene un gráfico G y el problema es encontrar la cubierta de vértice más pequeña. Una cubierta de vértice es un subconjunto de vértices S de tal manera que cada borde de G tiene al menos un punto final S.

Una heurística natural (codiciosa) es elegir vértices que tienen muchos bordes incidentes sobre ellos, porque parecen estar “cuidando” muchos bordes a la vez. Resulta que esto podría (potencialmente) ser muy subóptimo. Por otro lado, es un ejercicio interesante diseñar un gráfico donde esta estrategia podría fallar potencialmente.

Por otro lado, considere el siguiente algoritmo. Sea M una colección máxima de bordes disjuntos (esto es fácil de producir, simplemente escogiendo un borde, eliminándolo; y repitiendo hasta que no queden bordes). Los puntos finales de M juntos constituyen una cubierta de vértice (por máxima). Además, tenga en cuenta que cualquier cubierta de vértice tiene un tamaño de al menos | M | / 2, ya que cada borde en M necesita un “testigo distinto” en cualquier cubierta de vértice. Armados con estos hechos, sabemos que nuestra solución propuesta está “fuera de lo óptimo” por, en el peor de los casos, un factor de dos.

Una heurística a menudo puede (ser) un algoritmo de aproximación que simplemente no ha sido analizado desde la perspectiva requerida.

Por ejemplo, considere el problema del corte máximo: dado un gráfico G, encuentre una partición de V (G) en dos partes (llamada “corte”) que maximice el número de bordes que tienen un punto final en cada parte (estos son los bordes que se dice que cruzan el corte ).

Una vez más, una heurística natural podría ser la siguiente. Inicialicemos A y B en conjuntos vacíos. Para comenzar, elija un vértice y asígnelo a la parte A. En adelante, repita los vértices restantes: para cada vértice v en el gráfico, “intente” asignar v a A y cuente los bordes que cruzan el corte [matemática] (A \ cup \ {v \}, B) [/ math] y de manera similar, intente asignar v a B y cuente los bordes que cruzan el corte [math] (A, B \ cup \ {v \}) [/ math]. Asigne v al lado correspondiente al corte más grande.

Esto tal vez cuente como una heurística suficientemente natural. Con un poco de reflexión, se puede demostrar que esto es, de hecho, también una aproximación de dos para corte máximo. Si dejamos que m denote el número de bordes en G, tenga en cuenta que cualquier corte puede tener como máximo m bordes que lo crucen. Ahora, no es muy difícil demostrar que el procedimiento anterior garantiza que al menos m / 2 bordes crucen el corte. Esto nos da la garantía deseada.

A menudo, la heurística podría prestarse a algunas garantías con respecto a lo óptimo, aunque posiblemente estos serían más débiles que los algoritmos de aproximación más conocidos. Por otro lado, es bastante posible que una heurística sea tal que no haya una garantía posible sobre el rendimiento, es decir, uno podría demostrar una familia infinita de ejemplos en los que la solución de la heurística es arbitrariamente peor en comparación con el rendimiento. mejor posible. Sin embargo, cualquier algoritmo de aproximación que valga la pena es necesario para tener alguna garantía por definición, incluso si es bastante débil.

Como dice Justin, un algoritmo de aproximación es solo una heurística que tiene un teorema adjunto.

Por lo general, el teorema trata sobre el análisis del peor de los casos , tal como lo es para un algoritmo exacto. El teorema de un algoritmo de tiempo polinómico exacto generalmente dirá:

“En el peor de los casos sobre todas las entradas posibles x, el algoritmo A se ejecutará en tiempo polinómico y producirá una solución exactamente óptima A (x)”

Un algoritmo de aproximación siempre se combina con una medida de calidad numérica f, que evalúa la calidad de una solución en una entrada dada. OPT (x) = max f (s, x) es el valor de la mejor solución en la entrada x. Un algoritmo de aproximación tendrá la siguiente garantía:

“En el peor de los casos sobre todas las entradas posibles x, el algoritmo A se ejecutará en tiempo polinómico y producirá una solución A (x) tal que f (A (x), x)> = OPT (x) / t”

Aquí t> 1 es el factor de aproximación, y cuanto menor es t, mejor es el algoritmo.

En contraste, cuando las personas hablan de buenas heurísticas (por ejemplo, ramificar y limitar para resolver programas enteros), a menudo significan que en la mayoría de las entradas encontradas en la práctica, la heurística parece funcionar rápidamente o producir buenas soluciones. Pero podría ser posible preparar una entrada incorrecta (por ejemplo, codificando un problema de factorización de enteros como un programa de enteros) en el que la heurística tomará un tiempo exponencial o no producirá una buena solución.

Un algoritmo de aproximación es una heurística con una garantía de rendimiento.