Problem ranca

Из Википедије, слободне енциклопедије

Problem ranca je problem koji je najviše istraživan u kombinatornoj optimizaciji, sa mnogo primena u stvarnom životu. Zbog ovoga je ispitano mnogo specijalnih slučajeva i napravljeno je mnogo generalizacija.

Zajedničko za sve verzije je n predmeta, a svaki predmet ima pridruženu vrednost pj i težinu wj. Cilj je sakupiti određeni broj predmeta, tako da vrednost ranca bude maksimalna, ali da ne pređe zadatu vrednost W. Uglavnom, ovi koeficijenti se skaliraju da bi bili celi brojevi i gotovo uvek se pretpostavlja da su pozitivni.

Problem ranca u osnovnoj formi:

maksimalno
predmet

Direktne generalizacije[уреди]

Jedna od češćih varijanti je da se svaki predmet može birati više puta. Konkretno, kod problema ograničenog ranca za svaki predmet j, i gornju granicu uj (koja može biti pozitivan ceo broj ili beskonačno) za broj predmeta j može biti izabrano:

maksimalno
predmet
ceo broj za sve j

Neograničeni problem ranca (koji se nekada naziva i celobrojni problem ranca) ne postavlja gornju granicu za broj predmeta koji mogu da se odaberu:

maksimalno
predmet
ceo broj za sve j

Lueker je pokazao 1975. godine [1] da je varijata bez granice NP-kompletan problem. Obe varijatne, i sa ograničenjem i bez ograničenja, imaju aproskimativnu šemu polinomijalnog vremena - FPTAS (u suštini, kao i kod 0-1 problemna ranca).

Ako se predmeti podele na k klasa označene sa , i ako iz svake klase mora da se uzme tačno jedan predmet, dobija se problem ranca sa višetrukim izborom:

maksimalno
predmet
za sve
za sve i sve

Ako su za sve predmete vrednost i težina identični, dobijamo problem zbira podskupa (često je dat odgovarajući problem, problem odlučivanja ):

maksimalno
predmet

Ako imamo n predmeta i m rančeva sa kapacitetima , dobijamo višestruki problem ranca:

maksimalno
predmet za sve
za sve
za sve i sve

Kao specijalan slučaj višetrukog problema ranca, kada su vrednosti jednake težinama i svi binovi imaju isti kapacitet, možemo imati i problem zbira višetrukog podskupa:

Kvadratni problem ranca:

maksimalno
predmet
za sve

Problem ranca - Unija skupa:

SUKP (Set-Union Knapsack Problem) je definisao Kellerer i dr.[2] (na 423. str.):

Dat je skup od predmeta i skup od , tako reći, elemenata , gde svaki predmet odgovara podskupu skupa elemenata . Predmeti imaju nenegativne vrednosti , , a elementi nenegativne težine , . Konačna težina skupa predemeta je data konačnom težinom elemenata unije odgovarajućih skupa elemenata. Cilj je naći podskup predmeta sa konačnom težinom koja ne prelazi kapacitet ranca i maksimalnu vrednost.

Višestruko ograničenje[уреди]

Ako postoji više od jednog ograničenja (na primer, i granica za obim i granica za težinu, gde obim i težina svakog predmeta nisu povezani), dobijamo problem ranca sa višestrukim ograničenjem, višedimenzionalni problem ranca, ili m-dimenzionalni problem ranca. (Napomena, "dimenzija" se ovde ne odnosi na oblik predmeta.) Ovo ima 0-1, ograničenu, i neograničenu varijantu; neograničena je prikazana ispod.

maksimalno
predmet za sve
, integer za sve

Pokazano je da je varijanta 0-1 (za sve fiksne ) NP-komplentna oko 1980. godine i da nema FPTAS osim ako je P=NP.[3][4]

Ograničena i neograničena varijanta (za sve fiksne ) imaju istu složenost.[5]

Za bilo koje fiksno , ovi problemi imaju pseudo-polinomijalni algoritam (sličan onom za klasičn problem ranca) i PTAS.[2]

Ranac-slični problemi[уреди]

Ako su sve vrednosti jednake 1, možemo da pokušamo da minimizujemo broj predmeta koji tačno popunjuju ranac:

minimalno
predmet

Ako imamo broj skladišta (iste veličine), i želimo da spakujemo svih n predmeta u što je manje moguće skladišta, dobijamo bin-problem ranca, koji je urađen tako da ima indikator za varijable skladište i se trenutno koristi:

milimalno
predmet
  • Problem seckanja zaliha je identičan bin-problemu ranca, ali pošto parcijalne istance obično imaju mnogo manje tipova predmeta, često se koristi druga formulacija. Predmet j je potreban Bj puta, svaki primer premdeta koji može da stane u samo jedan ranac ima promenljivu, xi (postoji m primera), i primer i koristi predmet j bij puta:
minimalno
predmet za sve
za sve

Ako na višestruki problem ranca, dodamo ograničenje da je svaki podskup veličine n i uklonimo ograničenje za konačnu težinu, dobijamo problem zadatka, koji je takođe problem pronalaženja maksimalnog bipartitivnog poklapanja:

maksimalno
predmet za sve
za sve
za sve i sve

U varijanti ranac maksimalne gustine postoji inicijalna težina , i mi uvećavamo gustinu izabranog predemta koi ne ugrožava kapacitet ograničenja: [6]

maksimalno
predmet

Iako su manje poznadi od problema pomenutih iznad, postoji još nekoliko ranac-sličnih problema, uključujući:

  • Ugneždeni problem ranca
  • Kolapsirajući problem ranca
  • Nelinearan problem ranca
  • Obrnuto-parametarski problem ranca

Od ovih, poslednja tri su obrađena u referencnom radu Kellerer-a i drugih, Knapsack Problems.[2]

Reference[уреди]

  1. Lueker, G.S. (1975). „Report No. 178, Computer Science Laboratory, Princeton”. 
  2. 2,0 2,1 2,2 Kellerer, Hans and Pferschy, Ulrich and Pisinger, David (2004). Knapsack Problems. Springer Verlag. ISBN 3-540-40286-1. 
  3. Gens, G. V. and Levner, E. V. (1979). „Complexity and Approximation Algorithms for Combinatorial Problems: A Survey”. Central Economic and Mathematical Institute, Academy of Sciences of the USSR, Moscow. 
  4. „On the Existence of Fast Approximation Schemes”. Nonlinear Programming. Academic Press. 4: 415—437. 1980. 
  5. Magazine, M. J.; Chern, M.-S. (1984). „A Note on Approximation Schemes for Multidimensional Knapsack Problems”. Mathematics of Operations Research. 9 (2): 244—247. doi:10.1287/moor.9.2.244. 
  6. Cohen, R. and Katzir, L. 2008. The Generalized Maximum Coverage Problem. Inf. Process. Lett. 108, 1 (Sep. 2008), 15-22.

Literatura[уреди]