WikiDer > Rucksackproblem

Beispiel für ein Rucksackproblem.

Es Rucksackproblem ist ein NP-vollständig Problem in der Mathematik, Informatik und Kryptographie. Das Rucksackproblem ergibt sich aus dem folgenden Problem:

Bestimmen Sie anhand einer Sammlung von Objekten, jedes mit Gewicht und Wert, welche (Unter-)Menge von Objekten in der Tornister, das Gesamtgewicht unter dem Grenzwert halten und den Gesamtwert maximieren.

Verschiedene Definitionen

Objekte mit Gewicht sind verfügbar ${displaystyle a_{1},dots ,a_{m}}$ und ein maximales Gewicht ${displaystyle b}$. Finden Sie jetzt eine Sammlung von Indizes

${displaystyle Isubseteq {1,2,dots,m}}$ mit ${Anzeigestilsumme _{iin I}a_{i}=b}$

Andererseits kann das Problem formuliert werden als: finde einen Vektor ${displaystyle {unterstreichen {x}}}$ aus Nullen und Einsen, mit

${displaystyle a_{1}x_{1} a_{2}x_{2} Punkte a_{m}x_{m}=b}$

Da das Rucksackproblem NP-vollständig ist, gibt es keine besseren Methoden zur Lösung des Problems als alle ${Displaystil 2^{m}}$ Möglichkeiten für ${displaystyle {unterstreichen {x}}}$ versuchen. Es ist auch unmöglich vorherzusagen, ob eine Lösung gefunden werden kann. Wenn ein Lösungsvektor ${displaystyle {unterstreichen {x}}}$ gefunden wird, kann es in polynomieller Zeit verifiziert werden.

Andere Definitionen, einschließlich des Werts von Objekten, sind:

Begrenztes Rucksackproblem, in dem die Nummer jedes Objekts, ${displaystyle a_{i}}$, ist auf einen bestimmten Wert begrenzt, ${displaystyle b_{i}}$,:

maximieren ${Anzeigestilsumme _{i=1}^{m}p_{i}a_{i}.}$

so dass ${displaystyle sum _{i=1}^{m}w_{i}a_{i}leq c,quad quad 0leq a_{i}leq b_{i},quad i=1,dots ,m.}$

Mit diesem ${displaystyle m}$ die Anzahl der Objekte. Beliebiges Objekt ${Anzeigestil i}$ hat Wert ${displaystyle p_{i}}$ und Gewicht ${displaystyle w_{i}}$. Das maximal zu tragende Gewicht beträgt ${Anzeigestil c}$

Unbegrenztes Rucksackproblem, in dem es keine Beschränkungen für den Wert der Anzahl jedes Objekts gibt.

Algorithmen

Es gibt derzeit keine Algorithmus für dieses Problem bekannt, dass:

• Gibt immer die richtige Antwort und
• Benötigt weniger als exponentielle Zeit.

rohe Gewalt

Es rohe Gewalt Die Lösung dieses Problems bedeutet, dass Sie alle möglichen Kombinationen von Objekten ausprobieren und sehen, welche Kombination von Objekten Ihnen das beste Ergebnis liefert. Dadurch entsteht die sogenannte Potenzmenge der Objektliste: die Menge aller Teilmengen.

Gieriger Algorithmus

EIN Gieriger Algorithmus würde die Objekte in absteigender Reihenfolge nach dem Wert-Gewichts-Verhältnis des Objekts sortieren und dann die Objekte in dieser Reihenfolge in den Rucksack legen, bis nichts mehr an ihn herankommt. Das funktioniert, hat aber den großen Nachteil, dass es bei etwas größeren Objektsammlungen sehr langsam ist.

 Sortiere die Objekte nach Wert/Gewicht (w und g): w[1]/g[1] ${displaystyle leq }$ w[2]/g[2] ${displaystyle leq }$ w[3]/g[3] ${displaystyle leq }$ ,${Punkte im Anzeigestil}$, ${displaystyle leq }$ w[n]/g[n] Nimm S die leere Menge; Gewicht = 0

    für i=1 bis n wenn Gewicht g[i] <= G dann Stoppobjekt i in S; Gewicht = g[i] fi endfür Ausgabe S

Der obige Algorithmus funktioniert jedoch nicht richtig:

Nehmen Sie als maximale Größe des Rucksacks den Wert G = 6 und die folgenden zwei Gegenstände:

g[1]= 1; w[1]=2
g[2]= 6; w[2]=6

Die obige Heuristik liefert die Lösung, dass der Rucksack (mit einem maximalen Gewicht G von 6) nur Objekt 1 mit Wert 2 enthält, während die Lösung mit Objekt 2 mit Wert 6 optimal ist:

Wert/Gewichtsverhältnis von g[1] ist: 2/1 = 2
Wert/Gewichtsverhältnis von g[2] ist: 6/6 = 1
Sortieren nach: g[1], g[2]

