Problem z plecakiem

Koncepcja ta została wykorzystana do rozwiązania problemu wielowymiarowego plecaka, w którym musi być spełnionych kilka ograniczeń. Pierwsze algorytmy opierały się na idei algorytmu zachłannego: mrówki stopniowo wybierały najciekawsze obiekty. Ten dobór może się różnić, ale zawsze opiera się na śladach feromonów osadzonych przez mrówki, które warunkują kolejne wybory. Wśród proponowanych rozwiązań można wymienić osadzanie feromonów na najlepszych obiektach, osadzanie się na parach obiektów wstawianych jeden po drugim w roztworze czy też dodawanie feromonów na pary obiektów, niezależnie od kolejności wstawiania.

Synteza przeprowadzona przez badaczy tunezyjskich i francuskich wykazała, że ​​algorytm pozostawiania śladów na parach kolejno wybranych obiektów jest mniej skuteczny niż warianty skupiające się na obiekcie lub dowolnych parach. Jednak ulepszenia są nadal możliwe, ponieważ algorytmy te można łączyć z innymi metaheurystykami w celu uzyskania optymalnego rozwiązania.

Dokładna rozdzielczość

Problem plecaka w jego klasycznej wersji został dogłębnie zbadany. Obecnie istnieje wiele metod rozwiązania tego problemu. Większość z tych metod to ulepszona wersja jednej z poniższych metod.

Programowanie dynamiczne

Problem plecaka ma właściwość optymalnej podkonstrukcji , to znaczy, że możemy zbudować optymalne rozwiązanie problemu ze zmiennymi i z zadania ze zmiennymi i -1 . Użyj tej właściwości, aby użyć dynamicznej programowej metody rozstrzygania .

Oznaczymy przez KP ( i , c ) problem zredukowany do i zmiennych i pojemności c . Pomysł jest następujący:

Biorąc pod uwagę zmienną i oraz pojemność c , optymalnymi rozwiązaniami KP ( i , c ) są:

• optymalne rozwiązania problemu ze zmiennymi i -1 o tej samej pojemności c (czyli KP ( i -1, c ) ), do których dodajemy  ;xja=0{\ displaystyle x_ {i} = 0}
• optymalne rozwiązania problemu ze zmiennymi i -1 o pojemności c - w i (czyli KP ( i -1, c - w i ) ), do których dodajemy .xja=1{\ displaystyle x_ {i} = 1}

Problem plecaka o zmiennej zerowej ( KP (0, *) ) ma optymalne rozwiązanie o wartości zerowej.

Następnie konstruujemy tablicę T [i, c] zawierającą wartości optymalnych rozwiązań dowolnego problemu KP ( i , c ) w następujący sposób:

Po skonstruowaniu tabeli wszystko, co musisz zrobić, to zacząć od pudełka T [n, W] i wydedukować stan obiektów, przechodząc do pudełka T [0, *].

Algorytm ten ma czasową i przestrzenną złożoność w O ( nW ) . Jednak dodając algorytm dziel i zwyciężaj , możemy zmniejszyć zużycie pamięci do O ( n + W ) , a nawet, jeśli ważna jest tylko wartość rozwiązania optymalnego, do O ( W ) . Ma dwie zalety:

1. szybko, jeśli ciężary są pełne, a pojemność worka jest umiarkowana.
2. nie ma potrzeby sortowania zmiennych.

i wada:

1. intensywna pamięć (w związku z tym brak rozwiązania dużych problemów).

Zauważ, że ten algorytm nie działa w czasie wielomianowym w odniesieniu do rozmiaru danych wejściowych. Rzeczywiście, złożoność jest proporcjonalna do pojemności worka W , jest wykładnicza w odniesieniu do jego kodowania. Jeśli wagi przedmiotów są dziesiętne , wymusza to pomnożenie wagi przedmiotów i pojemności torby, aby uzyskać całość. Ta operacja może następnie spowolnić działanie algorytmu.

To podejście pochodzi od Garfinkela i Nemhausera (1972).

Procedura separacji i oceny

Jak każdy problem kombinatoryczny, problem plecaka można rozwiązać za pomocą procedury separacji i oceny (PSE). Funkcja oceny węzeł składa się często w rozwiązaniu problemu w zmiennych ciągłych (patrz poniżej). Wdrożenie zaproponowane przez Martello i Totha (1990) stało się punktem odniesienia. Wyróżnia się:

• ulepszona ocena węzłów;
• wyszukiwanie lokalne , gdy ostatnia zmienna dodana do worka nieudanej;
• znaczna złożoność kodu źródłowego .

Zaletą tej metody jest niskie zużycie pamięci .

Podejścia hybrydowe

