Problem plecakowy: Różnice pomiędzy wersjami

Dodane 16 bajtów ,  7 miesięcy temu
poprawiono pisownię i interpunkcję
(Rescuing 1 sources and tagging 0 as dead.) #IABot (v2.0.8)
(poprawiono pisownię i interpunkcję)
[[Plik:Knapsack.svg|mały|300px|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''' ([[język angielski|ang.]] ''discrete knapsack problem'') – jeden z najczęściej poruszanych [[problem optymalizacyjny|problemów optymalizacyjnych]]. Nazwa zagadnienia pochodzi od maksymalizacyjnego problemu wyboru przedmiotów, tak by ich sumaryczna wartość sumaryczna 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–tyj-ty przedmiot jest wart <math>c_j</math> oraz waży <math>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]], [[Kryptologia|kryptografii]] oraz [[matematyka stosowana|matematyce stosowanej]].
 
[[Problem decyzyjny (teoria obliczeń)|Decyzyjna]] wersja przedstawionego zagadnienia to pytanie: „czy„Czy wartość co najmniej <math>C</math> może być osiągnięta bez przekraczania wagi <math>W</math>?”.
 
== Definicja ==
: 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>
 
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.
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łybył rozwiązywalnerozwiązywalny w [[Algorytm wielomianowy|czasie wielomianowym]]<ref>[https://web.archive.org/web/20071122014915/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 [[Problem 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]] 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żejpodane poniżej dotyczy przypadku, w którym można użyć wielokrotnie każdego elementu:
 
Niech <math>w_1, \dots, w_n</math> będą wagami poszczególnych elementów oraz <math>c_1, \dots, c_n</math> ich 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:
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> a 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]):
</pre>
 
Podobne rozwiązanie może zostać zastosowane dla dyskretnego problemu plecakowego, także działające w czasie pseudowielomianowym. Niech <math>w_1, \dots, w_n</math> będzie wagą elementów oraz <math>c_1, \dots, c_n</math> 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:
=== 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) |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:
</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 raz pierwszy zachłanny algorytm aproksymacyjny został zaproponowany przez [[George Dantzig|George’a Dantziga]] w [[1957]] roku.
36

edycji