Википедија

Problem zatvorenja

U teoriji grafova i kombinatornoj optimizaciji, zatvorenje usmerenog grafa je skup čvorova bez izlaznih grana. To znači, da graf ne može da ima grane koje polaze iz oblasti zatvorenja a završavaju se izvan te oblasti. Problem zatvorenja je postupak pronalaženja zatvorenja sa maksimalnom ili minimalnom težinom čvorova u usmerenom grafu sa težinskim čvorovima.[1][2] Problem može biti rešen u polinomijalnom vremenu svođenjem na rešavanje problema maksimalnog protoka. Može se koristiti za modelovanje različitih aplikativnih problema pri biranju optimalnog podskupa izvršnih zadataka, uz postojanje zavisnosti između parova zadataka, kao što je na primer postupak vađenja rude u rudniku sa otvorenim kopom.

Algoritmi

uredi

Sažimanje - kondenzacija

uredi

Zatvorenje maksimalne težine datog grafa G je isto što i komplement zatvorenje minimalne težine transponovanog grafa G, stoga su oba problema ekvivalentna po računskoj složenosti.

Ako dva čvora grafa pripadaju istoj čvrsto povezanoj komponenti, oni mora da se ponašaju isto u odnosu na sva svoja zatvorenja: nije moguće da zatvorenje sadrži jedan čvor a drugi ne. Zato se ulazni graf za problem zatvorenja može zameniti svojim sažetkom, u kome je svaka čvrsto povezana komponenta zamenjena pojedinačnim čvorom. Sažetak je uvek usmereni aciklički graf.

Svođenje na maksimalni protok

uredi

Pikar 1976 je pokazao[2][3] da je zatvorenje sa maksimalnom težinom moguće dobiti iz G rešavanjem problema maksimalnog protoka na grafu H konstruisanog dodavanjem na graf G dva dodatna čvora s i t. Za svaki čvor v sa pozitivnom težinom u G, uvećani graf H sadrži granu od čvora s do v sa kapacitetom jednakim težini v, a za svaki čvor v sa negativnom težinom u G, uvećani graf H sadrži granu od čvora v do t čiji je kapacitet negativna težina od v. Svim granama u G su dati beskonačni kapaciteti u H.[1]

Minimalni odsečak koji odvaja s od t na ovom grafu ne može da ima grane od G koje su direktno usmerene duž odsečka: odsečak sa takvom granom bi imao beskonačni kapacitet i ne bi bio minimum. Zato skup čvorova na istoj strani odsečka kao s automatski formira zatvorenje C. Kapacitet odsečka je jednak težini svih nenegativnih čvorova umanjeno za težinu čvorova u C, koji je minimizovan kada je težina u C-u maksimalna. Sa maksimalni protok - minimalni odsečak teoremom, rešavanjem problema maksimalnog protoka, može da se izvede minimalni odsečak i optimalno zatvorenje.[1]

Alternativni algoritmi

uredi

Alternativni algoritmi za problem maksimalnog zatvorenja koji ne izračunvaju tokove su takođe proučavani.[4][5][6] Njihovo vreme izvršenja je slično vremenu najbržih poznatih algoritama protoka.[4]

Primene

uredi

Rudnici sa otvorenim kopom

uredi

Površinski kop rudnika može biti modeliran kao skup blokova materijala koji se mogu ukloniti samo ako su uklonjeni svi blokovi direktno iznad njih. Blok ima ukupnu vrednost, koja je jednaka vrednosti minerala koji se mogu izdvojiti iz njega, umanjenu za troškove izdvajanja minerala i vađenja bloka; u nekim slučajevima, blok nema vrednost ali ipak mora biti uklonjen da bi se stiglo do sledećih blokova, tom bloku se dodeljuje negativna vrednost.

Može se definisati aciklička mreža koja ima čvorove koji odgovaraju blokovima materijala, sa granama svakog bloka koje povezuju taj blok sa blokovima iznad njega koji pre njega moraju da se uklone. Težina svakog čvora ove mreže odgovara ukupnoj vrednosti bloka. Najprofitabilniji plan iskopavanja je moguće dobiti pronalaženjem zatvorenja sa maksimalnom težinom, a zatim treba formirati topološki redosled blokova tog zatvorenja.[1][5][7]

Vojni sistemi nišanjenja

uredi

U vojnim operacijama, mete visoke vrednosti kao što su komandni centri, su često zaštićeni višeslojnim sistemima odbrane, koji mogu zauzvrat biti zaštićeni drugim sistemima. Da bi se pogodila meta, svi sistemi odbrane moraju prvo biti uklonjeni, tako da originalna meta postaje sekundarna meta. Na svaku metu treba usmeriti određenu količinu sredstava da bi napad bio uspešan. Optimalni skup ciljeva za napad, da bi se dobila najviša vrednost pogotka, u odnosu na utrošene resurse, može da se modelira kao problem za zatvorenje grafa.[1][8]

Planiranje mreže za dostavu robe

uredi

Problem planiranja sistema dostave robe može da se modelira mrežom u kojoj čvorovi predstavljaju gradove a (neusmerene) grane predstavljaju rute za potencijalne isporuke tereta između dva grda. Svaka ruta može da donosi izvestan prihod, ali se može koristiti samo ako su skladišta za teret sagrađena na oba kraja rute, uz određene troškove. Problem dizajniranja mreže koja maksimizira razliku između profita i troškova može se rešiti kao problem zatvorenja, tako što bi se svaka neusmerena grana podelila na dve usmerene grane, obe usmerene izvan u odnosu na tačku podele. Težina svake tačke podele je pozitivan broj, tj. profit odgovarajuće rute, a težina originalnog čvora grafa je negativan broj, tj. troškovi gradnje skladišta u tom odgovarajućem gradu.[1][9] Zajedno sa rudnicima sa otvorenim kopom, ovo je bio jedan od originalnih motivacionih aplikacija za proučavanje problema zatvorenja; 1970. je proučavan u dva nezavisna objavljena rada u istom izdanju i istom časopisu od strane J.M.V. Risa i Mišela Belinskog.[9][10][11]