Podejście hybrydowe nie jest tak naprawdę nową metodą rozwiązywania. Polega po prostu na połączeniu dwóch poprzednich metod w celu uzyskania wszystkich korzyści. Zazwyczaj zastosujemy PSE do głębokości wyszukiwania, przy której podproblem zostanie oceniony jako wystarczająco mały, aby można go było rozwiązać za pomocą programowania dynamicznego.

Prekursorami tego podejścia są Plateau i Elkihel (1985), a następnie Martello i Toth (1990). Od tego czasu wprowadzono inne ulepszenia.

Warianty

Przedstawiony dotychczas problem to, dokładniej, problem plecaka ze zmienną binarną ( 01KP ). W rzeczywistości jest to jedna z wielu odmian. Ta sekcja przedstawia te różne warianty. Szczegóły dotyczą dziedziny zmiennych, liczby wartości przedmiotów, liczby wymiarów torby itp. Te funkcje można również łączyć.

Zmienne ciągłe

Problem plecaka ze zmienną ciągłą ( LKP ) osiąga się poprzez usunięcie ograniczenia integralności zmiennych. To znaczy, że ktoś jest upoważniony do podjęcia tylko część obiektów w plecaku: . LKP należy do klasy P złożoności . xja∈[0,1]{\ displaystyle x_ {i} \ in [0,1]}

Oto algorytm obliczania optymalnego rozwiązania problemu LKP  :

Należy zauważyć, że wartość optymalnego rozwiązania LKP jest co najwyżej równa dwukrotności wartości optymalnego rozwiązania odpowiedniego problemu KP :z∗(LK.P.)≤2×z∗(K.P.){\ Displaystyle z ^ {*} (LKP) \ równoważnik 2 \ razy z ^ {*} (KP)}

Zmienne całkowite

W przypadku problemu plecaka ze zmiennymi całkowitymi rozważamy, że mamy kilka kopii każdego obiektu. Problem polega zatem na znalezieniu liczby kopii do wykonania dla każdego.

Jeśli liczba kopii jest ograniczona, będziemy mówić o plecaku w oprawie ( BKP ), w przeciwnym razie o plecaku bez ograniczeń ( UKP ). Problem BKP można bez trudu przekształcić w 01KP .

Wielowymiarowy plecak

Uważamy tutaj, że plecak ma wymiary d , gdzie d > 0 ( d-KP ). Na przykład możemy sobie wyobrazić pudełko. Każdy obiekt ma trzy wymiary i nie powinien przenikać do żadnego z wymiarów. Następnie ograniczenie (1) zastępuje się:

∑ja=1niexjawjak≤W.k,∀k∈{1,...,re}{\ displaystyle \ sum _ {i = 1} ^ {n} x_ {i} w_ {i} ^ {k} \ leq W ^ {k}, \ forall k \ in \ {1, \ kropki, d \} }

W praktyce wersja wielowymiarowa może służyć do modelowania i rozwiązywania problemu napełnienia pojemnika, którego objętość i maksymalne obciążenie są ograniczone.

Innym przykładem jest zarządzanie personelem. W wersji uproszczonej oceniamy produktywność lub kompetencje każdej osoby (jego „wagę” w problemie) i przypisujemy mu inne zmienne: koszt i dyspozycyjność. Każdy z tych parametrów określa wymiar plecaka. Na koniec określasz ograniczenia związane z Twoim projektem w odniesieniu do poprzednich parametrów: dostępny budżet i czas przeznaczony na wykonanie prac. Uchwała pozwala określić, kto powinien zostać zatrzymany do realizacji projektu.

Uniwersalny plecak

Wariant problemu polega na tym, że z obiektów posiadających kilka wartości, aby zmaksymalizować kilka funkcji celu, jest to problem plecaka wielocelowego ( MOKP ). W związku z tym wkraczamy w obszar optymalizacji wielocelowej .

Na przykład załóżmy, że zaczynamy firmę specjalizującą się w rejsach wycieczkowych . Aby dać się poznać, postanawiamy zaprosić znane osoby na pokład najpiękniejszej łodzi . Ta łódź nie może pomieścić więcej niż tonę pasażerów (będzie to stałe W ). Każdy pasażer ma masę ( w i ), rozgłos swoją popularnością ( s1
i : indeks popularności) i prosi o wynagrodzenie ( s2
i : wynagrodzenie ujemne). Naturalnie staramy się zmaksymalizować dostarczaną reklamę i zminimalizować całkowitą pensję do wypłaty (zmaksymalizować ujemną pensję). Ponadto chcemy, aby na łodzi znajdowało się jak najwięcej osób ( s3
i= 1). Dlatego należy zmaksymalizować trzy kwoty.

W kategoriach matematycznych szukamy wektora X znanych osób spełniających problem:

