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

80

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.)

algorithm complexity-theory cnhk
quelle
Diese Quora-Antwort verwendet ein Beispiel, das sehr klare Argumente zeigt, die Sie zu einem Widerspruch und Verständnis dieses Themas führen
DanSkeel

Antworten:

45

O(n*W)sieht aus wie eine Polynomzeit, ist es aber nicht , es ist ein Pseudopolynom .

Die Zeitkomplexität misst die Zeit, die ein Algorithmus als Funktion der Länge in Bit seiner Eingabe benötigt. Die dynamische Programmierlösung ist zwar linear im Wert vonW , aber exponentiell in der Länge vonW - und darauf kommt es an!

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

// 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 klar O(n*W).

Was bedeutet es, die Größe der Eingabe des Algorithmus linear zu erhöhen? Es bedeutet , unter Verwendung von zunehmend längere Element - Arrays (so n, n+1, n+2, ...) und mehr progressiv W(so, wenn Wist xBit lang, nach einem Schritt , den wir verwenden , x+1Bits, dann x+2Bits, ...). Aber der Wert von Wwächst exponentiell mit x, daher ist der Algorithmus nicht wirklich polynomisch, sondern exponentiell (aber es sieht so aus, als wäre er polynomisch, daher der Name: "Pseudo-Polynom").

Weitere Referenzen

Giuseppe Cardone
quelle
2
Es gibt zwei Möglichkeiten, die Größe von Zahlen zu messen. Angesichts der Zahlen 10 und 1000 kann man sagen, dass 1000 entweder doppelt so groß (in Anzahl der Zeichen) oder hundertmal so groß ist. Da die Differenz exponentiell ist, können Sie einen Algorithmus verwenden, dessen Polynom gegen die numerische Größe und exponentiell gegen die Anzahl der Bits gemessen wird.
David Thornley
4
Ich sehe nicht, dass die Anzahl der Bits in der Codierung überhaupt etwas mit dieser Frage zu tun hat. Ich verstehe, wie die Anzahl der Bits die Komplexität der Ganzzahlfaktorisierung beeinflusst, da die einzelne Ganzzahl Ihre "Eingabe" ist. Die Zahlen Wund nhier geben jedoch die Anzahl der Schleifeniterationen an. Sie können sie beliebig codieren, und diese Schleife wird immer noch wiederholt n * W. Ich glaube, der Grund für dieses "Pseudopolynom" ist, ndass die tatsächliche Eingabegröße Wviel größer nsein kann und daher nicht als Konstante behandelt werden kann.
The111
4
Um Ihnen das Verständnis zu erleichtern 1) Betrachten Sie eine forSchleife von 1bis n(wo nist die Eingabe); In diesem Fall beträgt die Größe der Eingabe immer noch etwa 40 Bit, wenn Ihre Schleife 10 ^ 12 Iterationen ausführt. Die Anzahl der Iterationen wächst schneller als die Anzahl der Bits, die die Eingabe codieren sollen. Die zeitliche Komplexität ist nicht linear. 2) Betrachten Sie erneut eine forSchleife, die über ein Eingabearray (mit Größe n) von 1bis iteriert n. Wenn Sie 10 ^ 12 Iterationen haben, bedeutet dies, dass Ihr Array 10 ^ 12 Elemente enthält. Die Anzahl der Iterationen wächst mit der gleichen Geschwindigkeit wie die Größe der Eingabe. Zeit kompl. ist linear.
Zsolt Safrany
4
@AkshayLAradhya Wenn wir mein Beispiel betrachten, fügen wir der Eingabe einfach ein zusätzliches Bit hinzu. Damit verdoppeln wir die Anzahl der Iterationen (zusätzliche 10 ^ 12 Iterationen), aber die Länge der Eingabe wurde nur um eine länger. Und mit dem nächsten zusätzlichen Bit erhalten wir noch mehr zusätzliche Iterationen. Und so weiter. Daher wächst die "Anzahl der Iterationen schneller als die Anzahl der Bits [benötigt], um die Eingabe zu codieren", wobei die Eingabe die Anzahl der Iterationen darstellt. Ich habs? :-)
Zsolt Safrany
2
Die Sache, die es für mich zum Klicken gebracht hat, war, dass für die Eingaben des Rucksackproblems n keine Zahl ist, es sind tatsächliche Dinge, während W eine Zahl ist. Sie können das Rucksackproblem für Gewicht 10 und die Anzahl der Dinge 6 nicht lösen. Sie brauchen tatsächlich n, um Dinge zu sein ... ein Array, das wächst. Die Art und Weise, wie wir die GRÖSSE von n (ein Array von Dingen) darstellen, ist mit einer Zahl, aber die Art und Weise, wie wir die GRÖSSE von W (eine Zahl) darstellen, ist mit Bits.
Amoffat
24

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 ist die Zeitkomplexität T (n) = O (nW) = O (10 · 8) = O (80)

Wenn Sie die Größe von n verdoppeln :

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

also Zeitkomplexität T (n) = O (nW) = O (20 · 8) = O (160)

Wenn Sie jedoch die Größe von W verdoppeln , bedeutet dies nicht, dass W = 16 ist, sondern dass die Länge doppelt so lang ist:

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

also ist T (n) = O (nW) = O (10 · 128) = O (1280)

Die benötigte Zeit nimmt exponentiell zu, so dass es sich um ein NPC-Problem handelt.

YoEugene
quelle
Danke YoEugene, ich sehe endlich den Punkt hier! Der Punkt hier ist also wirklich, dass die Komplexität exponentiell zur Eingangsgröße ist, die in diesem Fall die Bitlänge von W ist. Dasselbe passiert, wenn wir diskutieren, ob eine Zahl N eine Primzahl ist, die Eingabe ist wirklich die Bitlänge von N, Wir machen zwar N Schritte und die Komplexität O (N), aber es ist immer noch ein Pseudopolynom. Wenn wir dagegen versuchen, eine Zahl in einem Array der Länge N zu finden, ist die Eingabe tatsächlich N, sodass die Komplexität von O (N) wirklich linear ist.
Yeelan
7

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

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

Aber wenn die Gewichte viel zu groß sind und Sie einen Algorithmus mit unabhängiger Komplexität benötigen W, ist das Problem NP-vollständig. ( O(2^n*n)in der naivsten Umsetzung).

Nikita Rybak
quelle
Was ist mit anderen dynamischen Programmierproblemen? Zum Beispiel kann das längste gemeinsame Teilsequenzproblem in O (L_1 * L_2) Zeit gelöst werden? Können wir sagen, dass es kein Polynom ist?
cnhk
@cnhk Sieht so aus, als hätte es eine polynomielle Komplexität, O (n ^ 2). Es gibt jedoch alle Arten von DP-Algorithmen, zum Beispiel diejenigen, die an allen Teilmengen einer bestimmten Menge (2 ^ n Kombinationen) arbeiten. Daher würde ich nicht sagen, dass jedes DP-Problem in Polynomzeit gelöst werden kann.
Nikita Rybak
3

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

Die eingegebene Gewichtsgröße 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)

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

Diese Lösung ist also kein Polynom.

kaushalpranav
quelle
0

Um die NP-Vollständigkeit zu verstehen , muss man ein bisschen Komplexitätstheorie lernen. Im Grunde ist es jedoch NP-vollständig, da ein effizienter Algorithmus für das Rucksackproblem auch ein effizienter Algorithmus für SAT , TSP und den Rest wäre.

Pontus Gagge
quelle