Knapzakprobleem

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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

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 definities[bewerken]

Er is de beschikking over objecten met gewicht a_1,\dots,a_m en een maximum gewicht 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_1x_1 + a_2x_2 + \dots + a_mx_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 \le c, \quad \quad 0 \le a_i \le 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[bewerken]

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[bewerken]

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 powerset van de lijst van objecten gemaakt: de verzameling van alle subverzamelingen.

Greedy Algoritme[bewerken]

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 maximum grootte 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], [g2]

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[bewerken]

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 O(nG).

Merkle en Hellman Trapdoor Knapsack methode[bewerken]

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_ix_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[bewerken]

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