Problem plecakowy: Różnice pomiędzy wersjami

Dodane 112 bajtów ,  1 rok temu
m
m (WP:SK+Bn)
m (WP:SK+Bn)
Podobny problem pojawia się często w [[kombinatoryka|kombinatoryce]], [[złożoność obliczeniowa|teorii złożoności obliczeniowej]], [[Kryptologia|kryptografii]] oraz [[matematyka stosowana|matematyce stosowanej]].
 
[[Problem decyzyjny (teoria obliczeń)|Decyzyjna]] wersja przedstawionego zagadnienia to pytanie „czy wartość co najmniej ''<math>C''</math> może być osiągnięta bez przekraczania wagi ''<math>W''</math>?”
 
== Definicja ==
Definicja formalna: mamy do dyspozycji plecak o maksymalnej pojemności <math>B</math> oraz zbiór <math>N</math> elementów <math>\{x_1, x_j, ...\dots, x_N\},</math> przy czym każdy element ma określoną wartość <math>c_j</math> oraz wielkość <math>w_j.</math>
 
'''Dyskretny problem plecakowy''' (ang. ''0-1 knapsack problem'')
: formalnie problem może być zdefiniowany:
: zmaksymalizuj <math>\sum_{j=1}^N c_j x_j.</math>
: przy założeniach: <math>\sum_{j=1}^N w_j x_j \leqslant B, \qquad x_j = 0\;\mbox{lub}\;1, \quad j=1,\dots,n.</math>
 
'''Problem plecakowy''', w którym liczba elementów danego typu jest ograniczona przez podaną wartość (ang. ''bounded knapsack problem'').
: Formalnie:
: zmaksymalizuj <math>\sum_{j=1}^N c_j x_j.</math>
: przy założeniach: <math>\sum_{j=1}^N w_j x_j \leqslant B, \qquad 0 \leqslant x_j \leqslant b_j, \quad j=1,\dots,n.</math>
 
 
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 <math>w_j=c_j,</math>
 
utożsamiany jest z problemem: czy dla danego zbioru liczb całkowitych istnieje taki jego podzbiór, że suma jego liczb wynosi dokładnie ''<math>W''</math>? Zagadnienie to nazywane jest [[problem sumy podzbioru|problemem sumy podzbioru]].
 
