Knapzakprobleem

Het knapzakprobleem is een NP-volledig probleem in de wiskunde, informatica en cryptografie. Het knapzakprobleem komt van het volgende vraagstuk:

Voorbeeld van een knapzakprobleem.

Gegeven een verzameling van objecten, elk met gewicht en waarde, bepaal welke (deel)verzameling van objecten meegenomen wordt in de knapzak, zodat het totale gewicht onder het maximum blijft en de totale waarde gemaximaliseerd wordt.

Verschillende definities

Er is de beschikking over objecten met gewicht $a_{1},\dots ,a_{m}$ en een maximumgewicht $b$. Vind nu een verzameling indices

$I\subseteq \{1,2,\dots ,m\}$ met $\sum _{i\in I}a_{i}=b$

Anderzijds is het probleem te formuleren als: vind een vector ${\underline {x}}$ van nullen en enen, met

$a_{1}x_{1}+a_{2}x_{2}+\dots +a_{m}x_{m}=b$

Omdat het knapzakprobleem NP-Volledig is, bestaan er geen betere methoden om het probleem op te lossen, dan door alle $2^{m}$ mogelijkheden voor ${\underline {x}}$ te proberen. Het is ook niet te voorspellen of een oplossing gevonden kan worden. Wel is het zo dat wanneer een oplossingsvector ${\underline {x}}$ is gevonden, deze in polynomiale tijd kan worden geverifieerd.

Overige definities, inclusief waarde van objecten, zijn:

Beperkt knapzakprobleem, waarin het nummer van elk object, $a_{i}$, wordt beperkt tot een specifieke waarde, $b_{i}$,:

Maximaliseer $\sum _{i=1}^{m}p_{i}a_{i}.$

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

met hierin $m$ het aantal objecten. Elk object $i$ heeft waarde $p_{i}$ en gewicht $w_{i}$. Het maximale gewicht dat kan worden meegenomen is $c$

Onbeperkt knapzakprobleem, waarin er geen restricties zijn op de waarde van het nummer van elk object.

Algoritmen

Er is op dit moment geen algoritme bekend voor dit probleem dat:

• Altijd het juiste antwoord geeft en,
• Minder dan exponentiële tijd nodig heeft.

Brute force

Het brute force oplossen van dit probleem wil zeggen dat je alle mogelijk combinaties van objecten probeert en kijkt met welke combinatie van objecten je het beste resultaat krijgt. Hierbij wordt de zogenaamde machtsverzameling van de lijst van objecten gemaakt: de verzameling van alle deelverzamelingen.

Greedy Algoritme

Een greedy algoritme zou de objecten in aflopende volgorde sorteren aan de hand van de waarde/gewicht-verhouding van het object, en dan de objecten in deze volgorde in de knapzak stoppen tot er niets meer bij kan. Dit werkt, maar heeft als grote nadeel dat het ontzettend traag is voor wat grotere verzamelingen objecten.

 Sorteer de objecten op waarde/gewicht (w en g): w[1]/g[1] $\leq$ w[2]/g[2] $\leq$ w[3]/g[3] $\leq$ ,$\dots$, $\leq$ w[n]/g[n]
 Neem S de lege verzameling; Gewicht = 0

  
  for i=1 to n
    if gewicht + g[i] <= G then
      Stop voorwerp i in S; gewicht += g[i]
    fi
  endfor
    
  Output S

Bovenstaand algoritme werkt echter niet goed:

Neem als maximumgrootte van de knapzak de waarde G = 6 en de volgende twee voorwerpen:

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

Bovenstaand heuristiek geeft als oplossing dat de knapzak (met maximaal gewicht G van 6) slechts object 1 met waarde 2 bevat, terwijl de oplossing met object 2 met waarde 6 optimaal is:

Waarde/gewicht ratio van g[1] is: 2/1 = 2
Waarde/gewicht ratio van g[2] is: 6/6 = 1
Sorteren als: g[1], g[2]

Vervolgens zo veel mogelijk in de zak stoppen.
Na object 1 erin is er nog G - g[1] = 6 - 1 = 5 over voor andere objecten.
Object 2 past er niet meer in, dus stopt het algoritme.

