Probablemente, todos se enfrentaron al hecho de que tenían que enfrentarse a una tarea difícil, cuya solución no se pudo encontrar, no solo de inmediato, sino incluso después de largas y difíciles horas de trabajo o días. Hoy hablaremos sobre una de las clases de tales problemas: NP-complete.
En general, ¿es realista cumplir con estas tareas en la vida diaria? De hecho, surgen en una gran cantidad de casos: combinatoria, gráficos y redes, ejecución de fórmulas lógicas, trabajo con mapas, cargas óptimas, mapas, problemas de optimización discreta, encontrar las secuencias más largas, encontrar sumas iguales, ¡y muchos problemas de conjuntos! Y esta no es una lista completa.
Debajo del corte hay una guía informal: cómo comprender que puede tener un problema de NP frente a usted y qué hacer si esto es exactamente lo que resultó ser. Hoy atacamos esta cuestión desde el punto de vista práctico.
Asegúrate de que ella realmente esté frente a ti.
¿Cómo saber cuándo se enfrenta a un problema NP-completo? Primero, la heurística de detección más simple es una búsqueda a través de problemas NP-completos ya conocidos para determinar algo similar, existen muchas listas de este tipo, por ejemplo .
En segundo lugar, considere las siguientes propiedades de las tareas:
- Necesitamos elegir una solución en la que n elementos del espacio exp (n)
- Si ya tiene una solución de longitud n de este espacio, se puede verificar fácilmente (polinomialmente)
- La elección de uno de los elementos de decisión (puede) afecta la elección de todos los demás (no necesariamente todos).
- En el peor de los casos, las opciones siempre se pueden enumerar, considerando todo el espacio exponencial mediante una simple enumeración.
- Los parámetros n - la longitud de la solución o el espacio en sí no tienen un valor fijo, es decir, no estamos hablando del tablero de ajedrez de 8 por 8 siempre fijo, sino de la forma general del problema N-by-N.
Lea más sobre las propiedades de los problemas NP-completos aquí y aquí .
Un ejemplo de trabajo en esta lista
¡Démosle un ejemplo simple sobre un problema que fue aprobado recientemente como NP-completo!
Basado en los materiales del artículo. Debe colocar N reinas en un tablero de tamaño N por N, siempre que ya estén colocadas K <= N en el tablero (imagen del artículo científico original)
Primero, observe que un problema muy similar con cuadrados latinos parcialmente restringidos NP está completo.
Y luego revisamos la lista:
- Necesitamos encontrar N reinas en el espacio exp (N) (= N ^ 2 * (N ^ 2-1) * ....).
- La solución de N reinas se verifica trivialmente: para cada reina, debe verificar las diagonales, verticales y líneas horizontales.
- Establecer uno invalida la elección de varios otros, es decir, existen dependencias entre los elementos de la solución (no se pueden organizar las reinas de forma independiente).
- Aquí puede resolver el problema mediante la fuerza bruta para un tablero elegido arbitrariamente en exp (N): colocamos el primero en el primero en la posición (i, j), el segundo en cualquier otro desocupado, y así sucesivamente. El retroceso está garantizado para encontrar una solución.
- El problema no tiene parámetros fijos, es decir, se formula en forma general y, a medida que N crece, también lo hace la complejidad.
Tenga en cuenta que uno de los elementos de la lista falla si siempre se sabe que el tablero está limpio y la tarea se vuelve trivial.
Además, es un enfoque práctico condicional: una heurística para detectar problemas NP-completos (con todos los pros y contras).
Mezcla
Fuente
¿Por qué, teniendo a mano problemas similares, no es fácil entender formalmente que tenemos un problema NP? ¡Realmente necesitamos mostrarle un problema NP al nuestro, entonces sabremos con certeza que nuestro problema es NP-difícil! Y si pudiéramos simularlo, como en la lista anterior, entonces está completo, es decir, al menos NP y no más que NP, de hecho “el más difícil entre los problemas NP” (como el resto del NP-completo).
Está bien, ¿lo necesitamos? En realidad, no. Si, después de todas las comprobaciones, es sencillo y directo que se enfrenta a un problema de NP, no es necesario que demuestre nada a menos que esté escribiendo un artículo científico.
Y necesita (hablaremos de esto a continuación):
- simule su tarea utilizando sistemas que resuelvan dichas tareas;
- encuentre una solución que funcione lo suficientemente rápido en su caso;
- encuentre una solución aproximada que nos satisfaga.
¡No te rindas!
¡Lo más importante es evaluar dimensiones-parámetros y escenarios realistas!
xkcd.com/287
Por ejemplo, sabe que a pesar de que los valores de los parámetros no son fijos, el condicional N <100 no se implementa en todos los escenarios prácticos, lo que significa que la enumeración condicional puede ser una solución real para usted.
Debe determinar usted mismo: ¿cuáles son mis valores reales de los parámetros que son posibles y que realmente entran en el sistema, cuál es la distribución general y las características de los datos, qué es real y qué no? ¿Necesitamos la solución más óptima? Repasemos estos puntos.
Distribución de datos de entrada
O a pesar del hecho de que, en el caso general, los datos de entrada pueden ser cualquiera, pero de nuevo para el ejemplo de las reinas, normalmente una reina es fija o incluso ninguna. Esto significa que el 90% de las veces puede usar una solución muy simple y solo llamar a una compleja en casos extremos.
Un ejemplo cuando, en promedio, todas las combinaciones habituales son simples: el problema de complementar las reinas: sabemos que las heurísticas DFS + condicionales pueden, en la mayoría de los casos, encontrar soluciones muy rápidamente, y solo en situaciones muy no estándar puede ser extremadamente difícil.
A continuación se muestra un ejemplo de cómo se evaluó la solución para un problema de mosaico NP-completo muy especializado frente a un método general para modelar una clase completa de tales problemas utilizando técnicas de programación lógica:
(del artículo Factorización de datos relacionales (Paramonov, Sergey; van Leeuwen, Matthijs; De Raedt, Luc: Factorización de datos relacionales, Aprendizaje automático, volumen 106))
En primer lugar, la velocidad de la solución especial LTM-k y el método general es significativamente diferente. Por lo tanto, una solución para este tipo de problema utilizando heurística puede resolver este problema por completo.
En segundo lugar, al sacrificar la calidad de la solución, el método de aproximación general dio una velocidad muy similar.
Heurística y aproximación
La última y más poderosa herramienta es utilizar sistemas de modelado de problemas NP-complete como la Programación de conjuntos de respuestas .
Más sobre lenguajes de programación lógica.
Por ejemplo, la solución al problema de colocación de la reina se verá así:
% domain
row(1..n).
column(1..n).
% alldifferent: guess a solution
1 { queen(X,Y) : column(Y) } 1 :- row(X).
1 { queen(X,Y) : row(X) } 1 :- column(Y).
% remove conflicting answers: check this solution
:- queen(X1,Y1), queen(X2,Y2), X1 < X2, Y1 == Y2.
:- queen(X1,Y1), queen(X2,Y2), X1 < X2, Y1 + X1 == Y2 + X2.
:- queen(X1,Y1), queen(X2,Y2), X1 < X2, Y1 - X1 == Y2 - X2.
Habiendo realizado un experimento simple para encontrar soluciones para un número diferente de reinas N, obtenemos lo siguiente: a lo largo del eje X - reinas, a lo largo de Y - el tiempo por segundo para encontrar una solución:
Vemos que a pesar de que el crecimiento del tiempo claramente no es polinomial (lo cual es lógico), hacemos un buen trabajo con un número adecuado de reinas y tamaños de tablero.
Entonces, si sabemos qué tamaños de placa son reales para nosotros, podemos entender cómo esta solución exacta es aceptable para nosotros en un sistema real.
conclusiones
Repasemos las ideas del artículo en forma de lista de verificación
- Determina que realmente tienes un problema de NP.
- Comprenda qué son los valores de parámetros realistas y la distribución de datos.
- Intente escribir (el orden depende del desarrollador y / o la tarea):
- Una solución heurística precisa (basada en nuestro análisis): ¿será lo suficientemente rápida?
- — ?
- NP- — ? , CPU ? .
- : , .
- — , — . !
:
