performance - significa - Necesito resolver un problema NP-difícil. ¿Hay esperanza?
qué es un problema np hard (1)
Hay muchos problemas del mundo real que resultan ser NP-hard . Si asumimos que P ≠ NP , no hay algoritmos de tiempo polinomial para estos problemas.
Si tiene que resolver uno de estos problemas, ¿hay alguna esperanza de que pueda hacerlo de manera eficiente? ¿O simplemente estás fuera de suerte?
Si un problema es NP- difícil, bajo el supuesto de que P ≠ NP no hay ningún algoritmo que sea
- determinista
- exactamente correcto en todas las entradas todo el tiempo, y
- Eficiente en todas las entradas posibles.
Si necesitas absolutamente todas las garantías anteriores, entonces estás bastante sin suerte. Sin embargo, si está dispuesto a conformarse con una solución al problema que alivie algunas de estas limitaciones, entonces es muy posible que aún haya esperanza. Aquí hay algunas opciones a considerar.
Opción uno: Algoritmos de aproximación
Si un problema es NP- hard y P ≠ NP , significa que no hay un algoritmo que siempre produzca de manera eficiente la respuesta correcta en todas las entradas. Pero, ¿y si no necesitas la respuesta exacta? ¿Qué pasa si solo necesitas respuestas que están cerca de corregir? En algunos casos, es posible que pueda combatir la dureza NP utilizando un algoritmo de aproximación.
Por ejemplo, un ejemplo canónico de un problema difícil de NP es el problema del vendedor ambulante . En este problema, le dan como entrada un gráfico completo que representa una red de transporte. Cada borde en la gráfica tiene un peso asociado. El objetivo es encontrar un ciclo que pase por cada nodo en el gráfico exactamente una vez y que tenga un peso total mínimo. En el caso de que los pesos de borde satisfagan la desigualdad del triángulo (es decir, la mejor ruta desde el punto A al punto B es seguir siempre el enlace directo de A a B), entonces puede recuperar un ciclo cuyo costo es como máximo 3 / 2 óptimo utilizando el algoritmo Christofides .
Como otro ejemplo, se sabe que el problema de la mochila 0/1 es NP- hard. En este problema, se le entrega una bolsa y una colección de objetos con diferentes pesos y valores. El objetivo es empaquetar el valor máximo de los objetos en la bolsa sin exceder el límite de peso de la bolsa. Aunque calcular una respuesta exacta requiere un tiempo exponencial en el peor de los casos, es posible aproximar la respuesta correcta a un grado arbitrario de precisión en el tiempo polinomial. (El algoritmo que hace esto se denomina esquema de aproximación completamente polinomial o FPTAS ).
Desafortunadamente, tenemos algunos límites teóricos en cuanto a la aproximabilidad de ciertos problemas con problemas de NP . El algoritmo de Christofides mencionado anteriormente da una aproximación de 3/2 a la TSP donde los bordes obedecen a la desigualdad del triángulo, pero, curiosamente, es posible mostrar que si P ≠ NP , no hay un algoritmo de aproximación de tiempo polinómico para la TSP que pueda entrar en cualquier constante Factor de óptimo. Por lo general, es necesario investigar un poco para saber qué problemas pueden ser bien aproximados y cuáles no, ya que muchos problemas de NP se pueden aproximar bien y otros no. No parece haber un tema unificado.
Opción Dos: Heurísticas
En muchos problemas de problemas de NP , los enfoques estándar como algortihms codiciosos no siempre producen la respuesta correcta, pero a menudo funcionan razonablemente bien en insumos "razonables". En muchos casos, es razonable atacar los problemas de NP con las heurísticas . La definición exacta de una heurística varía de un contexto a otro, pero por lo general una heurística es un enfoque de un problema que "a menudo" devuelve buenas respuestas al costo de devolver a veces respuestas incorrectas, o es una regla práctica útil que ayuda acelere las búsquedas aunque no siempre guíe la búsqueda de la manera correcta.
Como ejemplo del primer tipo de heurística, veamos el problema de colorear gráficos . Este problema difícil de NP pregunta, dado un gráfico, para encontrar el número mínimo de colores necesarios para pintar los nodos en el gráfico de modo que los puntos finales de ningún borde sean del mismo color. Esto resulta ser un problema particularmente difícil de resolver con muchos otros enfoques (los algoritmos de aproximación más conocidos tienen límites terribles y no se sospecha que tengan un algoritmo eficiente parametrizado). Sin embargo, existen muchas heurísticas para la coloración de gráficos que funcionan bastante bien en la práctica. Existen muchas heurísticas de colores codiciosos para asignar colores a los nodos en un orden razonable, y estas heurísticas a menudo funcionan bastante bien en la práctica. Desafortunadamente, a veces estas heurísticas devuelven respuestas terribles, pero siempre que la gráfica no esté construida patológicamente, las heurísticas a menudo funcionan bien.
Como ejemplo del segundo tipo de heurística, es útil observar a los usuarios de SAT. SAT , el problema de satisfacción booleana, fue el primer problema que se demostró que era NP- difícil. El problema se pregunta, dada una fórmula proposicional (a menudo escrita en forma conjuntiva normal ), para determinar si hay una manera de asignar valores a las variables de tal manera que la fórmula general se evalúe como verdadera. Los solucionadores de SAT modernos se están volviendo muy buenos resolviendo SAT en muchos casos al usar heurísticas para guiar su búsqueda sobre posibles asignaciones de variables. Un famoso algoritmo de resolución de SAT, DPLL , esencialmente intenta todas las asignaciones posibles para ver si la fórmula es satisfactoria, utilizando heurísticas para acelerar la búsqueda. Por ejemplo, si encuentra que una variable es siempre verdadera o falsa, DPLL intentará asignar a esa variable su valor forzado antes de probar otras variables. DPLL también encuentra cláusulas de unidad (cláusulas con solo un literal) y establece los valores de esas variables antes de probar otras variables. El efecto neto de estas heurísticas es que DPLL termina siendo muy rápido en la práctica, aunque se sabe que tiene un comportamiento exponencial en el peor de los casos.
Opción tres: Algoritmos de tiempo pseudopolinómico
Si P ≠ NP , entonces no se puede resolver ningún problema de NP en el tiempo polinomial. Sin embargo, en algunos casos, la definición de "tiempo polinomial" no coincide necesariamente con la intuición estándar del tiempo polinomial. Hablando formalmente, el tiempo polinomial significa polinomio en el número de bits necesarios para especificar la entrada, que no siempre se sincroniza con lo que consideramos que es la entrada.
Como ejemplo, considere el problema de partición de conjunto . En este problema, te dan un conjunto de números y necesitas determinar si hay una manera de dividir el conjunto en dos conjuntos más pequeños, cada uno de los cuales tiene la misma suma. La solución ingenua a este problema se ejecuta en el tiempo O (2 n ) y funciona solo con la prueba de fuerza bruta de todos los subconjuntos. Sin embargo, con la programación dinámica, es posible resolver este problema en el tiempo O (nN), donde n es el número de elementos en el conjunto y N es el valor máximo en el conjunto. Hablando técnicamente, el tiempo de ejecución O (nN) no es un tiempo polinomial porque el valor numérico N se escribe solo en log 2 N bits, pero suponiendo que el valor numérico de N no es demasiado grande, este es un tiempo de ejecución perfectamente razonable.
Este algoritmo se denomina algoritmo de tiempo pseudopolinomial porque el tiempo de ejecución O (nN) "parece" un polinomio, pero técnicamente hablando es exponencial en el tamaño de la entrada. Muchos problemas de NP , especialmente los relacionados con valores numéricos, admiten algoritmos de tiempo pseudopolinómico y, por lo tanto, son fáciles de resolver suponiendo que los valores numéricos no son demasiado grandes.
Para obtener más información sobre el tiempo pseudopolinómico, consulte esta pregunta anterior sobre el desbordamiento de pila sobre el tiempo pseudopolinómico .
Opción Cuatro: Algoritmos Aleatorizados
Si un problema es NP- hard y P ≠ NP , entonces no hay un algoritmo determinista que pueda resolver ese problema en el peor momento polinomial. ¿Pero qué pasa si permitimos algoritmos que introducen aleatoriedad? Si estamos dispuestos a conformarnos con un algoritmo que dé una buena respuesta a la expectativa , entonces a menudo podemos obtener respuestas relativamente buenas a los problemas de NP en poco tiempo.
Como ejemplo, considere el problema de corte máximo . En este problema, se le da un gráfico no dirigido y desea encontrar una manera de dividir los nodos en el gráfico en dos grupos A y B no vacíos con el número máximo de bordes que se ejecutan entre los grupos. Esto tiene algunas aplicaciones interesantes en física computacional (desafortunadamente, no las entiendo en absoluto, pero puedes leer este documento para ver algunos detalles sobre esto). Se sabe que este problema es NP- difícil, pero hay un algoritmo de aproximación aleatorio simple para ello. Si solo lanza cada nodo en uno de los dos grupos completamente al azar, terminará con un corte que, a la espera, se encuentra dentro del 50% de la solución óptima.
Al regresar a SAT, muchos de los solucionadores de SAT modernos utilizan cierto grado de aleatoriedad para guiar la búsqueda de una tarea satisfactoria. Los algoritmos WalkSAT y GSAT , por ejemplo, funcionan seleccionando una cláusula aleatoria que actualmente no está satisfecha y tratando de satisfacerla cambiando el valor de verdad de una variable. Esto a menudo guía la búsqueda hacia una asignación satisfactoria, lo que hace que estos algoritmos funcionen bien en la práctica.
Resulta que hay una gran cantidad de problemas teóricos abiertos sobre la capacidad de resolver problemas con problemas de NP mediante algoritmos aleatorios. Si tiene curiosidad, consulte la clase de complejidad BPP y el problema abierto de su relación con NP .
Opción Cinco: Algoritmos Parametrizados
Algunos problemas de NP- difícil toman en múltiples entradas diferentes. Por ejemplo, el problema del camino largo toma como entrada un gráfico y una longitud k, luego pregunta si hay un camino simple de longitud k en el gráfico. El problema de la suma de subconjuntos toma como entrada un conjunto de números y un número objetivo k, luego pregunta si hay un subconjunto de los números que dds hasta exactamente k.
Curiosamente, en el caso del problema del camino largo, hay un algoritmo (el algoritmo de codificación de colores ) cuyo tiempo de ejecución es O ((n 3 log n) · b k ), donde n es el número de nodos, k es la longitud de El camino solicitado, y b es algo constante. Este tiempo de ejecución es exponencial en k, pero solo es polinomial en n, el número de nodos. Esto significa que si k es fijo y conocido de antemano, el tiempo de ejecución del algoritmo en función del número de nodos es solo O (n 3 log n), que es un polinomio bastante bueno. De manera similar, en el caso del problema de suma de subconjuntos, hay un algoritmo de programación dinámico cuyo tiempo de ejecución es O (nW), donde n es el número de elementos del conjunto y W es el peso máximo de esos elementos. Si W se fija por adelantado como alguna constante, entonces este algoritmo se ejecutará en el tiempo O (n), lo que significa que será posible resolver exactamente la suma de los subconjuntos en el tiempo lineal.
Ambos algoritmos son ejemplos de algoritmos parametrizados , algoritmos para resolver problemas difíciles de NP que dividen la dureza del problema en dos partes: una pieza "dura" que depende de algún parámetro de entrada al problema, y una pieza "fácil" que Escala con gracia con el tamaño de la entrada. Estos algoritmos pueden ser útiles para encontrar soluciones exactas a los problemas de problemas de NP cuando el parámetro en cuestión es pequeño. El algoritmo de codificación de colores mencionado anteriormente, por ejemplo, ha demostrado ser bastante útil en la práctica en biología computacional.
Sin embargo, algunos problemas se conjeturan para no tener ningún algoritmo parametrizado agradable. Por ejemplo, se sospecha que la coloración de gráficos no tiene algoritmos parametrizados eficientes. En los casos en que existen algoritmos parametrizados, a menudo son bastante eficientes, pero no puede confiar en ellos para todos los problemas.
Para obtener más información sobre los algoritmos parametrizados, consulte esta pregunta anterior sobre Desbordamiento de pila .
Opción Seis: Algoritmos rápidos de tiempo exponencial
Los algoritmos de tiempo exponencial no se escalan bien: sus tiempos de ejecución se aproximan a la vida útil del universo para entradas tan pequeñas como 100 o 200 elementos.
Qué sucede si necesita resolver un problema de NP- difícil, pero sabe que la entrada es razonablemente pequeña; digamos, quizás su tamaño sea entre 50 y 70. Los algoritmos estándar de tiempo exponencial probablemente no serán lo suficientemente rápidos para resolver estos problemas . ¿Qué sucede si realmente necesita una solución exacta al problema y los otros enfoques aquí no lo eliminan?
En algunos casos, hay algoritmos de tiempo exponencial "optimizados" para problemas de NP- difícil. Estos son algoritmos cuyo tiempo de ejecución es exponencial, pero no tan malo como la solución ingenua. Por ejemplo, un algoritmo simple de tiempo exponencial para el problema de los 3 colores (dado un gráfico, determina si puede colorear los nodos uno de los tres colores para que los puntos finales de los bordes no sean del mismo color) podría verificar cada forma posible de colorear Los nodos en la gráfica, comprobando si alguno de ellos tiene 3 colores. Hay 3 n formas posibles de hacer esto, por lo que en el peor de los casos, el tiempo de ejecución de este algoritmo será O (3 n · poly (n)) para un pequeño polinomio poly (n). Sin embargo, al usar trucos y técnicas más inteligentes, es posible desarrollar un algoritmo para la colorabilidad de 3 colores que se ejecuta en el tiempo O(1.3289n) . Este sigue siendo un algoritmo de tiempo exponencial, pero es un algoritmo de tiempo exponencial mucho más rápido. Por ejemplo, 3 19 es aproximadamente 10 9 , por lo que si una computadora puede hacer mil millones de operaciones por segundo, puede usar nuestro algoritmo de fuerza bruta inicial para (en términos generales) resolver 3 colores en gráficos con hasta 19 nodos en un segundo . Usando el algoritmo exponencial en tiempo O ((1.3289 n ), podríamos resolver instancias de hasta aproximadamente 73 nodos en aproximadamente un segundo. Eso es una gran mejora: hemos aumentado el tamaño que podemos manejar en un segundo por más de un factor ¡de tres!
Como otro ejemplo famoso, considere el problema del vendedor ambulante. Hay una solución obvia de O (n! · Poly (n)) para TSP que funciona al enumerar todas las permutaciones de los nodos y al probar las rutas que resultan de esas permutaciones. Sin embargo, al usar un algoritmo de programación dinámica similar al utilizado por el algoritmo de codificación por colores, es posible mejorar el tiempo de ejecución a "solo" O (n 2 2 n ). ¡Dado que 13! es de aproximadamente mil millones, la solución ingenua le permitiría resolver TSP para gráficos de 13 nodos en aproximadamente un segundo. A modo de comparación, la solución DP le permite resolver TSP en gráficos de 28 nodos en aproximadamente un segundo.
Estos rápidos algoritmos de tiempo exponencial son a menudo útiles para aumentar el tamaño de las entradas que se pueden resolver exactamente en la práctica. Por supuesto, todavía se ejecutan en tiempo exponencial, por lo que estos enfoques generalmente no son útiles para resolver casos de problemas muy grandes.
Conclusión
Si necesita resolver un problema de NP- difícil, ¡no se desespere! Hay muchas opciones disponibles que pueden hacer que su problema intratable sea mucho más accesible. Ninguna de las técnicas anteriores funciona en todos los casos, pero al usar una combinación de estos enfoques, generalmente es posible progresar incluso cuando se enfrenta a la resistencia a la NP .
¡Espero que esto ayude!