Problem plecakowy

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Które pudełka powinny być wybrane, aby zmaksymalizować wartość przedmiotów w plecaku i jednocześnie nie zabrać więcej niż 15 kg?

Dyskretny problem plecakowy (ang. discrete knapsack problem) jest jednym z najczęściej poruszanych problemów optymalizacyjnych. Nazwa zagadnienia pochodzi od maksymalizacyjnego problemu wyboru przedmiotów, tak by ich sumaryczna wartość była jak największa i jednocześnie mieściły się w plecaku. Przy podanym zbiorze elementów o podanej wadze i wartości, należy wybrać taki podzbiór by suma wartości była możliwie jak największa, a suma wag była nie większa od danej pojemności plecaka.

Problem plecakowy często przedstawia się jako problem złodzieja rabującego sklep – znalazł on N towarów; j–ty przedmiot jest wart c_{j} oraz waży w_{j}. Złodziej dąży do zabrania ze sobą jak najwartościowszego łupu, przy czym nie może zabrać więcej niż B kilogramów. Nie może też zabierać ułamkowej części przedmiotów (byłoby to możliwe w ciągłym problemie plecakowym).

Podobny problem pojawia się często w kombinatoryce, teorii złożoności obliczeniowej, kryptografii oraz matematyce stosowanej.

Decyzyjna wersja przedstawionego zagadnienia to pytanie "czy wartość co najmniej C może być osiągnięta bez przekraczania wagi W?"

Definicja[edytuj | edytuj kod]

Definicja formalna: mamy do dys­pozycji plecak o maksymalnej pojemności B oraz zbiór N elementów \{x_1, x_j, ..., x_N\}, przy czym każdy element ma określoną wartość c_{j} oraz wielkość w_{j}.

Dyskretny problem plecakowy (ang. 0-1 knapsack problem)

formalnie problem może być zdefiniowany:
zmaksymalizuj \sum_{j=1}^N c_j x_j.
przy założeniach: \sum_{j=1}^N w_j x_j \le B, \quad \quad x_j = 0\;\mbox{lub}\;1, \quad j=1,\dots,n.

Problem plecakowy, w którym liczba elementów danego typu jest ograniczona przez podaną wartość (ang. bounded knapsack problem).

Formalnie:
zmaksymalizuj \sum_{j=1}^N c_j x_j.
przy założeniach: \sum_{j=1}^N w_j x_j \le B, \quad \quad 0 \le x_j \le b_j, \quad j=1,\dots,n.

Można rozważać także przypadek w którym nie ma wartości ograniczającej liczbę elementów danego typu (ang. unbounded knapsack problem).

W ciągłym problemie plecakowym można brać ułamkowe części przedmiotów.

W przypadku, gdy problem jest rozważany przy założeniach, że

  • jest problemem decyzyjnym
  • jest dyskretny
  • dla każdego elementu waga równa się wartości w_j=c_j

utożsamiany jest z problemem: czy dla danego zbioru liczb całkowitych istnieje taki jego podzbiór, że suma jego liczb wynosi dokładnie W? Zagadnienie to nazywane jest problemem sumy podzbioru.

Problem plecakowy może być rozwiązany przy użyciu programowania dynamicznego, ale rozwiązanie wielomianowe nie jest znane. Problem plecakowy oraz sumy podzbioru są problemami NP trudnymi, co było powodem użycia sumy podzbioru jako podstawy w niektórych systemach kryptografii asymetrycznej takich jak Merkle-Hellman. Algorytmy takie używały grup, nie liczb całkowitych. Merkle-Hellman oraz kilka podobnych algorytmów zostało w późniejszym czasie złamanych, ponieważ szczególny problem sumy podzbioru użyty w tych algorytmach były rozwiązywalne w czasie wielomianowym[1].

Decyzyjna wersja problemu plecakowego opisana wyżej jest problemem NP zupełnym i jest jednym z 21 NP zupełnych problemów Karpa.

Realizacje algorytmu[edytuj | edytuj kod]

Przegląd zupełny[edytuj | edytuj kod]