Problem plecakowy może być rozwiązany przy użyciu [[programowanie dynamiczne|programowania dynamicznego]], ale rozwiązanie wielomianowe nie jest znane. Problem plecakowy oraz sumy podzbioru są [[Problem NP-trudny|problemami NP trudnymi]], co było powodem użycia sumy podzbioru jako podstawy w niektórych systemach [[Kryptografia klucza publicznego|kryptografii asymetrycznej]] takich jak [[Merkle-Hellman]]. Algorytmy takie używały [[grupa (matematyka)|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 [[Algorytm wielomianowy|czasie wielomianowym]]<ref>[http://www.math.ohio-state.edu/history/math-matrix/Sp85/Matrix_Sp85 ''Knapsack Encryption Scheme Broken''], « Math Matrix », Wydział matematyki Ohio State University, wiosna 1985, Vol. 1, No. 3.</ref>.
== Realizacje algorytmu ==
=== Przegląd zupełny ===
Przegląd zupełny ([[Atak brute force|bruteforce]], metoda siłowa) – metoda nieefektywna obliczeniowo (ale optymalna, gdyż znajduje rozwiązanie najlepsze); w jego przypadku [[złożoność obliczeniowa]] algorytmu wyniesie <math>\Theta(2^n),</math> co zdecydowanie zawyży czas działania dla dużych n. Złożoność wynosi <math>\Theta(2^n)</math> 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 ===
Problem plecakowy może być rozwiązany w [[algorytm pseudowielomianowy|czasie pseudowielomianowym]] przy użyciu [[programowanie dynamiczne|programowania dynamicznego]]. Rozwiązanie niżej dotyczy przypadku w którym można użyć wielokrotnie każdego elementu:
 
Niech ''w<submath>1</sub>''w_1, ...\dots, ''w<sub>nw_n</submath>'' będzie wagą elementów oraz ''c<submath>1</sub>''c_1, ...\dots, ''c<sub>nc_n</submath>'' wartościami. Algorytm ma zmaksymalizować sumę wartości elementów, przy zachowaniu sumy ich wagi mniejszej bądź równej ''<math>W''.</math> Niech ''<math>A''(''i'')</math> będzie największą możliwą wartością, która może być otrzymana przy założeniu wagi mniejszej bądź równej ''<math>i''.</math> ''<math>A''(''W'')</math> jest rozwiązaniem problemu.
 
''<math>A''(''i'')</math> jest zdefiniowane rekurencyjnie:
* ''<math>A''(0) = 0,</math>
* ''<math>A''(''i'') = \max \{''c<sub>j</sub>''c_j + ''A''(''i'' - ''w<sub>j</sub>''w_j):\colon ''w<sub>j</sub>''w_j \leqslant ''i''\}.</math>
 
Rozwiązanie dla pustego plecaka jest równe zero. Obliczenie wyników kolejno dla ''<math>A''(0), ''A''(1)...\dots</math> aż do ''<math>A''(''W'')</math> pozwala obliczyć wynik. Ponieważ obliczenie ''<math>A''(''i'')</math> wymaga sprawdzenia ''<math>n''</math> elementów, a wartości ''<math>A''(''i'')</math> do obliczenia jest ''<math>W'',</math> złożoność obliczeniowa programu wynosi <math>\Theta(nW).</math>
 
Powyższa złożoność nie neguje faktu, że problem plecakowy jest [[Problem NP-zupełny|NP zupełny]], ponieważ ''<math>W'',</math> w przeciwieństwie do ''<math>n'',</math> nie jest proporcjonalne do rozmiaru danych wejściowych dla problemu. Rozmiar wejścia jest proporcjonalny do ilości bitów w liczbie ''<math>W'',</math> nie do wartości ''<math>W''.</math>
 
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
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])
</pre>
 
Podobne rozwiązanie może zostać zastosowane dla dyskretnego problemu plecakowego, także działające w czasie pseudowielomianowym. Niech ''w<submath>1</sub>''w_1, ...\dots, ''w<sub>nw_n</submath>'' będzie wagą elementów oraz ''c<submath>1</sub>''c_1, ...\dots, ''c<sub>nc_n</submath>'' wartościami. Algorytm ma zmaksymalizować wartość elementów, przy zachowaniu sumy ich wagi mniejszej bądź równej ''<math>W''.</math> Niech ''<math>A''(''i'', ''j'')</math> będzie największą możliwą wartością, która może być otrzymana przy założeniu wagi mniejszej bądź równej ''<math>j''</math> i wykorzystaniu pierwszych ''<math>i''</math> elementów. ''<math>A''(''n'','' W'')</math> jest rozwiązaniem problemu.
 
Funkcję ''<math>A''(''i'',''j'')</math> definiowana jest rekurencyjnie:
* <math>A(0, j) = 0,</math>
* <math>A(i, 0) = 0,</math>
* <math>A(i, j) = A(i - 1, j),\quad{}</math> jeśli <math>w_i > j</math>,
* <math>A(i, j) = \max(A(i - 1, j), c_i + A(i - 1, j - w_i))\quad{}</math> jeśli <math>w_i \leqslant j.</math>
 
Rozwiązaniem problemu jest wynik dla <math>A(''n'','' W'').</math> Do efektywnego wykonania algorytmu używa się tablicy do zapamiętywania obliczonych podproblemów. Złożoność obliczenia wynosi podobnie jak wyżej <math>\Theta(nW),</math> podobnie jak złożoność pamięciowa. Przy niewielkich modyfikacjach można jednak zredukować ilość potrzebnej pamięci do rzędu <math>\Theta(W).</math>.
* ''A''(0, ''j'') = 0
* ''A''(''i'', 0) = 0
* ''A''(''i'', ''j'') = ''A''(''i'' – 1, ''j'') jeśli w<sub>i</sub> > ''j''
* ''A''(''i'', ''j'') = max(''A''(''i'' – 1, ''j''), c<sub>i</sub> + ''A''(''i'' – 1, ''j'' – w<sub>i</sub>)) jeśli w<sub>i</sub> ≤ ''j''
 
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 <math>\Theta(nW),</math> podobnie jak złożoność pamięciowa. Przy niewielkich modyfikacjach można jednak zredukować ilość potrzebnej pamięci do rzędu <math>\Theta(W)</math>.
 
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]):
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
=== Algorytm aproksymacyjny ===
[[Plik:Knapsack greedy.svg|mały|300px|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 mieszczą 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 [[algorytm zachłanny|zachłannej]] [[algorytm aproksymacyjny]] sortuje elementy w kolejności malejącej porównując stosunek wartości do wagi elementu <math>h_j = \frac{c_j}{w_j}.</math> 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 ''<math>k''</math> jest maksymalną wartością przedmiotów w optymalnie upakowanym plecaku, algorytm zachłanny osiąga wyniki nie gorsze niż ''<math>k''/2</math><ref name="uni-freiburg">{{Cytuj |url=http://www.informatik.uni-freiburg.de/~souza/knapsack.pdf |tytuł=Algorithms and Complexity (Freiburg)<!-- Tytuł wygenerowany przez bota --> |opublikowany=www.informatik.uni-freiburg.de |język=de |data dostępu=2017-11-26}}</ref>. Złożoność obliczeniowa algorytmu zależy od sortowania <math>(\Theta(n \cdot \log{n})).</math>.
 
Pseudokod:
 
== Bibliografia ==
* {{Cytuj książkę |nazwisko = Garey |imię = Michael R. |nazwisko2 = Johnson |imię2 = David J.| tytuł = Computers and intractability: a guide to the theory of NP-completeness |data = 1979 |wydawca = W.H. Freeman |miejsce = San Francisco |isbn = 0-7167-1045-5 |strony =}}
* {{Cytuj książkę |nazwisko = Martello |imię = Silvano |nazwisko2 = Toth |imię2 = Paolo| tytuł = Knapsack problems: algorithms and computer implementations |data = 1990 |wydawca = J. Wiley |miejsce = Chichester |isbn = 0-471-92420-2 |strony =}}
* {{Cytuj książkę |nazwisko = Kellerer |imię = Hans |nazwisko2 = Pferschy |imię2 = Ulrich |nazwisko3 = Pisinger |imię3 = David| tytuł = Knapsack Problems |wydawca = Springer |miejsce = |isbn = 3-540-40286-1 |strony =}}
* {{Cytuj książkę |nazwisko = Cormen |imię = Thomas H. |nazwisko2 = Leiserson |imię2 = Charles E. |nazwisko3 = Rivest |imię3 = Ronald L. |nazwisko4 = Stein |imię4 = Clifford |tytuł = Wprowadzenie do algorytmów |data = 2003 |wydawca = Wydawnictwa Naukowo-Techniczne |miejsce = Warszawa |isbn = 83-204-2800-9 |strony =}}
 
== Linki zewnętrzne ==