Back

ⓘ Problem ranca




Problem ranca
                                     

ⓘ 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 1 ≤ j ≤ n {\displaystyle 1\leq j\leq n} ima pridruženu vrednost p j i težinu w j. Cilj je sakupiti odredeni broj predmeta, tako da vrednost ranca bude maksimalna, ali da težina ranca ne prede 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:

                                     

1. 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 u j koja može biti pozitivan ceo broj ili beskonačno za broj predmeta j može biti izabrano:

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

Lueker je pokazao 1975. godine 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 N i {\displaystyle N_{i}}, i ako iz svake klase mora da se uzme tačno jedan predmet, dobija se problem ranca sa višetrukim izborom:

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

Ako imamo n predmeta i m rančeva sa kapacitetima W i {\displaystyle W_{i}}, dobijamo višestruki problem ranca:

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:

Problem ranca - Unija skupa:

SUKP Set-Union Knapsack Problem je definisao Kellerer i dr. na 423. str.:

Dat je skup od n {\displaystyle n} predmeta N = { 1, …, n } {\displaystyle N=\{1,\ldots,n\}} i skup od m {\displaystyle m}, tako reći, elemenata P = { 1, …, m } {\displaystyle P=\{1,\ldots,m\}}, gde svaki predmet j {\displaystyle j} odgovara podskupu P j {\displaystyle P_{j}} skupa elemenata P {\displaystyle P}. Predmeti j {\displaystyle j} imaju nenegativne vrednosti p j {\displaystyle p_{j}}, j = 1, …, n {\displaystyle j=1,\ldots,n}, a elementi i {\displaystyle i} nenegativne težine w i {\displaystyle w_{i}}, i = 1, …, m {\displaystyle i=1,\ldots,m}. 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.

                                     

2. Višestruko ograničenje

Ako postoji više od jednog ograničenja, 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.

Pokazano je da je varijanta 0-1 za sve fiksne m ≥ 2 {\displaystyle m\geq 2} NP-komplentna oko 1980. godine i da nema FPTAS osim ako je P=NP.

Ograničena i neograničena varijanta za sve fiksne m ≥ 2 {\displaystyle m\geq 2} imaju istu složenost.

Za bilo koje fiksno m ≥ 2 {\displaystyle m\geq 2}, ovi problemi imaju pseudo-polinomijalni algoritam sličan onom za klasičn problem ranca i PTAS.

                                     

3. Ranac-slični problemi

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

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 uraden tako da ima indikator za varijable y i = 1 ⇔ {\displaystyle y_{i}=1\Leftrightarrow } skladište i se trenutno koristi:

  • 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 B j puta, svaki primer premdeta koji može da stane u samo jedan ranac ima promenljivu, x i postoji m primera, i primer i koristi predmet j b ij puta

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 takode problem pronalaženja maksimalnog bipartitivnog poklapanja:

U varijanti ranac maksimalne gustine postoji inicijalna težina w 0 {\displaystyle w_{0}}, mi uvećavamo gustinu izabranog predemta koi ne ugrožava kapacitet ograničenja:

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

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

Od ovih, poslednja tri su obradena u referencnom radu Kellerer-a i drugih, Knapsack Problems.



                                     
  • može da se posmatra kao poseban slučaj problema ranca Jedan zanimljiv slučaj poseban zbir podskupa podela problema u kojem je s polovina sume svih elemenata
  • da se pritom iskoristi najmanji mogući broj novčića? Ovaj problem je nalik problemu ranca i ima veću primenu od pukog vraćanja kusura. Vrednosti novčiča
  • Н - слагалица Проблем ранца Проблем Хамилтоновог циклуса Проблем трговачког путника Приблем изоморфизма подграфа Проблем суме подскупа Проблем клике Проблем покривача
  • pogrešnih rezultata. Da bi se koristila heuristika za rešavanja problema pretrage ili problema ranca neophodno je proveriti da li je heuristika dopustiva. Ako
  • понекад и најефикаснија као и при решавању проблема ранца и комбинаторним оптимизацијама неких проблема Такође бектрекинг је база за такозване логичке
  • fitnes uvek zavisi od problema Na primer u problemu ranca neko želi najveću ukupnu vrednost predmeta koja se može staviti u ranac fiksnog kapaciteta.
  • Динамичко програмирање је метод којим се смањује време извршавања оних проблема у којима се захтева тражење оптималне подструктуре и који имају потпроблеме
  • ранца итд. Искуство је потребно за коришћење карте, компаса, висиномера, и друге опреме. Основна планинарска опрема подразумева ципеле, јакну, ранац
  • самостално смишља своју руту и спроводи је у дело. Путник сам решава логистичке проблеме смештаја, превоза и исхране, путује са најчешће скромним финансијским средствима