wake-up-neo.com

Wie ist zu verstehen, dass das Rucksackproblem NP-vollständig ist?

Wir wissen, dass das Rucksackproblem durch dynamische Programmierung in O(nW) Komplexität gelöst werden kann. Wir sagen jedoch, dass dies ein NP-vollständiges Problem ist. Ich finde es hier schwer zu verstehen.

(n ist die Anzahl der Elemente. W ist das maximale Volumen.)

algorithmcomplexity-theory
70
cnhk

O(n*W) sieht aus wie eine Polynomzeit, aber es ist nicht , es ist pseudo-polynom .

Die Zeitkomplexität misst die Zeit, die ein Algorithmus in Abhängigkeit von der Länge seiner Eingabe in Bits benötigt. Die dynamische Programmierlösung ist zwar linear im Wert von W, aber exponentiell in der Länge von W - und das ist was zählt!

Genauer gesagt wird die zeitliche Komplexität der dynamischen Lösung für das Rucksackproblem im Wesentlichen durch eine verschachtelte Schleife angegeben:

// here goes other stuff we don't care about
for (i = 1 to n)
    for (j = 0 to W)
        // here goes other stuff

Somit ist die zeitliche Komplexität eindeutig O(n*W).

Was bedeutet es, die Größe der Eingabe des Algorithmus linear zu erhöhen? Dies bedeutet, dass immer längere Elementarrays (also n, n+1, n+2, ...) und immer längere W (also, wenn W ist x Bits lang, nach einem Schritt verwenden wir x+1 Bits, dann x+2 Bits, ...). Aber der Wert von W wächst exponentiell mit x, daher ist der Algorithmus nicht wirklich polynomiell, sondern exponentiell (aber er scheint polynomiell zu sein, daher der Name: "Pseudo-Polynom").

Weitere Referenzen

41
Giuseppe Cardone

Im Rucksack-0/1-Problem benötigen wir 2 Eingänge (1 Array & 1 Ganzzahl), um dieses Problem zu lösen:

  1. ein Array von n Elementen: [n1, n2, n3, ...], jedes Element mit seinem Wertindex und Gewichtsindex.
  2. ganzzahl W als maximal zulässiges Gewicht

Nehmen wir an, n = 10 und W = 8:

  1. n = [n1, n2, n3, ..., n10]
  2. W = 1000 im binären Term (4 Bit lang)

also die zeitliche Komplexität T(n) O(nW) = O (10 * 8) = O (80)

Wenn Sie verdoppeln die Größe von n:

n = [n1, n2, n3, ..., n1] -> n = [n1, n2, n3, ..., n2]

zeitkomplexität T(n) O(nW) = O (20 * 8) = O (160)

aber wenn Sie doppelte Größe von W, bedeutet dies nicht, dass W = 16 ist, aber die Länge wird zweimal länger sein:

W = 1000 -> W = 10000000 im binären Term (8 Bit lang)

so T(n) = O(nW) = O (10 * 128) = O (1280)

die benötigte Zeit nimmt exponentiell zu, es ist also ein NPC Problem.

20
YoEugene

Es hängt alles davon ab, welche Parameter Sie in O(...) eingeben.

Wenn das Zielgewicht durch die Anzahl W begrenzt ist, hat das Problem O(n*W) Komplexität, wie Sie erwähnt haben.

Wenn die Gewichte jedoch viel zu groß sind und Sie einen Algorithmus mit einer von W unabhängigen Komplexität benötigen, ist das Problem NP-vollständig. (O(2^n*n) in der naivsten Implementierung).

6
Nikita Rybak

Dies liegt daran, dass das Rucksackproblem eine pseudo-polynomielle Lösung hat und daher schwach NP-vollständig (und nicht stark NP-vollständig).

4
Manav Kataria

Die Größe der Eingabe beträgt log(W) Bits für das Gewicht (und O(n) für die Arrays "value" und "weight").

Die Eingabegröße für weight ist also j = log(W) (und nicht nur W). Also, W = 2ʲ (Als Binär wird verwendet).

Die endgültige Komplexität ist O(n * W)

Diese O(n * W) kann als O(n * 2ʲ) umgeschrieben werden, was in der Größe der Eingabe exponentiell ist.

Diese Lösung ist also kein Polynom.

3
kaushalpranav

Sie können diese kurze Erklärung lesen: Die NP-Vollständigkeit von Knapsack .

2
dfens