1. maxz1(X)=∑ja=1niexjapja1{\ displaystyle \ max z ^ {1} (X) = \ suma _ {i = 1} ^ {n} x_ {i} p_ {i} ^ {1}} (zależy nam na maksymalnej popularności)
2. maxz2(X)=∑ja=1niexjapja2{\ displaystyle \ max z ^ {2} (X) = \ suma _ {i = 1} ^ {n} x_ {i} p_ {i} ^ {2}} (zminimalizować wynagrodzenie do wypłaty, tj. zmaksymalizować wynagrodzenie ujemne);
3. maxz3(X)=∑ja=1niexjapja3{\ displaystyle \ max z ^ {3} (X) = \ suma _ {i = 1} ^ {n} x_ {i} p_ {i} ^ {3}} (mieć jak najwięcej osób na łodzi)

pod ograniczeniami

∑ja=1niexjawja≤W.{\ displaystyle \ sum _ {i = 1} ^ {n} x_ {i} w_ {i} \ równoważnik W}

Ogólnie rzecz biorąc, zastępujemy funkcję celu w pierwotnym problemie rodziną funkcji celu:

maxzjot(X)=∑ja=1niexjapjajot,∀jot∈{1,...,m}{\ displaystyle \ max z ^ {j} (X) = \ suma _ {i = 1} ^ {n} x_ {i} p_ {i} ^ {j}, \ forall j \ in \ {1, \ kropki , m \}}

Plecak kwadratowy

Problem z plecakiem kwadratowym jest oznaczony przez QKP . Tutaj mamy dodatkowe wzmocnienie g ij, gdy dwa obiekty ( i i j ) są brane jednocześnie. Na przykład załóżmy, że chcemy zmaksymalizować jakość kawy podczas wyprawy z plecakiem. Możemy zrozumieć, że bardziej interesujące jest przyniesienie łyżki i cukru niż tylko jednego z nich.

Następnie zapisujemy funkcję celu:

max{z(X)}=∑ja=1niexjapja+∑ja=1nie∑jot=1niexjaxjotsoljajot{\ Displaystyle \ max \ lewo \ {Z (X) \ prawo \} = \ suma _ {i = 1} ^ {n} x_ {i} p_ {i} + \ suma _ {i = 1} ^ {n } \ sum _ {j = 1} ^ {n} x_ {i} x_ {j} g_ {ij}}

Problem sumy podzbiorów lub sumy podzbiorów

Specyfika problemu sumy podzbiorów (w języku angielskim: suma podzbiorów ) polega na tym, że wartość i waga obiektów są identyczne ( p i = w i ). Jest to ważny problem z zakresu kryptografii , stosowany w kilku systemach generowania kluczy publicznych .

Plecak wielokrotnego wyboru

W przypadku problemu z plecakiem wielokrotnego wyboru ( MCKP ) obiekty są pogrupowane w klasy, a dla każdej klasy należy wziąć tylko jednego przedstawiciela.

Na przykład jesteśmy w trakcie tworzenia Twojego zestawu narzędzi . Jeśli masz pięć kluczy nastawnych , możesz wybrać najlżejszy, aby wziąć potężny młotek , lub wybrać najmocniejszy klucz i młotek z niższej półki, albo pójść na kompromis. Ogólna idea jest taka, że ​​nie możesz wziąć więcej niż jednego klucza ani więcej niż jednego młotka.

Jeśli obiekty są ułożone w k klas, oznaczymy zbiór indeksów obiektów należących do klasy j . Uważamy oczywiście, że obiekt należy tylko do jednej klasy. Sformułowanie problemu wygląda następująco: NIEjot,jot∈{1,...,k}{\ Displaystyle N_ {j}, j \ w \ {1, \ kropki, k \}}

maxz(X)=∑jot=1k∑ja∈NIEjotxjajotpjajot{\ Displaystyle \ max z (X) = \ suma _ {j = 1} ^ {k} \ suma _ {i \ in N_ {j}} x_ {i} ^ {j} p_ {i} ^ {j} }

pod ograniczeniami:

• ∑jot=1k∑ja∈NIEjotxjajotwjajot≤W.{\ displaystyle \ sum _ {j = 1} ^ {k} \ sum _ {i \ in N_ {j}} x_ {i} ^ {j} w_ {i} ^ {j} \ równoważnik W} (nie przekraczamy pojemności worka);
• ∑ja∈NIEjotxjajot≤1,∀jot∈{1,...,k}{\ displaystyle \ sum _ {i \ in N_ {j}} x_ {i} ^ {j} \ równorzędny 1, \ dla wszystkich j \ w \ {1, \ kropki, k \}} (wybiera się co najwyżej jednego przedstawiciela każdej klasy).

Wielokrotny plecak

