algorithm - ruta - ¿Cómo entender el problema de la mochila es NP-completo?
problema de la mochila python (7)
Sabemos que el problema de la mochila se puede resolver en O (nW) complejidad mediante programación dinámica. Pero decimos que este es un problema NP completo. Siento que es difícil de entender aquí.
(n es la cantidad de elementos. W es el volumen máximo).
El tamaño de la entrada es log(W) bits para el peso (y O(n) para "valor" y "peso" arrays).
Entonces, el tamaño de entrada de peso es j = log(W) (y no meramente W ). Entonces, W = 2ʲ (como se usa binario).
La complejidad final es O(n * W)
Este
O(n * W)puede reescribirse comoO(n * 2ʲ), que es exponencial en el tamaño de la entrada.
Entonces, esta solución no es polinómica.
En el problema 0/1 de la mochila, necesitamos 2 entradas (1 matriz y 1 entero) para resolver este problema:
- una matriz de n elementos: [n1, n2, n3, ...], cada elemento con su índice de valor e índice de peso.
- entero W como peso máximo aceptable
Supongamos que n = 10 y W = 8:
- n = [n1, n2, n3, ..., n10]
- W = 1000 en término binario (4 bits de largo)
entonces la complejidad del tiempo T (n) = O (nW) = O (10 * 8) = O (80)
Si duplica el tamaño de n :
n = [n1, n2, n3, ..., n10 ] -> n = [n1, n2, n3, ..., n20 ]
entonces la complejidad del tiempo T (n) = O (nW) = O (20 * 8) = O (160)
pero al duplicar el tamaño de W , no significa W = 20, pero la longitud es dos veces larga:
W = 1000 -> W = 10000000 en términos binarios (8 bits de longitud)
entonces T (n) = O (nW) = O (10 * 128) = O (1280)
el tiempo necesario aumenta en términos exponenciales, por lo que es un problema NPC.
Esto se debe a que el problema de la mochila tiene una solución pseudopolinomial y, por lo tanto, se denomina NP-Complete débilmente (y no fuertemente NP-Complete ).
Para comprender NP-completeness , debe aprender un poco de la teoría de la complejidad. Sin embargo, básicamente, es NP-completo porque un algoritmo eficiente para el problema de la mochila también sería un algoritmo eficiente para SAT , TSP y el resto.
Puede leer esta breve explicación: NP-Completitud de Knapsack .
Todo depende de qué parámetros coloques dentro de O(...) .
Si el peso objetivo está limitado por el número W , entonces el problema tiene una complejidad O(n*W) , como usted mencionó.
Pero si los pesos son demasiado grandes y necesita un algoritmo con complejidad independiente de W , entonces el problema es NP-completo. ( O(2^n*n) en la mayoría de las implementaciones ingenuas).
O(n*W) parece un tiempo polinomial, pero no lo es, es un pseudo-polynomial .
La complejidad del tiempo mide el tiempo que toma un algoritmo en función de la longitud en bits de su entrada. La solución de programación dinámica es de hecho lineal en el valor de W , pero exponencial en la longitud de W , ¡y eso es lo que importa!
Más precisamente, la complejidad temporal de la solución dinámica para el problema de la mochila está básicamente dada por un bucle anidado:
// here goes other stuff we don''t care about
for (i = 1 to n)
for (j = 0 to W)
// here goes other stuff
Por lo tanto, la complejidad del tiempo es claramente O(n*W) .
¿Qué significa aumentar linealmente el tamaño de la entrada del algoritmo? Significa utilizar conjuntos de elementos progresivamente más largos (por lo que n , n+1 , n+2 , ...) y W progresivamente más largos (entonces, si W es x bits de largo, después de un paso usamos x+1 bits, luego x+2 bits, ...). Pero el valor de W crece exponencialmente con x , por lo que el algoritmo no es realmente polinomial, es exponencial (pero parece ser un polinomio, de ahí el nombre: "pseudo-polinomio").