Lista problemów plecakowych
Problem plecakowy jest jednym z najczęściej badanych problemów optymalizacji kombinatorycznej i ma wiele zastosowań w życiu codziennym. Z tego powodu zbadano wiele przypadków szczególnych i uogólnień.
p dla wszystkich wersji zestaw n elementów, z których każdy w ma zysk i . Binarna zmienna decyzyjna x j służy do wyboru pozycji. Celem jest zebranie kilku przedmiotów z maksymalnym całkowitym zyskiem, przy czym maksymalna łączna waga wybranych przedmiotów nie może przekroczyć W . Ogólnie rzecz biorąc, współczynniki te są skalowane do liczb całkowitych i prawie zawsze przyjmuje się, że są dodatnie.
Problem plecakowy w najbardziej podstawowej postaci:
maksymalizować | ||
z zastrzeżeniem | ||
Bezpośrednie uogólnienia
Jednym z powszechnych wariantów jest to, że każdy element można wybrać wiele razy. Ograniczony problem plecakowy określa dla każdego elementu j górną granicę u j (która może być dodatnią liczbą całkowitą lub nieskończonością) liczby przypadków wybrania elementu j :
maksymalizować | ||
z zastrzeżeniem | ||
całka dla wszystkich j |
Nieograniczony problem plecakowy (czasami nazywany całkowitym problemem plecakowym ) nie nakłada żadnych górnych ograniczeń na liczbę przypadków, w których element może zostać wybrany:
maksymalizować | ||
z zastrzeżeniem | ||
całka dla wszystkich j |
Nieograniczony wariant okazał się NP-zupełny w 1975 roku przez Luekera. Zarówno ograniczone, jak i nieograniczone warianty dopuszczają FPTAS (zasadniczo taki sam jak ten używany w problemie plecakowym 0-1).
Jeśli przedmioty są podzielone na k klas oznaczonych iz każdej klasy należy pobrać dokładnie przedmiot, otrzymujemy problem plecakowy wielokrotnego wyboru : N ja }
maksymalizować | ||
z zastrzeżeniem | ||
dla wszystkich | ||
dla wszystkich jot |
Jeśli dla każdej pozycji zysk i waga są równe, otrzymujemy problem sumy podzbioru (często zamiast tego podaje się odpowiedni problem decyzyjny ):
maksymalizować | ||
z zastrzeżeniem | ||
Jeśli mamy n przedmiotów i m plecaków o pojemnościach , otrzymujemy problem wielu plecaków :
maksymalizować | ||
z zastrzeżeniem | dla wszystkich | |
dla wszystkich | ||
dla wszystkich i wszystkie |
Jako szczególny przypadek problemu wielu plecaków, gdy zyski są równe ciężarom, a wszystkie pojemniki mają taką samą pojemność, możemy mieć problem sum wielu podzbiorów .
Kwadratowy problem plecakowy :
maksymalizować | |||
z zastrzeżeniem | |||
dla wszystkich |
Problem plecakowy Set-Union :
SUKP jest zdefiniowany przez Kellerera i wsp. (na stronie 423) w następujący sposób:
zestaw elementów } zestaw , każdy element podzbiorowi jot zestawu elementów . . Pozycje mają nieujemne zyski \ , a elementy mają nieujemne wagi , . Całkowita waga zestawu elementów jest określona przez całkowitą wagę elementów połączenia odpowiednich zestawów elementów. Celem jest znalezienie podzbioru przedmiotów o łącznej masie nieprzekraczającej pojemności plecaka i maksymalnego zysku.
Wiele ograniczeń
Jeśli istnieje więcej niż jedno ograniczenie (na przykład zarówno limit objętości, jak i limit wagi, gdzie objętość i waga każdego przedmiotu nie są powiązane), otrzymujemy problem plecakowy z wieloma ograniczeniami , wielowymiarowy problem plecakowy lub m - wymiarowy problem z plecakiem . (Uwaga: „wymiar” nie odnosi się tutaj do kształtu żadnych przedmiotów). Ma to warianty 0-1, ograniczone i nieograniczone; nieograniczony pokazano poniżej.
maksymalizować | ||
z zastrzeżeniem | dla wszystkich | |
, liczba całkowita | dla wszystkich |
że wariant 0-1 (dla dowolnego ustalonego jest NP-zupełny około 1980 I silniej, nie ma FPTAS, chyba że P = NP
Warianty ograniczone i nieograniczone (dla dowolnego ustalonego wykazują tę samą
Dla każdego ustalonego dopuszczają algorytm pseudowielomianowego podobny do tego dla podstawowego plecaka) i PTAS .
Problemy jak z plecakiem
Jeśli wszystkie zyski wynoszą 1, spróbujemy zmaksymalizować liczbę przedmiotów, która nie przekroczy pojemności plecaka:
maksymalizować | ||
z zastrzeżeniem | ||
Jeśli mamy kilka pojemników (o tym samym rozmiarze) i chcemy zapakować wszystkie n przedmiotów do jak najmniejszej liczby pojemników, otrzymujemy problem pakowania w pojemniki , który jest modelowany przez zmienne wskaźnikowe używany jest kontener i :
minimalizować | ||
z zastrzeżeniem | ||
Problem z rozbiorem jest identyczny z problemem z pakowaniem do pojemników , ale ponieważ praktyczne przypadki obejmują zwykle znacznie mniej rodzajów przedmiotów, często stosuje się inne sformułowanie. Przedmiot j jest potrzebny B j razy, każdy „wzór” przedmiotów mieszczących się w jednym plecaku ma zmienną x i (jest m wzorców), a wzór i wykorzystuje przedmiot j b ij razy:
zminimalizować | ||
z zastrzeżeniem | dla wszystkich | |
dla wszystkich |
Jeśli do problemu plecakowego wielokrotnego wyboru dodamy ograniczenie, że każdy podzbiór ma rozmiar n i usuniemy ograniczenie dotyczące całkowitej wagi, otrzymamy problem przypisania , który jest również problemem znalezienia maksymalnego dopasowania dwudzielnego :
maksymalizować | ||
z zastrzeżeniem | dla wszystkich | |
dla wszystkich | ||
dla wszystkich jot |
W wariancie plecakowym o maksymalnej gęstości istnieje waga początkowa i maksymalizujemy gęstość wybranych przedmiotów, które nie naruszają ograniczenia pojemności: w
maksymalizować | ||
z zastrzeżeniem | ||
Chociaż mniej powszechne niż powyższe, istnieje kilka innych problemów podobnych do plecaka, w tym:
- Zagnieżdżony problem plecakowy
- Problem z zapadającym się plecakiem
- Nieliniowy problem plecakowy
- Odwrotnie parametryczny problem plecakowy
Ostatnie trzy z nich omówiono w pracy referencyjnej Kellerera i wsp. Problemy plecakowe .
-
^
Martello, Silvano i Toth, Paolo (1990). Problemy plecakowe: algorytmy i implementacje komputerowe . John Wiley & Synowie . ISBN 978-0471924203 .
{{ cite book }}
: CS1 maint: wiele nazwisk: lista autorów ( link ) -
^ a b c d
Kellerer, Hans i Pferschy, Ulrich i Pisinger, David (2004). Problemy z plecakiem . Springer Verlag . ISBN 978-3-540-40286-2 .
{{ cite book }}
: CS1 maint: wiele nazwisk: lista autorów ( link ) -
^
Lueker, GS (1975). „Dwa problemy NP-zupełne w nieujemnym programowaniu liczb całkowitych”. Raport nr 178, Laboratorium Informatyki, Princeton.
{{ cite journal }}
: Cite journal wymaga|journal=
( pomoc ) -
^
Gens, GV i Levner, EV (1979). „Algorytmy złożoności i aproksymacji dla problemów kombinatorycznych: ankieta”. Centralny Instytut Ekonomiczno-Matematyczny Akademii Nauk ZSRR w Moskwie.
{{ cite news }}
: CS1 maint: używa parametru autorów ( link ) - ^ „O istnieniu schematów szybkiego zbliżania” . Programowanie nieliniowe . 4 : 415–437. 1980.
- ^ Magazyn, MJ; Chern, M.-S. (1984). „Uwaga na temat schematów aproksymacji dla wielowymiarowych problemów plecakowych”. Matematyka badań operacyjnych . 9 (2): 244–247. doi : 10.1287/moor.9.2.244 .
- ^ Cohen, Reuven; Katzir, Liran (2008). „Uogólniony problem maksymalnego zasięgu”. Listy dotyczące przetwarzania informacji . 108 : 15–22. CiteSeerX 10.1.1.156.2073 . doi : 10.1016/j.ipl.2008.03.017 .
- „Algorytmy problemów plecakowych” , D. Pisinger. doktorat praca magisterska, DIKU, Uniwersytet Kopenhaski, Raport 95/1 (1995).