Przegląd zupełny (bruteforce, metoda siłowa) – metoda nieefektywna obliczeniowo (ale optymalna, gdyż znajduje rozwiązanie najlepsze); w jego przypadku złożoność obliczeniowa al­gorytmu wyniesie \Theta(2^n), co zdecydowanie zawyży czas działania dla dużych n. Złożoność wynosi \Theta(2^n) ponieważ jest tyle możliwych ciągów zero jedynkowych na n polach. Złożoność można również obliczyć ze wzoru dwumianowego Newtona (dwumian Newtona) podstawiając za a i b jedynki.

Rozwiązania dynamiczne[edytuj | edytuj kod]

Problem plecakowy może być rozwiązany w czasie pseudowielomianowym przy użyciu programowania dynamicznego. Rozwiązanie niżej dotyczy przypadku w którym można użyć wielokrotnie każdego elementu:

Niech w1, ..., wn będzie wagą elementów oraz c1, ..., cn wartościami. Algorytm ma zmaksymalizować sumę wartości elementów, przy zachowaniu sumy ich wagi mniejszej bądź równej W. Niech A(i) będzie największą możliwą wartością, która może być otrzymana przy założeniu wagi mniejszej bądź równej i. A(W) jest rozwiązaniem problemu.

A(i) jest zdefiniowane rekurencyjnie:

  • A(0) = 0
  • A(i) = max { cj + A(iwj) : wji }

Rozwiązanie dla pustego plecaka jest równe zero. Obliczenie wyników kolejno dla A(0), A(1)... aż do A(W) pozwala obliczyć wynik. Ponieważ obliczenie A(i) wymaga sprawdzenia n elementów, a wartości A(i) do obliczenia jest W, złożoność obliczeniowa programu wynosi \Theta(nW).

Powyższa złożoność nie neguje faktu, że problem plecakowy jest NP zupełny, ponieważ W, w przeciwieństwie do n, nie jest proporcjonalne do rozmiaru danych wejściowych dla problemu. Rozmiar wejścia jest proporcjonalny do ilości bitów w liczbie W, nie do wartości W.

Pseudokod (rozwiązanie znajduje się w komórce A[W], tablica A[0..W] przechowuje wyniki, wagi znajdują się w tablicy w[1..n], a wartości w tablicy c[1..n]):

  for i:=0 to W do
    A[i]:= 0

  for i:=0 to W do
    for j:=1 to n do
      if ( w[j] <= i ) then   //sprawdzenie czy j-ty element mieści się w plecaku o rozmiarze i
        A[i] = max(A[i], A[i-w[j]] + c[j])

Podobne rozwiązanie może zostać zastosowane dla dyskretnego problemu plecakowego, także działające w czasie pseudowielomianowym. Niech w1, ..., wn będzie wagą elementów oraz c1, ..., cn wartościami. Algorytm ma zmaksymalizować wartość elementów, przy zachowaniu sumy ich wagi mniejszej bądź równej W. Niech A(i, j) będzie największą możliwą wartością, która może być otrzymana przy założeniu wagi mniejszej bądź równej j i wykorzystaniu pierwszych i elementów. A(n,W) jest rozwiązaniem problemu.

Funkcję A(i,j) definiowana jest rekurencyjnie:

  • A(0, j) = 0
  • A(i, 0) = 0
  • A(i, j) = A(i – 1, j) jeśli wi > j
  • A(i, j) = max(A(i – 1, j), ci + A(i – 1, j – wi)) jeśli wij

Rozwiązaniem problemu jest wynik dla A(n,W). Do efektywnego wykonania algorytmu używa się tablicy do zapamiętywania obliczonych podproblemów. Złożoność obliczenia wynosi podobnie jak wyżej \Theta(nW), podobnie jak złożoność pamięciowa. Przy niewielkich modyfikacjach można jednak zredukować ilość potrzebnej pamięci do rzędu \Theta(W).

