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 de limiet blijft en de totale waarde gemaximaliseerd wordt.

Verschillende definitiesBewerken

Er is de beschikking over objecten met gewicht   en een maximumgewicht  . Vind nu een verzameling indices

  met  

Anderzijds is het probleem te formuleren als: vind een vector   van nullen en enen, met

 

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

Overige definities, inclusief waarde van objecten, zijn:

Beperkt knapzakprobleem, waarin het nummer van elk object,  , wordt beperkt tot een specifieke waarde,  ,:

Maximaliseer  
zodat  
met hierin   het aantal objecten. Elk object   heeft waarde   en gewicht  . Het maximale gewicht dat kan worden meegenomen is  

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

AlgoritmenBewerken

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 forceBewerken

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 AlgoritmeBewerken

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]   w[2]/g[2]   w[3]/g[3]   , ,   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 rugzak 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 rugzak (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 ProgrammingBewerken

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 methodeBewerken

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   simpel als:

 

Het coderingssysteem werkt dan als volgt:

  • Genereer een aselecte enkelvoudige knapzakvector  , deze blijft geheim.
  • Genereer een aselect getal
  en een aselect paar   met  .
Dit kan snel via het uitgebreide algoritme van Euclides. Ook deze getallen worden geheimgehouden
 .
  • Boodschappen worden gerepresenteerd als rijen binaire vectoren   van dezelfde lengte als   en  

Voorbeeld: Als iemand   wil oversturen, pakt hij de publieke vector van de ontvanger,  , en codeert deze als  . Omdat   nu geen simpele vector meer is, vertrouwt men erop dat het   moeilijk decodeerbaar is door een afluisteraar.

De ontvanger kan de boodschap decoderen door gebruik te maken van zijn geheime informatie,   en  . Hiermee bepaalt hij

 

en kent dan ook

 , want  .

Hiermee kent hij  , want   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.

ReferentiesBewerken

  • van Leijenhorst, Dick, Complexiteitstheorie: een beknopte inleiding in 12 voordrachten. NORTH STAR PUBLICATIONS. Versie 1.2, pg.204.