Problem plecakowy: Różnice pomiędzy wersjami

Usunięte 71 bajtów ,  2 lata temu
m
m (Wycofano edycje użytkownika 217.96.169.16 (dyskusja). Autor przywróconej wersji to RoclorD.)
Znacznik: Wycofanie zmian
m (WP:SK+Bn)
'''Dyskretny problem plecakowy''' ([[język angielski|ang.]] ''discrete knapsack problem'') jest jednym z najczęściej poruszanych [[problem optymalizacyjny|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 <math>c_{j}c_j</math> oraz waży <math>w_{j}w_j.</math>. 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 [[kombinatoryka|kombinatoryce]], [[złożoność obliczeniowa|teorii złożoności obliczeniowej]], [[kryptografiaKryptologia|kryptografii]] oraz [[matematyka stosowana|matematyce stosowanej]].
 
[[Problem decyzyjny (teoria obliczeń)|Decyzyjna]] wersja przedstawionego zagadnienia to pytanie "czy„czy wartość co najmniej ''C'' może być osiągnięta bez przekraczania wagi ''W''?"
 
== Definicja ==
Definicja formalna: mamy do dys­pozycjidyspozycji plecak o maksymalnej pojemności <math>B</math> oraz zbiór <math>N</math> elementów <math>\{x_1, x_j, ..., x_N\},</math>, przy czym każdy element ma określoną wartość <math>c_{j}c_j</math> oraz wielkość <math>w_{j}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 \leleqslant B, \quad \quadqquad 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 \leleqslant B, \quad \quadqquad 0 \leleqslant x_j \leleqslant b_j, \quad j=1,\dots,n.</math>
 
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'').
* 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 ''W''? 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ą [[problemProblem NP -trudny|problemami NP trudnymi]], co było powodem użycia sumy podzbioru jako podstawy w niektórych systemach [[Kryptografia asymetrycznaklucza 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>.
 
Decyzyjna wersja problemu plecakowego opisana wyżej jest problemem [[problemProblem NP -zupełny|NP zupełnym]] i jest jednym z 21 NP zupełnych problemów Karpa.
 
== 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]] al­gorytmualgorytmu 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 ===
''A''(''i'') jest zdefiniowane rekurencyjnie:
* ''A''(0) = 0
* ''A''(''i'') = max { ''c<sub>j</sub>'' + ''A''(''i'' ''w<sub>j</sub>'') : ''w<sub>j</sub>'' ≤ ''i'' }
 
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 <math>\Theta(nW).</math>.
 
Powyższa złożoność nie neguje faktu, że problem plecakowy jest [[problemProblem NP -zupełny|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]):
* ''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]):
=== 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 ''k'' jest maksymalną wartością przedmiotów w optymalnie upakowanym plecaku, algorytm zachłanny osiąga wyniki nie gorsze niż ''k''/2<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:
aktualna_waga := aktualna_waga + w[i]
</pre>
Po wykonaniu tej części algorytmu należy porównać wynik z plecakiem w którym jest przedmiot o największej wartości<ref name="uni-freiburg"/>.
 
Po wykonaniu tej części algorytmu należy porównać wynik z plecakiem w którym jest przedmiot o największej wartości<ref name="uni-freiburg" />.
Po raz pierwszy zachłanny algorytm aproksymacyjny został zaproponowany przez [[George Dantzig|George'a Dantziga]] w [[1957]] roku.
 
Po raz pierwszy zachłanny algorytm aproksymacyjny został zaproponowany przez [[George Dantzig|George'aGeorge’a Dantziga]] w [[1957]] roku.
 
=== Ciągły problem plecakowy ===
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 <math>h_j = \frac{c_j}{w_j},</math>, uszeregować uzyskane wartości od największej do najmniejszej (można to zrobić w czasie <math>\Theta(n \cdot \log{n})</math>), a następnie wstawiać kolejne elementy do plecaka dopóki <math>\sum w_j < B.</math>.
 
== 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
| data=
| 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=
}}
 
== Przypisy ==
{{Przypisy}}
 
== 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 ==