Pseudokod (tablica A[1..n,0..W] przechowuje wyniki, wagi znajdują się w tablicy w[1..n], a wartości w tablicy c[1..n], rozwiązanie znajduje się w komórce A[n,W]):

  for i:=0 to n do
    A[i,0]:= 0
  for j:=0 to W do
    A[0,j]:= 0

  for i:=1 to n do           //rozważanie kolejno i pierwszych przedmiotów
    for j:=0 to W do
      if ( w[i] > j ) then   //sprawdzenie czy i-ty element mieści się w plecaku o rozmiarze j
        A[i,j] = A[i-1,j]
      else
        A[i,j] =  max(A[i-1,j], A[i-1,j-w[i]] + c[i])

Algorytm aproksymacyjny[edytuj | edytuj kod]

W pierwszej części algorytmu zachłannego przedmioty są sortowane według stosunku wartości do wagi (po lewej), po czym wybierane są kolejno od góry te elementy które się jeszcze mieszą w plecaku. W wyniku wybrane zostały przedmioty o 1. i 3. o łącznej wartości 11$ i wadze 11 kg. Optymalnym wynikiem byłyby jednak przedmioty 1. i 5. o łącznej wadze 14 kg i wartości 12$.

W wersji zachłannej algorytm aproksymacyjny sortuje elementy w kolejności malejącej porównując stosunek wartości do wagi elementu h_j = \frac{c_j}{w_j}. Następnie wstawia je kolejno zaczynając od przedmiotu o największym ilorazie do plecaka. Jeśli jakiś element nie mieści się w plecaku to jest omijany, a algorytm przechodzi do następnego. W algorytmie wybierany jest maksymalny wynik z tak obliczonego upakowania plecaka oraz plecaka z elementem o największej wartości. Jeśli k jest maksymalną wartością przedmiotów w optymalnie upakowanym plecaku, algorytm zachłanny osiąga wyniki nie gorsze niż k/2[2]. Złożoność obliczeniowa algorytmu zależy od sortowania (\Theta(n \cdot \log{n})).

Pseudokod:

posortuj nierosnąco przedmioty według wartości c[j]/w[j]
aktualna_waga:=0

for i:=1 to n do
  if w[i] + aktualna_waga <= W then
    dodaj i-ty przedmiot do plecaka
    aktualna_waga := aktualna_waga + w[i]

Po wykonaniu tej części algorytmu należy porównać wynik z plecakiem w którym jest przedmiot o największej wartości[2].

Po raz pierwszy zachłanny algorytm aproksymacyjny został zaproponowany przez George'a Dantziga w 1957 roku.

Ciągły problem plecakowy[edytuj | edytuj kod]

Można go rozwiązać za pomocą algorytmu zachłannego, takiego samego jak w przypadku aproksymacyjnego algorytmu dla dyskretnego problemu plecakowego: obliczyć dla każdego elementu stosunek wartości do wagi h_j = \frac{c_j}{w_j}, uszeregować uzyskane wartości od największej do najmniejszej (można to zrobić w czasie \Theta(n \cdot \log{n})), a następnie wstawiać kolejne elementy do plecaka dopóki \sum w_j < B. Jest to rozwiązanie optymalne.

Bibliografia[edytuj | edytuj kod]

  • Michael R. Garey, David J. Johnson: Computers and intractability: a guide to the theory of NP-completeness. San Francisco: W.H. Freeman, 1979. ISBN 0-7167-1045-5.
  • Silvano Martello, Paolo Toth: Knapsack problems: algorithms and computer implementations. Chichester: J. Wiley, 1990. ISBN 0-471-92420-2.
  • Hans Kellerer, Ulrich Pferschy, David Pisinger: Knapsack Problems. Springer. ISBN 3-540-40286-1.
  • Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, Clifford Stein: Wprowadzenie do algorytmów. Warszawa: Wydawnictwa Naukowo-Techniczne, 2003. ISBN 83-204-2800-9.

Przypisy

  1. Knapsack Encryption Scheme Broken, « Math Matrix », Wydział matematyki Ohio State University, wiosna 1985, Vol. 1, No. 3.
  2. 2,0 2,1 Chair of Algorithms and Complexity (Freiburg)

Linki zewnętrzne[edytuj | edytuj kod]