Dann so viel wie möglich in die Tüte geben.
Nach Objekt 1 darin bleibt noch G - g[1] = 6 - 1 = 5 für andere Objekte übrig.
Objekt 2 passt nicht mehr, daher stoppt der Algorithmus.

Eine Möglichkeit, dies zu verbessern, besteht darin, zu sehen, ob die Werte aller Objekte in S (der Ausgabe des Algorithmus) kleiner sind als der Wert des wertvollsten Elements.

Im obigen Algorithmus wird Folgendes ersetzt:

 Ausgang S

 if ( w[z] > W) then Ausgabe z else Ausgabe S fi

W ist hier der Mehrwert (der Werte) der Objekte in S, und z ist das wertvollste Element.

Wenn der Algorithmus auf diese Weise modifiziert wird, ist der Wert der Lösung immer innerhalb eines Faktors 2 des optimalen Wertes.

Dynamische Programmierung

Bei der sogenannten dynamischen Programmierung des Rucksackproblems wird in einer Tabelle festgehalten, welcher bisher beste Rucksack ist.

 table = eine Tabelle von (1..n 1) bei (0..G) für w = 0..G table[n 1, w] = 0 für i = n..1 für w = 1..G if Gewicht von Objekt i <= w then table[i,w] = max( table[i 1, w - Gewicht von Objekt i] Wert von Objekt i, table[i 1, w] ) else table[i,w] = table [i 1, w] fi return table[1, G]

Bei welchem Objekte die Liste der Objekte ist und G der maximale Wert des Rucksacks. Dieser Algorithmus geht in die Polynomialzeit O(nG), die im Grenzfall viel schneller ist als die theoretische Exponentialzeit. Der Algorithmus erfordert jedoch, dass die Gewichte diskret sind. Dies ist also keine Lösung für das vollständige theoretische Problem, aber in der Praxis können die Gewichte immer gerundet werden, um eine Lösung mit einer gewissen Richtigkeit zu finden.

Merkle und Hellman Trapdoor Knapsack Methode

Das Kodierungssystem von Merkle und Hellman basiert auf einer Anwendung des Knapsack-Problems. Es verwendet die Idee, dass das Knapsack-Problem in bestimmten Fällen leicht lösbar ist. Wir nennen den Vektor ${displaystyle {unterstreichen {a}}}$ einfach wie:

${displaystyle forall iin a_{i}>sum _{j$

Das Codiersystem funktioniert dann wie folgt:

• Erzeuge einen zufälligen einzelnen Rucksackvektor ${displaystyle {unterstreichen {a}}'}$, dieser bleibt geheim.
• Generiere eine Zufallszahl

${displaystyle m>Summe _{}a_{i}'}$ und ein zufälliges Paar ${Anzeigestil w,w^{-1}}$ mit ${displaystyle ww^{-1}=1mod m}$.

Das geht schnell über das umfangreiche Euklids Algorithmus. Auch diese Nummern werden geheim gehalten

• Das Öffentlicher Schlüssel ist jetzt der Vektor

${displaystyle {underline {a}}=(wa_{1}'mod m,wa_{2}'mod m,dots)}$.

• Nachrichten werden als Reihen binärer Vektoren dargestellt ${Anzeigestil x}$ gleich lang wie ${displaystyle {unterstreichen {a}}}$ und ${displaystyle {unterstreichen {a}}'}$

Beispiel: Wenn jemand ${displaystyle {unterstreichen {x}}}$ senden will, schnappt er sich den öffentlichen Vektor vom Empfänger, ${displaystyle {unterstreichen {a}}}$, und codiert es als ${displaystyle S=sum _{i=1}^{n}a_{i}x_{i}}$. weil ${displaystyle {unterstreichen {a}}}$ jetzt, da es kein einfacher Vektor mehr ist, vertraut man darauf ${Anzeigestil S}$ schwer von einem Lauscher zu entschlüsseln.

Der Empfänger kann die Nachricht mit seinen geheimen Informationen entschlüsseln, ${displaystyle w^{-1}}$ und ${displaystyle m}$. Damit bestimmt er

${displaystyle S'=w^{-1}Smod m=sum _{}a_{i}'x_{i}mod m}$

und weiß auch also

${Displaystyle-Summe _{}a_{i}'x_{i}}$, weil ${displaystyle m>sum _{}a_{i}'geq sum _{}a_{i}'x_{i}}$.

Damit weiß er ${displaystyle {unterstreichen {x}}}$, weil ${displaystyle {unterstreichen {a}}'}$ war einfach.

Das System ist jedoch nicht mehr verwendbar, da Adi Shamir 1982 zeigte, dass fast alles mit 1-Schritt-Verschlüsselung geknackt werden kann. Auch die mehrstufige Verschlüsselung wurde 1984 geknackt.

Verweise

• van Leijenhorst, Dick, Komplexitätstheorie: Eine kurze Einführung in 12 Vorlesungen. NORTH STAR-PUBLIKATIONEN. Version 1.2, S.204.