Problem z wieloma plecakami ( MKP ) polega na podzieleniu zestawu przedmiotów na wiele plecaków o różnej pojemności. Wartość przedmiotu zależy teraz od worka, w którym został umieszczony. Na przykład możemy uznać, że euro ma większą wartość na rachunku oszczędnościowym niż na rachunku bieżącym .

Jeśli mamy k plecaków, zanotujemy, czy przedmiot i jest umieszczony w torbie j . Sformułowanie problemu wygląda następująco: xjajot=1{\ displaystyle x_ {i} ^ {j} = 1}

maxz(X)=∑jot=1k∑ja=1niexjajotpjajot{\ Displaystyle \ max Z (X) = \ suma _ {j = 1} ^ {k} \ suma _ {i = 1} ^ {n} x_ {i} ^ {j} p_ {i} ^ {j} }

pod ograniczeniami

• ∑ja=1niexjajotwja≤W.jot,∀jot∈{1,...,k}{\ displaystyle \ sum _ {i = 1} ^ {n} x_ {i} ^ {j} w_ {i} \ leq W ^ {j}, \ forall j \ in \ {1, \ kropki, k \} } (nie przekraczamy pojemności worków);
• ∑jot=1kxjajot≤1,∀ja∈{1,...,nie}{\ displaystyle \ sum _ {j = 1} ^ {k} x_ {i} ^ {j} \ równoważnik 1, \ forall ja \ in \ {1, \ kropki, n \}} (przedmiot wkłada się tylko do torby).

Istnieje wariant tego problemu, w którym wszystkie torby mają taką samą pojemność, zaznaczono MKP-I .

Zobacz też

Powiązane artykuły

• Problem komiwojażera
• Optymalizacja kombinatoryczna

Bibliografia

(en) Hans Kellerer, Ulright Pferschy i David Pisinger, Knapsack Problems , Springer, 2004 ( ISBN  3-540-40286-1 ) .

Uwagi i odniesienia

1. (w) Lenore Blum , Felipe Cucker, Michael Shub i Stephen Smale , Complexity and Real Computation , Springer ,2012( czytaj online ) , s.  13.
2. (w) GB Mathews , „  O podziale liczb  ” , Proc. Natl. London Math. Soc. , vol.  28,1897, s.  486-490.
3. (w) Kryptografia klucza publicznego , w „  Historii  ” projektu klasy Erica Roberta w college'u Sophomore „ Intelektualna ekscytacja informatyki ” na Uniwersytecie Stanforda . Odpowiednia publikacja to: RC Merkle i ME Hellman, Hiding Information and Receipts in Trap Door Knapsacks , Internal Symposium on Information Theory , Cornell University, Ithaca, Nowy Jork, październik 1977.
4. Pascal Boyer, Mały towarzysz liczb i ich zastosowania , Paryż, Calvage i Mounet,2019, 648  str. ( ISBN  978-2-916352-75-6 ) , VI. Kryptografia, rozdz.  6 („Metoda plecakowa”), s.  538-539.
5. (w) A. Shamir , A Wielomian-Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem , IEEE Transactions on Information Theory , Vol. IT-30, s.  699-704 , 1984. (pierwsze opublikowane w kwietniu 1982 ).
6. (w) Knapsack Encryption Scheme Broken ,  wydział matematyki „  Math Matrix ” na State University of Ohio , v 1985 , vol. 1, nr 3.
7. (w) S. Vaudenay, Kryptanaliza kryptosystemu Chor-Rivest .
8. Na przykład, patrz (w) Kurt Eisemann, „  The trim problem  ” , Management Science , INFORMS flight.  3 n o  3,1957, s.  279-284.
9. (w) Michail G. Lagoudakis, Problem plecakowy 0-1 - ankieta wprowadzająca 1996.
10. (en) Optymalizacja Ant Colony dla problemu z powrotem w wielowymiarowej torbie .
11. (en) U. Pferschy, "  Dynamiczne programowanie ponownie: ulepszanie algorytmów plecakowych  " , Informatyka. Archives for Scientific Computing , vol.  63, n o  4,1999, s.  419-430 ( czytaj online ).
12. (w) RS Garfinkel i GL Nemhauser , Integer Pogramming , Nowy Jork, John Wiley & Sons ,1972( ISBN  978-0-471-29195-4 ).
13. (en) Silvano Martello i Paolo Toth , Knapsack Problems: Algorithms and Computer Implementations , John Wiley & Sons ,1990, 296  str. ( ISBN  978-0-471-92420-3 ).
14. (w) Gerard Plateau i Moussa Elkihel , "  Metoda hybrydowa dla problemu plecakowego 0-1  " , Methods Oper. Res. , vol.  49,1985, s.  277-293.