Een mogelijk manier om dit te verbeteren is om te kijken of de waarden van alle objecten in S (de uitvoer van het algoritme) opgeteld minder is dan de waarde van het meest waardevolle element.

In bovenstaand algoritme wordt het volgende vervangen:

 Output S

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

W is hierin de opgetelde waarde van (de waarden van) de objecten in S, en z is het meest waardevolle element.

Wanneer het algoritme op deze wijze wordt aangepast is de waarde van de oplossing altijd binnen een factor 2 van de optimale waarde.

Dynamic Programming

Bij het zogenaamde dynamic programming van het knapzakprobleem wordt in een tabel bijgehouden wat de beste knapzak is tot nu toe.

 tabel = een tabel van (1..n+1) bij (0..G)
 for w = 0..G
  tabel[n+1, w] = 0
 for i = n..1
  for w = 1..G
   if gewicht van object i <= w then 
    tabel[i,w] = max( tabel[i+1, w - gewicht object i] + waarde van object i, tabel[i+1, w] )
   else 
    tabel[i,w] = tabel[i+1, w]
   fi
 return tabel[1, G]

Waarbij Objecten het lijstje van objecten is en G de maximale waarde van de knapzak. Dit algoritme gaat in de polynomiale tijd O(nG), wat in de limiet veel sneller is dan de theoretische exponentiële tijd. Maar het algoritme vereist dat de gewichten discreet zijn. Dit is dus geen oplossing voor het volledige theoretische probleem, maar in de praktijk kunnen de gewichten altijd afgerond worden om zo een oplossing tot op een zekere correctheid te vinden.

Merkle en Hellman Trapdoor Knapsack methode

Het coderingssysteem van Merkle en Hellman is gebaseerd op een toepassing van het Knapzakprobleem. Het maakt gebruik van het idee dat het Knapzakprobleem in bepaalde gevallen makkelijk oplosbaar is. We noemen de vector ${\underline {a}}$ simpel als:

$\forall i\in a_{i}>\sum _{j<i}a_{j}$

Het coderingssysteem werkt dan als volgt:

• Genereer een aselecte enkelvoudige knapzakvector ${\underline {a}}'$, deze blijft geheim.
• Genereer een aselect getal

$m>\sum _{}a_{i}'$ en een aselect paar $w,w^{-1}$ met $ww^{-1}=1\mod m$.

Dit kan snel via het uitgebreide algoritme van Euclides. Ook deze getallen worden geheimgehouden

• De public key is nu de vector

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

• Boodschappen worden gerepresenteerd als rijen binaire vectoren $x$ van dezelfde lengte als ${\underline {a}}$ en ${\underline {a}}'$

Voorbeeld: Als iemand ${\underline {x}}$ wil oversturen, pakt hij de publieke vector van de ontvanger, ${\underline {a}}$, en codeert deze als $S=\sum _{i=1}^{n}a_{i}x_{i}$. Omdat ${\underline {a}}$ nu geen simpele vector meer is, vertrouwt men erop dat het $S$ moeilijk decodeerbaar is door een afluisteraar.

De ontvanger kan de boodschap decoderen door gebruik te maken van zijn geheime informatie, $w^{-1}$ en $m$. Hiermee bepaalt hij

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

en kent dan ook

$\sum _{}a_{i}'x_{i}$, want $m>\sum _{}a_{i}'\geq \sum _{}a_{i}'x_{i}$.

Hiermee kent hij ${\underline {x}}$, want ${\underline {a}}'$ was simpel.

Het systeem is echter niet meer bruikbaar omdat Adi Shamir in 1982 heeft aangetoond dat bij 1-staps codering bijna alles te kraken valt. De meertraps codering is in 1984 ook gekraakt.

Referenties

• Dr. D.C. van Leijenhorstvan Leijenhorst, Dick (2006). Complexiteitstheorie: een beknopte inleiding in 12 voordrachten. NORTH STAR PUBLICATIONS. Versie 1.2, pg.204.