language agnostic - problems - ¿Por qué el problema de la mochila es pseudopolinomial?
knapsack problem java (4)
Sé que Knapsack es NP-completo, mientras que DP lo puede resolver. Dicen que la solución DP es pseudo-polynomial , ya que es exponencial en la "longitud de entrada" (es decir, el número de bits necesarios para codificar la entrada). Desafortunadamente no lo entendí ¿Alguien puede explicarme esa cosa pseudo-polynomial lentamente?
El tiempo de ejecución del algoritmo Knapsack no solo está vinculado al tamaño de la entrada (n - el número de elementos) sino también a la magnitud de la entrada (W - la capacidad de la mochila) O (nW) que es exponencial en la forma representado en la computadora en binario (2 ^ n). La complejidad computacional (es decir, cómo se procesa dentro de una computadora a través de bits) solo se refiere al tamaño de las entradas, no a sus magnitudes / valores .
Ignore la lista valor / peso por un momento. Digamos que tenemos una instancia con capacidad de mochila 2. W tomaría dos bits en los datos de entrada. Ahora aumentaremos la capacidad de la mochila a 4, manteniendo el resto de la entrada. Nuestra entrada solo ha crecido en un bit, pero la complejidad computacional se ha duplicado. Si aumentamos la capacidad a 1024, tendríamos solo 10 bits de la entrada para W en lugar de 2, pero la complejidad se ha incrementado en un factor de 512. La complejidad del tiempo crece exponencialmente en el tamaño de W en representación binaria (o decimal) .
Otro ejemplo simple que me ayudó a entender el concepto de pseudo-polinomio es el ingenuo algoritmo de prueba de primalidad. Para un número dado n, estamos comprobando si está dividido de manera uniforme por cada número entero en el rango 2..√n, entonces el algoritmo toma √ (n-1) pasos. Pero aquí, n es la magnitud de la entrada, no su tamaño.
Now The regular O(n) case
Por el contrario, la búsqueda de una matriz para un elemento dado se ejecuta en tiempo polinomial: O (n). Lleva como máximo n pasos y aquí n es el tamaño de la entrada (la longitud de la matriz).
[ mira aquí ]
Cálculo de los bits necesarios para almacenar el número decimal
El tiempo de ejecución es O (NW) para un problema de mochila sin límites con N elementos y mochila de tamaño W. W no es polinomial en la longitud de la entrada sin embargo, que es lo que lo hace pseudo- polinomial.
Considera W = 1,000,000,000,000. Solo se necesitan 40 bits para representar este número, por lo que el tamaño de entrada = 40, pero el tiempo de ejecución computacional usa el factor 1,000,000,000,000 que es O (2 40 ).
Por lo tanto, se dice con mayor precisión que el tiempo de ejecución es O (N.2 bits en W ), que es exponencial.
Ver también:
En la mayoría de nuestros problemas, estamos lidiando con grandes listas de números que se ajustan cómodamente dentro de los tipos de datos estándar int / float. Debido a la forma en que la mayoría de los procesadores están diseñados para manejar números de 4 a 8 bytes a la vez sin costo adicional (en relación con los números que caben, digamos, 1 byte), rara vez encontramos un cambio en el tiempo de ejecución al escalar nuestros números o dentro de los rangos que encontramos en problemas reales, por lo que el factor dominante sigue siendo simplemente la cantidad de puntos de datos, los factores n o m a los que estamos acostumbrados.
(Puede imaginarse que la notación Big-O oculta un factor constante que divide 32 o 64 bits por dato, dejando solo el número de puntos de datos cada vez que cada uno de nuestros números encaja en tantos bits o menos )
Pero intente volver a trabajar con otros algoritmos para actuar en conjuntos de datos que involucren grandes ints (números que requieren más de 8 bytes para representarlos) y vea qué hace eso con el tiempo de ejecución. La magnitud de los números involucrados siempre hace una diferencia, incluso en los otros algoritmos como el género binario, una vez que se expande más allá del buffer de seguridad, los procesadores convencionales nos dan "gratis" al manejar lotes de 4 a 8 bytes.
El truco con el algoritmo Knapsack que discutimos es que es inusualmente sensible (en relación con otros algoritmos) a la magnitud de un parámetro en particular, W. Agregue un bit a W y duplique el tiempo de ejecución del algoritmo. No hemos visto ese tipo de respuesta dramática a los cambios en el valor en otros algoritmos antes de este, por lo que podría parecer que tratamos a Knapsack de manera diferente, pero ese es un análisis genuino de cómo responde de manera no polinómica. a cambios en el tamaño de entrada.
La forma en que entiendo esto es que la capacidad habría sido O (W) si la entrada de capacidad fuera una matriz de [1,2, ..., W] , que tiene un tamaño de W. Pero la capacidad de entrada no es una matriz de números, en cambio, es un entero único. La complejidad del tiempo se trata de la relación con el tamaño de la entrada. El tamaño de un entero NO es el valor del número entero, sino el número de bits que lo representa. Posteriormente, convertimos este entero W en una matriz [1,2, ..., W] en el algoritmo, lo que lleva a las personas a pensar erróneamente que W es el tamaño, pero esta matriz no es la entrada, el número entero sí lo es.
Piense en la entrada como "una serie de cosas", y el tamaño como "cuántas cosas en la matriz". La entrada del elemento es en realidad una matriz de n elementos en la matriz, de modo que size = n. La entrada de capacidad NO es una matriz de números W en ella, sino un entero único , representado por una matriz de bits de registro (W). Aumente el tamaño de la misma en 1 (agregando 1 bit significativo), W dobla así que el tiempo de ejecución se duplica, de ahí la complejidad del tiempo exponencial.