Raspoređivanje poslova

uredi

Sidni 1975 i Lavler 1978 opisuju primenu problema zatvorenja na primeru rasporeda poslova u prodavnici gde je dat skup zadataka koje treba rasporediti za izvršenje, na način jedan po jedan. Svakom zadatku pridružena su dva broja: težina ili prioritet, i vreme obrade odnosno vreme potrebno za izvršenje zadatka. Pored toga, zadaci imaju ograničenja prvenstva: određeni zadaci se moraju izvršiti pre drugih. Ova ograničenja prioriteta mogu se opisati pomoću usmerenog acikličnog grafa G u kome grane između dva zadatka ukazuju da prvi zadatak mora biti izvršen pre drugog zadatka. Cilj je da se izabere redosled koji je u skladu sa ograničenjima (topološki redosled od G) koji minimizira ukupno težinsko vreme izvršenja zadatka.[12][13]

Iako je Lavler pokazao da je problem zakazivanja poslova NPNP-kompletan u celini, Sidni je opisao metod razčlanjivanja (dekompozicije) koji pomaže u rešavanju problema svodeći ga na nekoliko manjih problema istog tipa. Konkretno, ako je S podskup od zadataka koji (među svim podskupovima) ima najveću moguću razmeru između ukupne težine i ukupnog vremena obrade, i pored toga S je minimalan u odnosu na sve skupove sa istom razmerom, pa onda postoji optimalni raspored u kojem se svi zadaci u S obavljaju pre svih drugih zadataka. Dokle god S nije kompletan skup zadataka, ova podela zadataka deli problem raspoređivanja poslova u dva manja problema, jedan raspoređuje S a drugi raspoređuje preostale zadatke.[12] Iako je S zatvorenje (za graf sa obrnutim granama od G) problem pronalaženja S nije baš pravi problem zatvorenja sa maksimalnom težinom jer je vrednost S razmera a ne suma težina. Ipak, Lavler je pokazao da se S može naći u polinomijalnom vremenu pomoću algoritma za binarno pretraživanje u kome svaki stepen pretraživanja koristi slučaj problema zatvorenja kao podprogram.[13]

Reference

uredi
  1. ^ a b v g d đ Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993), „19.2 Maximum weight closure of a graph”, Network flows, Englewood Cliffs, NJ: Prentice Hall Inc., str. 719—724, ISBN 978-0-13-617549-0, MR 1205775 
  2. ^ a b Cook, William J.; Cunningham, William H.; Pulleyblank, William R.; Schrijver, Alexander (2011), „Optimal closure in a digraph”, Combinatorial Optimization, Wiley Series in Discrete Mathematics and Optimization, 33, John Wiley & Sons, str. 49—50, ISBN 9781118031391 
  3. ^ Picard, Jean-Claude (1976), „Maximal closure of a graph and applications to combinatorial problems”, Management Science, 22 (11): 1268—1272, MR 0403596, doi:10.1287/mnsc.22.11.1268 
  4. ^ a b Hochbaum, Dorit S. (2001), „A new-old algorithm for minimum-cut and maximum-flow in closure graphs”, Networks, 37 (4): 171—193, MR 1837196, doi:10.1002/net.1012 
  5. ^ a b Lerchs, H.; Grossmann, I. F. (1965), „Optimum design of open-pit mines”, Transactions of the Canadian Institute of Mining and Metallurgy, 68: 17—24 . As cited by Hochbaum 2001
  6. ^ Faaland, Bruce; Kim, Kiseog; Schmitt, Tom (1990), „A new algorithm for computing the maximal closure of a graph”, Management Science, 36 (3): 315—331, doi:10.1287/mnsc.36.3.315 
  7. ^ Johnson, T. B. (1968), Optimum pit mine production scheduling, Technical Report, University of California, Berkeley, CA . As cited by Ahuja, Magnanti & Orlin 1993
  8. ^ Orlin, D. (1987), „Optimal weapons allocation against layered defenses”, Naval Research Logistics Quarterly, 34: 605—617, doi:10.1002/1520-6750(198710)34:5<605::aid-nav3220340502>3.0.co;2-l . As cited by Ahuja, Magnanti & Orlin 1993
  9. ^ a b Hochbaum, Dorit (2004), „50th Anniversary Article: Selection, Provisioning, Shared Fixed Costs, Maximum Closure, and Implications on Algorithmic Methods Today”, Management Science, 50 (6): 709—723, doi:10.1287/mnsc.1040.0242 
  10. ^ Rhys, J. M. W. (1970), „A selection problem of shared fixed costs and network flows”, Management Science, 17 (3): 200—207, doi:10.1287/mnsc.17.3.200 
  11. ^ Balinski, M. L. (1970), „On a selection problem”, Management Science, 17 (3): 230—231, doi:10.1287/mnsc.17.3.230 
  12. ^ a b Sidney, Jeffrey B. (1975), „Decomposition algorithms for single-machine sequencing with precedence relations and deferral costs”, Operations Research, 23 (2): 283—298, doi:10.1287/opre.23.2.283 
  13. ^ a b Lawler, E. L. (1978), „Sequencing jobs to minimize total weighted completion time subject to precedence constraints”, Ann. Discrete Math., 2: 75—90, MR 0495156, doi:10.1016/S0167-5060(08)70323-6 
Preuzeto iz „https://sr.wikipedia.org/w/index.php?title=Проблем_затворења&oldid=27753936”